ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 39
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.5. Elimination of Quantifiers
|
| Each model $A$ of a theory T gives rise to a complete theory, namely
| the set of all sentences holding in $A$, which is an extension of T.
| For this reason it is important to know something about the complete
| extensions of a theory. In a few fortunate cases, it is possible to
| give a simple description of all the complete extensions of a theory
| by using the method of elimination of quantifiers.
|
| This method applies only to very special theories. Moreover, each time the
| method is applied to a new theory we must start from scratch in the proofs,
| because there are few opportunities to use general theorems about models.
| On the other hand, the method is extremely valuable when we want to beat
| a particular theory into the ground. When it can be carried out, the
| method of elimination of quantifiers gives a tremendous amount of
| information about a theory. For instance, it tells us about the
| behavior of all formulas, as well as all sentences, relative to
| the theory. Usually it also gives a uniform way of deciding
| whether or not a sentence belongs to the theory; in other
| words, it gives a proof that the theory is decidable.
|
| The question of the decidability of a theory lies outside the scope of this book,
| since it is not usually considered model theory. However, it is a very important
| question, and in fact the most striking applications of the method of elimination
| of quantifiers are to show that certain theories are decidable. The method is
| also valuable as a source of examples of thoroughly understood theories, which
| are useful for testing conjectures and for illustrating results. The method
| may be thought of as a direct attack on a theory. Later on we shall learn
| of several more indirect attacks on theories, which work more often but
| give less information in particualar cases.
|
| Beside describing the method, we need some more notation. In Section 1.3,
| we introduced the notion of a sentence p being a consequence of a set !S! of
| sentences, in symbols !S! |= p. What meaning shall we give to !S! |= p if p
| is a formula? We shall say that a formula p(v_0 ... v_n) is a 'consequence'
| of !S!, symbolically !S! |= p, if and only if for every model $A$ of !S! and
| every sequence a_0, ..., a_n in A, the sequence a_0, ..., a_n satisfies p.
| It follows that the 'formula' p(v_0 ... v_n) is a consequence of !S! iff
| the 'sentence' (`A`v_0 ... v_n) p(v_0 ... v_n) is a consequence of !S!.
| We say that two formulas p, q are !S!-'equivalent' iff !S! |= p <=> q.
|
| In general, the method of elimination of quantifiers is as follows:
| First, depending on the theory T, we pick out an appropriate set of
| formulas, called 'basic formulas'. By a 'Boolean combination' of
| basic formulas we mean a formula obtained from basic formulas by
| repeated application of the connectives ~ and &. The main result
| to be proved is that 'every formula is T-equivalent to a Boolean
| combination of basic formulas'. The key step in the proof is
| the step where we "eliminate quantifiers". In fact, we may
| state at once a simple but general lemma which shows why
| the name "elimination of quantifiers" is given to the
| method (the name is due to Tarski, 1935).
|
| 1.5.1. Lemma. Let T be a theory and let !S! be a set of formulas,
| called basic formulas. In order to show that every formula
| is T-equivalent to a Boolean combination of basic formulas,
| it is sufficient to show the following:
|
| 1. Every atomic formula is T-equivalent to
| a Boolean combination of basic formulas.
|
| 2. If r is a Boolean combination of basic formulas, then
| (`E`v_m)r is T-equivalent to a Boolean combination of
| basic formulas.
|
| Proof. Let Q be the set of all formulas which are
| T-equivalent to a boolean combination of
| basic formulas. We show by induction
| that every formula p belongs to Q.
|
| If p is an atomic formula,
| then p is in Q by (1).
|
| If p is ~q, where q is in Q,
| it is obvious that p is in Q.
|
| Similarly, if p is q_1 & q_2,
| where q_1 and q_2 are in Q,
| then p is in Q.
|
| If p is (`E`v_m)q, where q is in Q,
| then q is T-equivalent to a Boolean combination r of basic formulas.
| Moreover, p is T-equivalent to (`E`v_m)r. By (2), (`E`v_m)r is in Q,
| so p is in Q. -|
|
| Chang & Keisler, 'Model Theory', pages 49-50.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤