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

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}} )=\{<\!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_{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}} )\ =\ \{<\!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_{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}} )\ =\ \{<\!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}\ .\,\!

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.