# 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 ${\displaystyle {\mathcal {L_{S}}}\,\!}$ (and now ${\displaystyle {\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 ${\displaystyle {\mathcal {L_{S}}}\,\!}$ are sentences. This enabled rules for assigning truth values directly to larger formulae. For the predicate language ${\displaystyle {\mathcal {L_{P}}}\,\!}$, the situation is more complex. Not all formulae of ${\displaystyle {\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 ${\displaystyle {\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. ${\displaystyle \forall x\,\!}$ is then interpreted as 'for any object ${\displaystyle x\,\!}$ in the domain …'; ${\displaystyle \exists x\,\!}$ is interpreted as 'there exists at least one object ${\displaystyle 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 ${\displaystyle {\mathfrak {M}}\,\!}$, written ${\displaystyle |{\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 ${\displaystyle {\mathfrak {M}}\,\!}$ is ${\displaystyle 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 ${\displaystyle |{\mathfrak {M}}|\,\!}$ above and ${\displaystyle a_{0}^{0}\,\!}$ is assigned 0, then we think of ${\displaystyle 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 ${\displaystyle a_{0}^{0}\,\!}$ can be expressed as:

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

${\displaystyle {\mathfrak {f}}_{0}^{2}(0,0)=2,\quad {\mathfrak {f}}_{0}^{2}(0,1)=1,\quad {\mathfrak {f}}_{0}^{2}(0,2)=0,\,\!}$
${\displaystyle {\mathfrak {f}}_{0}^{2}(1,0)=1,\quad {\mathfrak {f}}_{0}^{2}(1,1)=0,\quad {\mathfrak {f}}_{0}^{2}(1,2)=2,\,\!}$
${\displaystyle {\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:

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

Suppose that ${\displaystyle a_{0}^{0}\,\!}$ is assigned 0 as above and also that ${\displaystyle b_{0}^{0}\,\!}$ is assigned 1. Then we can intuitively think of the informally written ${\displaystyle 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 ${\displaystyle \pi \,\!}$ a sentence letter, either
${\displaystyle I_{\mathfrak {M}}(\pi )=\mathrm {True} \,\!}$

or

${\displaystyle 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 ${\displaystyle |{\mathfrak {M}}|\,\!}$ above and assume the assignment

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

Suppose that ${\displaystyle a_{0}^{0}\,\!}$ is assigned 0, ${\displaystyle b_{0}^{0}\,\!}$ is assigned 1, and ${\displaystyle c_{0}^{0}\,\!}$ is assigned 2. Then intuitively ${\displaystyle \mathrm {F} (a,b)\,\!}$, ${\displaystyle \mathrm {F} (b,c)\,\!}$, and ${\displaystyle \mathrm {F} (c,b)\,\!}$ should each be true. However, ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle {\mathfrak {M}}\,\!}$, are:

${\displaystyle |{\mathfrak {M}}|\ =\ \{0,\ 1,\ 2\}\ .\,\!}$
${\displaystyle I_{\mathfrak {M}}(a_{0}^{0})\ =\ 0\ .\,\!}$
${\displaystyle I_{\mathfrak {M}}(b_{0}^{0})\ =\ 1\ .\,\!}$
${\displaystyle I_{\mathfrak {M}}(c_{0}^{0})\ =\ 2\ .\,\!}$
${\displaystyle 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,\,\!}$
${\displaystyle {\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,\,\!}$
${\displaystyle {\mathfrak {f}}_{0}^{2}(2,1)=2,\ {\mbox{and}}\ {\mathfrak {f}}_{0}^{2}(2,2)=1\ .\,\!}$
${\displaystyle 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:

${\displaystyle f(a,b)\ {\mbox{resolves to}}\ 1\ \mathrm {in} \ {\mathfrak {M}}\ .\,\!}$
${\displaystyle \mathrm {F} (a,b),\ \mathrm {F} (b,c),\ {\mbox{and}}\ \mathrm {F} (c,b)\ {\mbox{are True in}}\ {\mathfrak {M}}\ .\,\!}$
${\displaystyle \mathrm {F} (a,a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!}$

Some more desired results can be added:

${\displaystyle \mathrm {F} (a,f(a,b))\ {\mbox{is True in}}\ {\mathfrak {M}}\ .\,\!}$
${\displaystyle \mathrm {F} (f(a,b),a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!}$
${\displaystyle \mathrm {F} (c,b)\rightarrow \mathrm {F} (a,b)\ {\mbox{is True in}}\ {\mathfrak {M}}\ .\,\!}$
${\displaystyle \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 ${\displaystyle {\mathcal {L_{P}}}\,\!}$ and assign then the numbers 0, 1, and 2 respectively. We then want:

${\displaystyle (1)\quad \mathrm {F} (0,1)\rightarrow \mathrm {F} (1,0)\quad {\mbox{False in}}\ {\mathfrak {M}}\ .\,\!}$
${\displaystyle (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:

${\displaystyle \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:

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

### An infinite model

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

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

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

The assignments to individual constant symbols can be as before:

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

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

${\displaystyle 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 ${\displaystyle \mathrm {F_{0}^{2}} \,\!}$ can be assigned, for example, the less than relation:

${\displaystyle 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:

${\displaystyle f(a,b)\ {\mbox{resolves to}}\ 1\ \mathrm {in} \ {\mathfrak {M}}_{2}\ .\,\!}$
${\displaystyle \mathrm {F} (a,b)\ {\mbox{and}}\ \mathrm {F} (b,c)\ {\mbox{are True in}}\ {\mathfrak {M}}_{2}\ .\,\!}$
${\displaystyle \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:

${\displaystyle \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:

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