Formal Logic/Predicate Logic/Models

Models

Interpretations

We said earlier that the formal semantics for a formal language such as ${ℒ}_{𝒮}$ (and now ${ℒ}_{𝒫}$) 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 ${ℒ}_{𝒮}$ are sentences. This enabled rules for assigning truth values directly to larger formulae. For the predicate language ${ℒ}_{𝒫}$, the situation is more complex. Not all formulae of ${ℒ}_{𝒫}$ 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 $𝔐$.

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. $\mathrm{\forall }x$ is then interpreted as 'for any object $x$ in the domain …'; $\mathrm{\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 $𝔐$, written $|𝔐|$, 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 $𝔐$ is $I_{𝔐}$.

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 $|𝔐|$ 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_{𝔐}(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 $|𝔐|$ 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 ${𝔣}_0^2$ such that:

${𝔣}_0^2(0,0)=2,{𝔣}_0^2(0,1)=1,{𝔣}_0^2(0,2)=0,$

${𝔣}_0^2(1,0)=1,{𝔣}_0^2(1,1)=0,{𝔣}_0^2(1,2)=2,$

${𝔣}_0^2(2,0)=0,{𝔣}_0^2(2,1)=2,{𝔣}_0^2(2,2)=1.$

The assignment to the operation letter is written as:

$I_{𝔐}(f_0^2)={𝔣}_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_{𝔐}(\pi )=\mathrm{T}\mathrm{r}\mathrm{u}\mathrm{e}$

or

$I_{𝔐}(\pi )=\mathrm{F}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e}.$

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 $|𝔐|$ above and assume the assignment

$I_{𝔐}(F_{\mathrm{0}}^{\mathrm{2}})=\{⟨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 (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 $𝔐$, are:

$|𝔐|=\{0,1,2\}.$

$I_{𝔐}(a_0^0)=0.$

$I_{𝔐}(b_0^0)=1.$

$I_{𝔐}(c_0^0)=2.$

$I_{𝔐}(f_0^2)={𝔣}_0^2\text{such that:}{𝔣}_0^2(0,0)=2,{𝔣}_0^2(0,1)=1,{𝔣}_0^2(0,2)=0,$

${𝔣}_0^2(1,0)=1,{𝔣}_0^2(1,1)=0,{𝔣}_0^2(1,2)=2,{𝔣}_0^2(2,0)=0,$

${𝔣}_0^2(2,1)=2,\text{and}{𝔣}_0^2(2,2)=1.$

$I_{𝔐}(F_{\mathrm{0}}^{\mathrm{2}})=\{⟨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)\text{resolves to}1\mathrm{i}\mathrm{n}𝔐.$

$\mathrm{F}(a,b),\mathrm{F}(b,c),\text{and}\mathrm{F}(c,b)\text{are True in}𝔐.$

$\mathrm{F}(a,a)\text{is False in}𝔐.$

Some more desired results can be added:

$\mathrm{F}(a,f(a,b))\text{is True in}𝔐.$

$\mathrm{F}(f(a,b),a)\text{is False in}𝔐.$

$\mathrm{F}(c,b)\to \mathrm{F}(a,b)\text{is True in}𝔐.$

$\mathrm{F}(c,b)\to \mathrm{F}(b,a)\text{is False in}𝔐.$

We can temporarily pretend that the numerals '0', '1', and '2' are added to ${ℒ}_{𝒫}$ and assign then the numbers 0, 1, and 2 respectively. We then want:

$(1)\mathrm{F}(0,1)\to \mathrm{F}(1,0)\text{False in}𝔐.$

$(2)\mathrm{F}(1,2)\wedge \mathrm{F}(2,1)\text{True in}𝔐.$

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

$\mathrm{\forall }x\mathrm{\forall }y(\mathrm{F}(x,y)\to \mathrm{F}(y,x))\text{is false in }𝔐.$

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

$\mathrm{\exists }x\mathrm{\exists }y(\mathrm{F}(x,y)\wedge \mathrm{F}(y,x))\text{is true in}𝔐.$

An infinite model

The domain $|𝔐|$ had finitely many members; 3 to be exact. Domains can have infinitely many members. Below is an example model ${𝔐}_2$ with an infinitely large domain.

The domain $|{𝔐}_2|$ is the set of natural numbers:

$|{𝔐}_2|=\{0,1,2,...\}$

The assignments to individual constant symbols can be as before:

$I_{{𝔐}_2}(a_0^0)=0.$

$I_{{𝔐}_2}(b_0^0)=1.$

$I_{{𝔐}_2}(c_0^0)=2.$

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

$I_{{𝔐}_2}(f_0^2)={𝔣}_0^2\text{such that}{𝔣}_0^2(u,v)=u+v.$

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

$I_{{𝔐}_2}(F_{\mathrm{0}}^{\mathrm{2}})=\{⟨x,y⟩:x<y\}.$

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

$f(a,b)\text{resolves to}1\mathrm{i}\mathrm{n}{𝔐}_2.$

$\mathrm{F}(a,b)\text{and}\mathrm{F}(b,c)\text{are True in}{𝔐}_2.$

$\mathrm{F}(c,b)\text{and}\mathrm{F}(a,a)\text{are False in}{𝔐}_2.$

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

$\mathrm{\forall }x\mathrm{\exists }y\mathrm{F}(x,y)\text{is true in}{𝔐}_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:

$\mathrm{\forall }x\mathrm{\exists }y\mathrm{F}(y,x)\text{is false in}{𝔐}_2.$