Jump to content

User:JMRyan/New Page1

From Wikibooks, open books for an open world
← Satisfaction ↑ Predicate Logic End



Truth

[edit | edit source]

Truth in a model

[edit | edit source]

We have defined satisfaction in a model with a variable assignment. We have expressed formula being satisfied by model with variable assignment as:

Now we can also say that a formula is satisfied my model (not limited to a specific variable assignment) if and only if is satisfied by with every variable assignment. Thus

if and only if

If no free variables occur in (thatis, if is a sentence), then is true in model .

Variable assignments allow us to deal with free variables when doing the semantic analysis of a formula. For two variable assignments, and , satisfaction by differs from satisfaction by 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:

is true in if and only if there is a variable assignment such that
is true in if and only if, for every variable assignment

The latter is just a notational variant of:

is true in if and only if

Examples

[edit | edit source]

A finite model

[edit | edit source]

The example model

[edit | edit source]

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

For the model

For the variable assignment

Example results

[edit | edit source]

We noted the following results:

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 .

Applying our definition of truth, we get:

.

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

An infinite model

[edit | edit source]

The example model

[edit | edit source]

On Models page, we also considered an infinite model

We can reuse the same variable assignment from above, namely

Example of extended varable assignment

[edit | edit source]

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

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 on defined on :

Example results without quantifiers

[edit | edit source]

We also listed the following goal on the Models page.

First we note that:

Indeed:

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

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

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

Corresponding to (11):

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:

But 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 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):

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:

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 with variable assignment . The formula of (12) and (14) is a sentence, so it fails to be satisfied by with any variable assignment. The formula (a sentence) of (12) and (14) is false, and so the goal of (12) is met.