ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 30
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.3. Languages, Models, and Satisfaction (cont.)
|
| We shall state one more elementary proposition which
| deals with the behavior of the satisfaction relation
| under the substitution of variables by terms. We omit
| the proof, which is another tedious but straightforward
| induction.
|
| 1.3.18. Proposition.
|
| Let p(v_0 ... v_k) be a formula and let
| t_0 (v_0 ... v_k), ..., t_k (v_0 ... v_k)
| be terms. Suppose that no variable occurring
| in any of the terms t_0, ..., t_k occurs bound in p.
|
| Let x_0, ..., x_k be a sequence of elements of A and
| let p(t_0 ... t_k) be the formula obtained from p by
| substituting t_i for v_i (i = 0, ..., k).
|
| Then:
|
| $A$ |= p(t_0 ... t_k) [x_0 ... x_k]
|
| if and only if
|
| $A$ |= p[t_0 [x_0 ... x_k] ... t_k [x_0 ... x_k]].
|
| We have now completed the project started several paragraphs back.
| Namely, we say of a sentence !s! that:
|
| !s! is true in $A$
|
| iff and only if
|
| $A$ |= !s![x_0 ... x_m]
|
| for some (or for every) sequence x_0, ..., x_m of A.
|
| We use the special notation $A$ |= !s! to denote that !s! is true in A.
| This last phrase is equivalent to each of the following phrases:
|
| !s! holds in $A$
|
| $A$ satisfies !s!
|
| $A$ is a model of !s!
|
| !s! is satisfied in $A$
|
| When it is not the case that !s! holds in $A$, we say that
| !s! is 'false' in $A$, or that !s! 'fails' in $A$, or that
| $A$ is a model of ~!s!.
|
| Given a set !S! of sentences, we say $A$ is a 'model' of !S!
| iff $A$ is a model of each !s! in !S!, and it is convenient
| to use the notation $A$ |= !S! for this notion.
|
| A sentence !s! that holds in every model for $L$ is called 'valid'.
| A sentence, or a set of sentences, is 'satisfiable' if and only if
| it has at least one model. Whence, !s! is satisfiable if and only
| if ~!s! is 'refutable'.
|
| |= !s! denotes that !s! is a valid sentence.
|
| A sentence !t! is a 'consequence' of another sentence !s!,
| in symbols !s! |= !t!, iff every model of !s! is a model of !t!.
|
| A sentence !t! is a 'consequence' of a set of sentences !S!,
| in symbols !S! |= !t!, iff every model of !S! is a model of !t!.
|
| It follows that:
|
| !S! |_| {!s!} |= !t!
|
| if and only if
|
| !S! |= !s! => !t!
|
| Two models $A$ and $B$ for $L$ are 'elementarily equivalent' iff
| every sentence that is true in $A$ is true in $B$ and vice versa.
| We express this relationship between models by !=!. It is easy to
| see that !=! is indeed an equivalence relation. The symbol we have
| chosen to denote elementary equivalence is exactly the same [in the
| original text] as the identity symbol for the language $L$. However,
| no confusion can ever arise because one is a relation between models
| for $L$ and the other is a relation between terms of $L$. If the
| context is clear, 'equivalent' shall mean elementarily equivalent.
|
| 1.3.19. Proposition.
|
| If $A$ ~=~ $B$
|
| then $A$ !=! $B$.
|
| In case $A$ is finite, then the converse is also true.
|
| Chang & Keisler, 'Model Theory', pages 31-32.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤