User:JMRyan/New Page1

← Satisfaction

↑ Predicate Logic

End

Truth

Truth in a model

We have defined satisfaction in a model with a variable assignment. We have expressed formula $\varphi \,\!$ being satisfied by model ${\mathfrak {M}}\,\!$ with variable assignment $\mathrm {s} \,\!$ as:

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \vDash \varphi \,\!$

Now we can also say that a formula $\varphi \,\!$ is satisfied my model ${\mathfrak {M}}\,\!$ (not limited to a specific variable assignment) if and only if $\varphi \,\!$ is satisfied by ${\mathfrak {M}}\,\!$ with every variable assignment. Thus

${\mathfrak {M}}\ \vDash \varphi \,\!$

if and only if

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \vDash \varphi \ {\mbox{for every}}\ \mathrm {s} \ .\,\!$

If no free variables occur in $\varphi ,\,\!$ (thatis, if $\varphi \,\!$ is a sentence), then $\varphi \,\!$ is true in model ${\mathfrak {M}}\,\!$.

Variable assignments allow us to deal with free variables when doing the semantic analysis of a formula. For two variable assignments, $\mathrm {s_{1}} \,\!$ and $\mathrm {s_{2}} \,\!$, satisfaction by $<\!{\mathfrak {M}},\ \mathrm {s_{1}} \!>\,\!$ differs from satisfaction by $<\!{\mathfrak {M}},\ \mathrm {s_{2}} \!>\,\!$ only if the formula has free variables. But sentences do not have free variables. Thus a model satisfies a sentence with at least one variable assignment if and only if it satisfies the sentence with every variable assignment. The following two definitions are equivalent:

$\varphi \,\!$ is true in ${\mathfrak {M}}\,\!$ if and only if there is a variable assignment $\mathrm {s} \,\!$ such that

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \vDash \varphi \ .\,\!$

$\varphi \,\!$ is true in ${\mathfrak {M}}\,\!$ if and only if, for every variable assignment $\mathrm {s} ,\,\!$

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \vDash \varphi \ .\,\!$

The latter is just a notational variant of:

$\varphi \,\!$ is true in ${\mathfrak {M}}\,\!$ if and only if

${\mathfrak {M}}\ \vDash \varphi \ .\,\!$

Examples

A finite model

The example model

On the previous page, we looked at the following model and variable assignment.

For the model $I_{\mathfrak {M}}\ :\,\!$

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

For the variable assignment $\mathrm {s} \ :\,\!$

$\mathrm {s} (x_{0})\ =\ 0\ .\,\!$

$\mathrm {s} (y_{0})\ =\ 1\ .\,\!$

$\mathrm {s} (z_{0})\ =\ 2\ .\,\!$

Example results

We noted the following results:

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \vDash \mathrm {F} (a,b),\ \mathrm {F} (b,c),\ {\mbox{and}}\ \mathrm {F} (c,b)\ .\,\!$

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \not \vDash \mathrm {F} (a,a))\ .\,\!$

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \vDash \mathrm {F} (a,f(a,b))\ .\,\!$

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \not \vDash \mathrm {F} (f(a,b),a)\ .\,\!$

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \vDash \mathrm {F} (c,b)\rightarrow \mathrm {F} (a,b)\ .\,\!$

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \not \vDash \mathrm {F} (c,b)\rightarrow \mathrm {F} (b,a)\ .\,\!$

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \not \vDash \forall x\,\forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\,\!$

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \vDash \exists x\,\exists y\,(\mathrm {F} (x,y)\land \mathrm {F} (y,x))\,\!$

We also noted above that for sentences (though not for formulae in general), a model satisfies the sentence with at least one variable assignment if and only if it satisfies the sentence with every variable assignment. Thus the results just listed hold for every variable assignment, not just $\mathrm {s} \,\!$.

Applying our definition of truth, we get:

$(1)\quad \mathrm {F} (a,b),\ \mathrm {F} (b,c),\ {\mbox{and}}\ \mathrm {F} (c,b)\ {\mbox{are True in}}\ {\mathfrak {M}}\ .\,\!$

$(2)\quad \mathrm {F} (a,a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!$

$(3)\quad \mathrm {F} (a,f(a,b))\ {\mbox{is True in}}\ {\mathfrak {M}}\ .\,\!$

$(4)\quad \mathrm {F} (f(a,b),a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!$

$(5)\quad \mathrm {F} (c,b)\rightarrow \mathrm {F} (a,b)\ {\mbox{is True in}}\ {\mathfrak {M}}\ .\,\!$

$(6)\quad \mathrm {F} (c,b)\rightarrow \mathrm {F} (b,a)\ {\mbox{is False in}}\ {\mathfrak {M}}\ .\,\!$

$(7)\quad \forall x\,\forall y\,(\mathrm {F} (x,y)\rightarrow \mathrm {F} (y,x))\ {\mbox{is false in }}\ {\mathfrak {M}}\ .\,\!$.

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

This corresponds to the goals (1)–(8) of the previous page. We have now achieved those goals.

An infinite model

The example model

On Models page, we also considered an infinite model $I_{\mathfrak {M_{2}}}\ :\,\!$

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

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

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

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

$I_{{\mathfrak {M}}_{2}}(f_{0}^{2})\ =\ {\mathfrak {f}}_{0}^{2}\ {\mbox{such that}}\ {\mathfrak {f}}_{0}^{2}(u,v)=u+v\ .\,\!$

$I_{{\mathfrak {M}}_{2}}(\mathrm {F_{0}^{2}} )\ =\ \{<\!x,\ y\!>:\ x<y\}\ .\,\!$

We can reuse the same variable assignment from above, namely $\mathrm {s} \ :\,\!$

$\mathrm {s} (x_{0})\ =\ 0\ .\,\!$

$\mathrm {s} (y_{0})\ =\ 1\ .\,\!$

$\mathrm {s} (z_{0})\ =\ 2\ .\,\!$

Example of extended varable assignment

On the Models page, we listed the following goals for our defintions.

$f(a,b)\ {\mbox{resolves to}}\ 1\ \mathrm {in} \ {\mathfrak {M}}_{2}\ .\,\!$

This does not require our definition of truth or the definition of satisfaction; it is simply requires evaluating the exended variable assignment. We have for any $\mathrm {s} \,\!$ on defined on $I_{\mathfrak {M}}\,\!$:

${\overline {\mathrm {s} }}(f(a,b))\ =\ I_{\mathfrak {M}}(f)\,(\ {\overline {\mathrm {s} }}(a),\,{\overline {\mathrm {s} }}(b)\ )\ =\ {\mathfrak {f}}_{0}^{2}(\ {\overline {\mathrm {s} }}(a),\,{\overline {\mathrm {s} }}(b)\ )\,\!$

$=\ {\mathfrak {f}}_{0}^{2}(\ I_{\mathfrak {M}}(a),\,I_{\mathfrak {M}}(b)\ )\ =\ {\mathfrak {f}}_{0}^{2}(0,\,1)\,\!$

$=\ 0+1\ =\ 1\ .\,\!$

Example results without quantifiers

We also listed the following goal on the Models page.

$(9)\quad \mathrm {F} (a,b)\ {\mbox{and}}\ \mathrm {F} (b,c)\ {\mbox{are True in}}\ {\mathfrak {M}}_{2}\ .\,\!$

$(10)\quad \mathrm {F} (c,b)\ {\mbox{and}}\ \mathrm {F} (a,a)\ {\mbox{are False in}}\ {\mathfrak {M}}_{2}\ .\,\!$

First we note that:

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \vDash \mathrm {F} (a,b)\ \ {\mbox{because}}\ <\!{\overline {\mathrm {s} }}(a),\,{\overline {\mathrm {s} }}(b)\!>\ =\ <\!0,\,1\!>\ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ \,\!$

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \vDash \mathrm {F} (b,c)\ \ {\mbox{because}}\ <\!{\overline {\mathrm {s} }}(b),\,{\overline {\mathrm {s} }}(c)\!>\ =\ <\!1,\,2\!>\ \in \ I_{\mathfrak {M}}(\mathrm {F} )\,\!$

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \not \vDash \mathrm {F} (c,b)\ \ {\mbox{because}}\ <\!{\overline {\mathrm {s} }}(c),\,{\overline {\mathrm {s} }}(b)\!>\ =\ <\!2,\,1\!>\ \notin \ I_{\mathfrak {M}}(\mathrm {F} )\,\!$

$<\!{\mathfrak {M}},\ \mathrm {s} \!>\ \not \vDash \mathrm {F} (a,a)\ \ {\mbox{because}}\ <\!{\overline {\mathrm {s} }}(a),\,{\overline {\mathrm {s} }}(a)\!>\ =\ <\!0,\,0\!>\ \notin \ I_{\mathfrak {M}}(\mathrm {F} )\ .\,\!$

Indeed:

$<\!0,\,1\!>\ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ \ {\mbox{because}}\ \ 0<1\,\!$

$<\!1,\,2\!>\ \in \ I_{\mathfrak {M}}(\mathrm {F} )\ \ {\mbox{because}}\ \ 1<2\,\!$

$<\!2,\,1\!>\ \notin \ I_{\mathfrak {M}}(\mathrm {F} )\ \ {\mbox{because}}\ \ 2\not <1\,\!$

$<\!0,\,0\!>\ \notin \ I_{\mathfrak {M}}(\mathrm {F} )\ \ {\mbox{because}}\ \ 0\not <0\ .\,\!$

Because the formulae of (9) and (10) are sentences,

$<\!{\mathfrak {M}}\!>\ \vDash \mathrm {F} (a,b)\ .\,\!$

$<\!{\mathfrak {M}}\!>\ \vDash \mathrm {F} (b,c)\ .\,\!$

$<\!{\mathfrak {M}}\!>\ \not \vDash \mathrm {F} (c,b)\ .\,\!$

$<\!{\mathfrak {M}}\!>\ \not \vDash \mathrm {F} (a,a)\ .\,\!$

Applying the definition of truth, we find the goals of (9) and (10) achieved. The sentences of (9) are true and those of (10) are false.

Example results with quantifiers

In addition, we listed the following goal on the Models page.

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

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

Corresponding to (11):

$(13)\quad <\!{\mathfrak {M_{2}}},\ \mathrm {s} \!>\ \vDash \forall x\,\exists y\,\mathrm {F} (x,y)\,\!$

is true if and only if, for each i a member of the domain, the following is true of at least one j a member of the domain:

$<\!{\mathfrak {M_{2}}},\ \mathrm {s} [x\!:\,i,x\!:\,j]\!>\ \vDash \mathrm {F} (x,y)\ .\,\!$

But $\mathrm {F_{0}^{2}} \,\!$ was assigned the less then relation. Thus the preceeding holds if and only if, for every member of the domain, there is a larger member of the domain. Given that the domain is $\{0,1,2,...\},\,\!$ this is obviously true. Thus, (13) is true. Given that the formula of (11) and (12) is a sentence, we find the goal expressed as (11) to be met.

Corresponding to (12):

$(14)\quad <\!{\mathfrak {M_{2}}},\ \mathrm {s} \!>\ \vDash \forall x\,\exists y\,\mathrm {F} (y,x)\,\!$

is true if and only if, for each i a member of the domain, the following is true of at least one j a member of the domain:

$<\!{\mathfrak {M_{2}}},\ \mathrm {s} [x\!:\,i,x\!:\,j]\!>\ \vDash \mathrm {F} (y,x)\ .\,\!$

This holds if and only if, for every member of the domain, there is a smaller member of the domain. But there is no member of the domain smaller than 0. Thus (14) is false. The formula of (12) and (14) fails to be satisfied by ${\mathfrak {M_{2}}}\,\!$ with variable assignment $\mathrm {s} \,\!$. The formula of (12) and (14) is a sentence, so it fails to be satisfied by ${\mathfrak {M_{2}}}\,\!$ with any variable assignment. The formula (a sentence) of (12) and (14) is false, and so the goal of (12) is met.