ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 29
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.3. Languages, Models, and Satisfaction (cont.)
|
| Having finished our definition, our first task
| is to prove the proposition that the relation:
|
| $A$ |= p(v_0 ... v_k) [x_0 ... x_m]
|
| depends only on x_0, ..., x_k, where k < m.
| This is the last part of the plan we have
| outlined.
|
| 1.3.16. Proposition.
|
| 1. Let t(v_0 ... v_k) be a term and let
| x_0, ..., x_m and y_0, ..., y_n be two
| sequences such that k =< m and k =< n,
| and x_i = y_i whenever v_i is a free
| variable of t.
|
| Then t[x_0 ... x_m] = t[y_0 ... y_n].
|
| 2. Let p be a formula all of whose free and
| bound variables are among v_0, ..., v_k
| and let x_0, ..., x_m and y_0, ..., y_n
| be two sequences with k =< m and k =< n,
| and x_i = y_i whenever v_i is a free
| variable of p.
|
| Then $A$ |= p[x_0 ... x_m]
|
| iff $A$ |= p[y_0 ... y_n].
|
| Remark. Proposition 1.3.16 shows that the value of a term t at x_0, ..., x_m
| and whether a formula p is satisfied or not by a sequence x_0, ..., x_m
| 'depend only' on those values of x_i for which v_i is a free variable,
| and are 'independent' of the other values of the sequence as well as
| the length of the sequence. The length m of the sequence must be
| high enough to cover all the free and bound variables of t and p
| in order for the expressions t[x_0 ... x_m], $A$ |= p[x_0 ... x_m]
| to be defined at all. We can now immediately infer that if !s! is
| a sentence, then $A$ |= !s![x_0 ... x_m] is entirely independent of
| the sequence x_0, ..., x_m. The importance of the above proposition
| is that it allows us to make the following definition:
|
| 1.3.17. Let p(v_0 ... v_k) be a formula all of whose free and bound variables
| are among v_0, ..., v_m, k =< m. Let x_0, ..., x_k be a sequence of
| elements of A. We say that p is 'satisfied' in $A$ by x_0, ..., x_k,
|
| $A$ |= p[x_0 ... x_k],
|
| if and only if
|
| p is satisfied in $A$ by x_0, ..., x_k, ..., x_m for
| some (or, equivalently, every) x_(k+1), ..., x_m.
|
| Let p be a sentence all of whose bound variables are among
| v_0, ..., v_m. We say that $A$ 'satisfies' p, in symbols
| $A$ |= p, if and only if p is satisfied in $A$ by some
| (or, equivalently, every) sequence x_0, ..., x_m.
|
| The proof of Proposition 1.3.16 is straightforward but tedious.
| We shall sketch it here as a first example of an inductive proof
| on the "complexity" of formulas. We shall often omit similar easy
| inductive proofs in the future.
|
| Proof of Proposition 1.3.16. [C&K, pages 30-31].
|
| Chang & Keisler, 'Model Theory', pages 28-31.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤