ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 27
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.3. Languages, Models, and Satisfaction (cont.)
|
| The next proposition duplicates Lemma 1.2.9. There is no change in the proof.
|
| 1.3.11. Proposition. (Lindenbaum's Theorem).
|
| Any consistent set of sentences of $L$ can
| be extended to a maximal consistent set of
| sentences of $L$.
|
| We now come to the key definition of this section. In fact, the following
| definition of satisfaction is the cornerstone of model theory. We first
| give the motivation for the definition in a few remarks. If we compare
| the models of Section 1.2 and the models discussed here, we see that
| with the former we were only concerned with whether a statement is
| true or false in it, while here the situation is more complicated
| because the sentences of $L$ say something about the individual
| elements of the model. The whole question of the (first-order)
| truths or falsities of a possible world (i.e., model) is just not
| a simple problem. For instance, there is no way to decide whether a
| given sentence of $L$ = {+, ·, S, 0} is true or false in the standard
| model <N, +, ·, S, 0> of arithmetic (where S is the successor function).
| Whereas we have already seen in Section 1.2 that there is such a decision
| procedure for every model for $S$ and for every sentence of $S$. To define
| the notion:
|
| the sentence !s! is true in the model $A$,
|
| we have first to break up !s! into smaller parts and to examine each part.
| If !s! is ~p or if !s! is p & q, then we see that the truth or falsity of !s!
| in $A$ follows once we know the truth or falsity of p and q in $A$. If, on the
| other hand, !s! is (`A`x)p, then the same method for deciding the truth of !s!
| breaks down as p may not be a sentence and it would be meaningless to ask if
| p is true or false in $A$.
|
| The free variable x in p is supposed to range over the elements
| of A. For each particular a in A it is meaningful to ask whether:
|
| the formula p is true in $A$ if p is talking about a.
|
| If for each a in A the answer to this question is yes, then we can
| say that !s! is true in $A$. If there exists an a in A so that the
| answer is no, then we can say that !s! is false in $A$. But in order
| to answer the above question, even for a fixed element of A, we shall
| run into the same difficulty if p happens to be (`A`y)q. Then we are
| led naturally to ask whether:
|
| q is true in $A$ if q is talking about a pair of elements a and b in A.
|
| It takes but a very small step before we see
| that the crucial question is the following:
|
| Given a formula p(v_0 ... v_k) and a sequence x_0, ..., x_k in A,
| what does it mean to say that p is true in $A$ if the variables
| v_0, ..., v_k are taken to be x_0, ..., x_k?
|
| Our plan is to give an answer to this question first for every atomic formula
| q(v_0 ... v_k) and all elements x_0, ..., x_k. Then, by an inductive procedure
| based on our inductive definition of a formula (1.3.1-1.3.3), we shall give an
| answer for all formulas p(v_0 ... v_k) and elements x_0, ..., x_k.
|
| There is still one difficulty with our plan: If all the free variables
| of a formula p are among v_0, ..., v_k, it does not follow that all the
| free variables of every subformula of p are among v_0, ..., v_k. For a
| quantifier make a free variable bound. This will cause trouble in the
| induction part of our plan. To overcome this difficulty we observe that
| the follwoing is true. If all the variables, free or bound, of a formula
| p are among v_0, ..., v_m, then all the variables of every subformula of p
| are also among v_0, ..., v_m. So we shall modify our plan thus: First, we
| answer the question for all atomic formulas q(v_0 ... v_m) and all elements
| x_0, ..., x_m. Then by an inductive procedure we answer the question for
| all formulas p such that all its 'free and bound' variables are among
| v_0, ..., v_m, and all elements x_0, ..., x_m. Finally we 'prove'
| that the answer to the question for a formula p(v_0 ... v_k) and
| elements x_0, ..., x_m, k =< m, depends only on the elements
| x_0, ..., x_k corresponding to the 'free' variables of p,
| so that the values of x_(p+1), ..., x_m are irrelevant.
|
| Chang & Keisler, 'Model Theory', pages 26-27.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤