User:JMRyan/New Page1

From Wikibooks, open books for an open world
Jump to: navigation, search
← Satisfaction ↑ Predicate Logic End



Truth[edit]

Truth in a model[edit]

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[edit]

A finite model[edit]

The example model[edit]

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

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

\mathrm{s}(x_0)\ =\ 0\ .\,\!
\mathrm{s}(y_0)\ =\ 1\ .\,\!
\mathrm{s}(z_0)\ =\ 2\ .\,\!

Example results[edit]

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[edit]

The example model[edit]

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^2_0)\ =\ \mathfrak{f}^2_0\ \mbox{such that}\ \mathfrak{f}^2_0(u, v) = u + v\ .\,\!
I_{\mathfrak{M}_2}(\mathrm{F^2_0})\ =\ \{<\!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[edit]

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}^2_0(\ \overline{\mathrm{s}}(a),\, \overline{\mathrm{s}}(b)\ )\,\!
=\ \mathfrak{f}^2_0(\ I_{\mathfrak{M}}(a),\, I_{\mathfrak{M}}(b)\ )
\ =\ \mathfrak{f}^2_0(0,\, 1)\,\!
=\ 0 + 1\ =\ 1\ .\,\!

Example results without quantifiers[edit]

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[edit]

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^2_0}\,\! 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.