# 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 {1, 2, 3}.

### 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^2_0\,\!$. The function assigned to $f^2_0\,\!$ must then be defined on each ordered pair from the domain. For example, it can be the function $\mathfrak{f}^2_0\,\!$ such that:

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

The assignment to the operation letter is written as:

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

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^2_0}) = \{<\!0,\ 1\!>,\ <\!1,\ 2\!>,\ <\!2,\ 1\!>\}\ .\,\!$

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 <2, 3>.

### 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 ( aset 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}|\ =\ \{1,\ 2,\ 3\}\ .\,\!$
$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^2_0)\ =\ \mathfrak{f}^2_0\ \mbox{such that:} \quad \mathfrak{f}^2_0(0, 0) = 2,\ \mathfrak{f}^2_0(0, 1)\ =\ 1,\ \mathfrak{f}^2_0(0, 2) = 0,\,\!$
$\mathfrak{f}^2_0(1, 0) = 1,\ \mathfrak{f}^2_0(1, 1)\ =\ 0,\ \mathfrak{f}^2_0(1, 2) = 2,\ \mathfrak{f}^2_0(2, 0) = 0,\,\!$
$\mathfrak{f}^2_0(2, 1) = 2,\ \mbox{and}\ \mathfrak{f}^2_0(2, 2) = 1\ .\,\!$
$I_{\mathfrak{M}}(\mathrm{F^2_0})\ =\ \{<\!0,\ 1\!>,\ <\!1,\ 2\!>,\ <\!2,\ 1\!>\}\ .\,\!$

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. Models 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^2_0)\ =\ \mathfrak{f}^2_0\ \mbox{such that}\ \mathfrak{f}^2_0(u, v) = u + v\ .\,\!$

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

$I_{\mathfrak{M}_2}(\mathrm{F^2_0})\ =\ \{<\!x,\ y\!>:\ 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\ .\,\!$