Formal Logic/Predicate Logic/Models

← Informal Conventions

↑ Predicate Logic

Satisfaction →

Models

Interpretations

We said earlier that the formal semantics for a formal language such as ${\mathcal {L_{S}}}\,\!$ (and now ${\mathcal {L_{P}}}\,\!$) goes in two parts.

• Rules for specifying an interpretation. An interpretation assigns semantic values to the non-logical symbols of a formal syntax. Just as a valuation was an interpretation for a sentential language, a model is an interpretation for a predicate language.

• Rules for assigning semantic values to larger expressions of the language. All formulae of the sentential language ${\mathcal {L_{S}}}\,\!$ are sentences. This enabled rules for assigning truth values directly to larger formulae. For the predicate language ${\mathcal {L_{P}}}\,\!$, the situation is more complex. Not all formulae of ${\mathcal {L_{P}}}\,\!$ are sentences. We will need to define the auxiliary notion satisfaction and use that when assigning truth values.

Models

A model is an interpretation for a predicate language. It consists of two parts: a domain and interpretation function. Along the way, we will progressively specify an example model ${\mathfrak {M}}\,\!$.

Domain

• A domain is a non-empty set.

Intuitively, the domain contains all the objects under current consideration. It contains all of the objects over which the quantifiers range. $\forall x\,\!$ is then interpreted as 'for any object $x\,\!$ in the domain …'; $\exists x\,\!$ is interpreted as 'there exists at least one object $x\,\!$ in the domain such that …'. Our predicate logic requires that the domain be non-empty, i.e., that it contains at least one object.

The domain of our example model ${\mathfrak {M}}\,\!$, written $|{\mathfrak {M}}|\,\!$, is {0, 1, 2}.

Interpretation function

• An interpretation function is an assignment of semantic value to each operation letter and predicate letter.

The interpretation function for model ${\mathfrak {M}}\,\!$ is $I_{\mathfrak {M}}\,\!$.

Operation letters

• To each constant symbol (i.e., zero-place operation letter) is assigned a member of the domain.

Intuitively, the constant symbol names the object, a member of the domain. If the domain is $|{\mathfrak {M}}|\,\!$ above and $a_{0}^{0}\,\!$ is assigned 0, then we think of $a_{0}^{0}\,\!$ naming 0 just as the name 'Socrates' names the man Socrates or the numeral '0' names the number 0. The assignment of 0 to $a_{0}^{0}\,\!$ can be expressed as:

$I_{\mathfrak {M}}(a_{0}^{0})=0\ .\,\!$

• To each n-place operation letter with n greater than zero is assigned an n+1 place function taking ordered n-tuples of objects (members of the domain) as its arguments and objects (members of the domain) as its values. The function must be defined on all n-tuples of members of the domain.

Suppose the domain is $|{\mathfrak {M}}|\,\!$ above and we have a 2-place operation letter $f_{0}^{2}\,\!$. The function assigned to $f_{0}^{2}\,\!$ must then be defined on each ordered pair from the domain. For example, it can be the function ${\mathfrak {f}}_{0}^{2}\,\!$ such that:

${\mathfrak {f}}_{0}^{2}(0,0)=2,\quad {\mathfrak {f}}_{0}^{2}(0,1)=1,\quad {\mathfrak {f}}_{0}^{2}(0,2)=0,\,\!$

${\mathfrak {f}}_{0}^{2}(1,0)=1,\quad {\mathfrak {f}}_{0}^{2}(1,1)=0,\quad {\mathfrak {f}}_{0}^{2}(1,2)=2,\,\!$

${\mathfrak {f}}_{0}^{2}(2,0)=0,\quad {\mathfrak {f}}_{0}^{2}(2,1)=2,\quad {\mathfrak {f}}_{0}^{2}(2,2)=1\ .\,\!$

The assignment to the operation letter is written as:

$I_{\mathfrak {M}}(f_{0}^{2})={\mathfrak {f}}_{0}^{2}\ .\,\!$

Suppose that $a_{0}^{0}\,\!$ is assigned 0 as above and also that $b_{0}^{0}\,\!$ is assigned 1. Then we can intuitively think of the informally written $f(a,b)\,\!$ as naming (referring to, having the value) 1. This is analogous to 'the most famous student of Socrates' naming (or referring to) Plato or '2 + 3' naming (having the value) 5.

Predicate letters

• To each sentence letter (i.e., zero-place predicate letter) is assigned a truth value. For $\pi \,\!$ a sentence letter, either

$I_{\mathfrak {M}}(\pi )=\mathrm {True} \,\!$

or

$I_{\mathfrak {M}}(\pi )=\mathrm {False} \ .\,\!$

This is the same treatment sentence letters received in sentential logic. Intuitively, the sentence is true or false accordingly as the sentence letter is assigned the value 'True' or 'False'.

• To each n-place predicate letter with n greater than zero is assigned an n-place relation (a set of ordered n-tuples) of members of the domain.

Intuitively, the predicate is true of each n-tuple in the assigned set. Let the domain be $|{\mathfrak {M}}|\,\!$ above and assume the assignment

$I_{\mathfrak {M}}(\mathrm {F_{0}^{2}} )\ =\ \{\langle 0,\ 1\rangle ,\ \langle 1,\ 2\rangle ,\ \langle 2,\ 1\rangle \}.$

Suppose that $a_{0}^{0}\,\!$ is assigned 0, $b_{0}^{0}\,\!$ is assigned 1, and $c_{0}^{0}\,\!$ is assigned 2. Then intuitively $\mathrm {F} (a,b)\,\!$, $\mathrm {F} (b,c)\,\!$, and $\mathrm {F} (c,b)\,\!$ should each be true. However, $\mathrm {F} (a,c)\,\!$, among others, should be false. This is analogous to 'is snub-nosed' being true of Socrates and 'is greater than' being true of $\langle 2,3\rangle$.

Summary

The definition is interspersed with examples and so rather spread out. Here is a more compact summary. A model consists of two parts: a domain and interpretation function.

• A domain is a non-empty set.

• An interpretation function is an assignment of semantic value to each operation letter and predicate letter. This assignment proceeds as follows:

• To each constant symbol (i.e., zero-place operation letter) is assigned a member of the domain.
• To each n-place operation letter with n greater than zero is assigned an n+1 place function taking ordered n-tuples of objects (members of the domain) as its arguments and objects (members of the domain) as its values.
• To each sentence letter (i.e., zero-place predicate letter) is assigned a truth value.
• To each n-place predicate letter with n greater than zero is assigned an n-place relation (a set of ordered n-tuples) of members of the domain.

Examples

A finite model

An example model was specified in bits and pieces above. These pieces, collected together under the name ${\mathfrak {M}}\,\!$, are:

$|{\mathfrak {M}}|\ =\ \{0,\ 1,\ 2\}\ .\,\!$

$I_{\mathfrak {M}}(a_{0}^{0})\ =\ 0\ .\,\!$

$I_{\mathfrak {M}}(b_{0}^{0})\ =\ 1\ .\,\!$

$I_{\mathfrak {M}}(c_{0}^{0})\ =\ 2\ .\,\!$

$I_{\mathfrak {M}}(f_{0}^{2})\ =\ {\mathfrak {f}}_{0}^{2}\ {\mbox{such that:}}\quad {\mathfrak {f}}_{0}^{2}(0,0)=2,\ {\mathfrak {f}}_{0}^{2}(0,1)\ =\ 1,\ {\mathfrak {f}}_{0}^{2}(0,2)=0,\,\!$

${\mathfrak {f}}_{0}^{2}(1,0)=1,\ {\mathfrak {f}}_{0}^{2}(1,1)\ =\ 0,\ {\mathfrak {f}}_{0}^{2}(1,2)=2,\ {\mathfrak {f}}_{0}^{2}(2,0)=0,\,\!$

${\mathfrak {f}}_{0}^{2}(2,1)=2,\ {\mbox{and}}\ {\mathfrak {f}}_{0}^{2}(2,2)=1\ .\,\!$

$I_{\mathfrak {M}}(\mathrm {F_{0}^{2}} )\ =\ \{\langle 0,\ 1\rangle ,\ \langle 1,\ 2\rangle ,\ \langle 2,\ 1\rangle \}.$

We have not yet defined the rules for generating the semantic values of larger expressions. However, we can see some simple results we want that definition to achieve. A few such results have already been described:

$f(a,b)\ {\mbox{resolves to}}\ 1\ \mathrm {in} \ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (a,b),\ \mathrm {F} (b,c),\ {\mbox{and}}\ \mathrm {F} (c,b)\ {\mbox{are True in}}\ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (a,a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!$

Some more desired results can be added:

$\mathrm {F} (a,f(a,b))\ {\mbox{is True in}}\ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (f(a,b),a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (c,b)\rightarrow \mathrm {F} (a,b)\ {\mbox{is True in}}\ {\mathfrak {M}}\ .\,\!$

$\mathrm {F} (c,b)\rightarrow \mathrm {F} (b,a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!$

We can temporarily pretend that the numerals '0', '1', and '2' are added to ${\mathcal {L_{P}}}\,\!$ and assign then the numbers 0, 1, and 2 respectively. We then want:

$(1)\quad \mathrm {F} (0,1)\rightarrow \mathrm {F} (1,0)\quad {\mbox{False in}}\ {\mathfrak {M}}\ .\,\!$

$(2)\quad \mathrm {F} (1,2)\land \mathrm {F} (2,1)\quad {\mbox{True in}}\ {\mathfrak {M}}\ .\,\!$

Because of (1), we will want as a result:

$\forall x\,\forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\ {\mbox{is false in }}\ {\mathfrak {M}}\ .\,\!$

Because of (2), we will want as a result:

$\exists x\,\exists y\,(\mathrm {F} (x,y)\land \mathrm {F} (y,x))\ {\mbox{is true in}}\ {\mathfrak {M}}\ .\,\!$

An infinite model

The domain $|{\mathfrak {M}}|\,\!$ had finitely many members; 3 to be exact. Domains can have infinitely many members. Below is an example model ${\mathfrak {M}}_{2}\,\!$ with an infinitely large domain.

The domain $|{\mathfrak {M}}_{2}|\,\!$ is the set of natural numbers:

$|{\mathfrak {M}}_{2}|=\{0,1,2,...\}\,\!$

The assignments to individual constant symbols can be as before:

$I_{{\mathfrak {M}}_{2}}(a_{0}^{0})\ =\ 0\ .\,\!$

$I_{{\mathfrak {M}}_{2}}(b_{0}^{0})\ =\ 1\ .\,\!$

$I_{{\mathfrak {M}}_{2}}(c_{0}^{0})\ =\ 2\ .\,\!$

The 2-place operation letter $f\,\!$ can be assigned, for example, the addition function:

$I_{{\mathfrak {M}}_{2}}(f_{0}^{2})\ =\ {\mathfrak {f}}_{0}^{2}\ {\mbox{such that}}\ {\mathfrak {f}}_{0}^{2}(u,v)=u+v\ .\,\!$

The 2-place predicate letter $\mathrm {F_{0}^{2}} \,\!$ can be assigned, for example, the less than relation:

$I_{{\mathfrak {M}}_{2}}(\mathrm {F_{0}^{2}} )\ =\ \{\langle x,\ y\rangle :\ x<y\}\ .\,\!$

Some results that should be produced by the specification of an extended model:

$f(a,b)\ {\mbox{resolves to}}\ 1\ \mathrm {in} \ {\mathfrak {M}}_{2}\ .\,\!$

$\mathrm {F} (a,b)\ {\mbox{and}}\ \mathrm {F} (b,c)\ {\mbox{are True in}}\ {\mathfrak {M}}_{2}\ .\,\!$

$\mathrm {F} (c,b)\ {\mbox{and}}\ \mathrm {F} (a,a)\ {\mbox{are False in}}\ {\mathfrak {M}}_{2}\ .\,\!$

For every x, there is a y such that x < y. Thus we want as a result:

$\forall x\,\exists y\,\mathrm {F} (x,y)\ {\mbox{is true in}}\ {\mathfrak {M}}_{2}\ .\,\!$

There is no y such that y < 0 (remember, we are restricting ourselves to the domain which has no number less than 0). So it is not the case that, for every x, there is a y such that y < x. Thus we want as a result:

$\forall x\,\exists y\,\mathrm {F} (y,x)\ {\mbox{is false in}}\ {\mathfrak {M}}_{2}\ .\,\!$