ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 28
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.3. Languages, Models, and Satisfaction (cont.)
|
| We are now ready for the formal definition. The crucial notion to be defined
| is the following: Let p be any formula of $L$, all of whose free and bound
| variables are among v_0, ..., v_m, and let x_0, ..., x_m be any sequence
| of elements of A. We define the predicate:
|
| 1.3.12. p is 'satisfied by' the sequence x_0, ..., x_m in $A$,
|
| or
|
| x_0, ..., x_m 'satisfies' p in $A$.
|
| The definition proceeds in three stages (compare with 1.3.1 - 1.3.3).
|
| Let $A$ be a fixed model for $L$.
|
| 1.3.13. The 'value' of a term t(v_0 ... v_m) at x_0, ..., x_m is
| defined as follows (we let t[x_0 ... x_m] denote this value):
|
| 1. If t = v_i,
|
| then t[x_0 ... x_m] = x_i.
|
| 2. If t is a constant symbol c,
|
| then t[x_0 ... x_m] is the interpretation of c in $A$.
|
| 3. If t = F(t_1 ... t_n), where F is an n-placed function symbol,
|
| then t[x_0 ... x_m] = G(t_1 [x_0 ... x_m] ... t_n [x_0 ... x_m]),
|
| where G is the interpretation of F in $A$.
|
| 1.3.14. 1. Suppose p(v_0 ... v_m) is the atomic formula t_1 = t_2,
|
| where t_1 (v_0 ... v_m) and t_2 (v_0 ... v_m) are terms.
|
| Then x_0, ..., x_m 'satisfies' p
|
| if and only if
|
| t_1 [x_0 ... x_m] = t_2 [x_0 ... x_m].
|
| 2. Suppose p(v_0 ... v_m) is the atomic formula P(t_1 ... t_n),
|
| where P is an n-placed relation symbol
|
| and t_1 (v_0 ... v_m), ..., t_n (v_0 ... v_m) are terms.
|
| Then x_0, ..., x_m 'satisfies' p
|
| if and only if
|
| R(t_1 [x_0 ... x_m] ... t_n [x_0 ... x_m]),
|
| where R is the interpretation of P in $A$.
|
| For brevity, we write:
|
| $A$ |= p[x_0 ... x_m]
|
| for: x_0, ..., x_m satisfies p in $A$.
|
| Thus 1.3.14 can also be formulated as:
|
| 1.3.14. 1. $A$ |= (t_1 = t_2) [x_0 ... x_m]
|
| if and only if
|
| t_1 [x_0 ... x_m] = t_2 [x_0 ... x_m].
|
| 2. $A$ |= P(t_1 ... t_n) [x_0 ... x_m]
|
| if and only if
|
| R(t_1 [x_0 ... x_m] ... t_n [x_0 ... x_m]).
|
| 1.3.15. Suppose that p is a formula of $L$
| and all free and bound variables
| of p are among v_0, ..., v_m.
|
| 1. If p is r_1 & r_2
|
| then $A$ |= p[x_0 ... x_m]
|
| if and only if
|
| both $A$ |= r_1 [x_0 ... x_m]
|
| and $A$ |= r_2 [x_0 ... x_m].
|
| 2. If p is ~r
|
| then $A$ |= p[x_0 ... x_m]
|
| if and only if
|
| not $A$ |= r[x_0 ... x_m].
|
| 3. If p is (`A`v_i) q
|
| where i =< m,
|
| then $A$ |= p[x_0 ... x_m]
|
| if and only if
|
| for every x in A,
|
| $A$ |= q[x_0 ... x_(i-1) x x_(i+1) ... x_m].
|
| Our definition of 1.3.12 is now completed. As simple exercises,
| the reader should check that the abbreviations v, =>, <=>, `E`
| have their usual meanings.
|
| In particular:
|
| If p is (`E`v_i) q
|
| where i =< m,
|
| then $A$ |= p[x_0 ... x_m]
|
| if and only if
|
| there exists x in A such that
|
| $A$ |= q[x_0 ... x_(i-1) x x_(i+1) ... x_m].
|
| More important, the reader should realize that we can formulate
| a precise definition of t[x_0 ... x_m] and $A$ |= p[x_0 ... x_m]
| in set theory, based upon 1.3.13 - 1.3.15.
|
| Chang & Keisler, 'Model Theory', pages 27-28.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤