# 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

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}\ .\,\!$