Fundamentals of Model Theory William Weiss and Cherie D'Mello Department of Mathematics University of Toronto
c 1997 W.Weiss and C. D'Mello
1
Introduction Model Theory is the part of mathematics which shows how to apply logic to the study of structures in pure mathematics. On the one hand it is the ultimate abstraction on the other, it has immediate applications to every-day mathematics. The fundamental tenet of Model Theory is that mathematical truth, like all truth, is relative. A statement may be true or false, depending on how and where it is interpreted. This isn't necessarily due to mathematics itself, but is a consequence of the language that we use to express mathematical ideas. What at rst seems like a deciency in our language, can actually be shaped into a powerful tool for understanding mathematics. This book provides an introduction to Model Theory which can be used as a text for a reading course or a summer project at the senior undergraduate or graduate level. It is also a primer which will give someone a self contained overview of the subject, before diving into one of the more encyclopedic standard graduate texts. Any reader who is familiar with the cardinality of a set and the algebraic closure of a eld can proceed without worry. Many readers will have some acquaintance with elementary logic, but this is not absolutely required, since all necessary concepts from logic are reviewed in Chapter 0. Chapter 1 gives the motivating examples and we recommend that you read it rst, before diving into the more technical aspects of Chapter 0. Chapters 2 and 3 are selections of some of the most important techniques in Model Theory. The remaining chapters investigate the relationship between Model Theory and the algebra of the real and complex numbers. Thirty exercises develop familiarity with the denitions and consolidate understanding of the main proof techniques. Throughout the book we present applications which cannot easily be found elsewhere in such detail. Some are chosen for their value in other areas of mathematics: Ramsey's Theorem, the Tarski-Seidenberg Theorem. Some are chosen for their immediate appeal to every mathematician: existence of innitesimals for calculus, graph colouring on the plane. And some, like Hilbert's Seventeenth Problem, are chosen because of how amazing it is that logic can play an important role in the solution of a problem from high school algebra. In each case, the derivation is shorter than any which tries to avoid logic. More importantly, the methods of Model Theory display clearly the structure of the main ideas of the proofs, showing how theorems of logic combine with theorems from other areas of mathematics to produce stunning results. The theorems here are all are more than thirty years old and due in great part to the cofounders of the subject, Abraham Robinson and Alfred Tarski. However, we have not attempted to give a history. When we attach a name to a theorem, it is simply because that is what mathematical logicians popularly call it. The bibliography contains a number of texts that were helpful in the preparation of this manuscript. They could serve as avenues of further study and in addition, they contain many other references and historical notes. The more recent titles were added to show the reader where the subject is moving today. All are worth a look. This book began life as notes for William Weiss's graduate course at the University of Toronto. The notes were revised and expanded by Cherie D'Mello and
2
William Weiss, based upon suggestions from several graduate students. The electronic version of this book may be downloaded and further modied by anyone for the purpose of learning, provided this paragraph is included in its entirety and so long as no part of this book is sold for prot.
Contents Chapter 0. Models, Truth and Satisfaction Formulas, Sentences, Theories and Axioms Prenex Normal Form Chapter 1. Notation and Examples Chapter 2. Compactness and Elementary Submodels Compactness Theorem Isomorphisms, elementary equivalence and complete theories Elementary Chain Theorem Lowenheim-Skolem Theorems The L os-Vaught Test Every complex one-to-one polynomial map is onto Chapter 3. Diagrams and Embeddings Diagram Lemmas Every planar graph can be four coloured Ramsey's Theorem The Leibniz Principle and innitesimals Robinson Consistency Theorem Craig Interpolation Theorem Chapter 4. Model Completeness Robinson's Theorem on existentially complete theories Lindstrom's Test Hilbert's Nullstellensatz Chapter 5. The Seventeenth Problem Positive denite rational functions are the sums of squares Chapter 6. Submodel Completeness Elimination of quantiers The Tarski-Seidenberg Theorem Chapter 7. Model Completions Almost universal theories Saturated models Blum's Test Bibliography Index 3
4 4 9 11 14 14 15 16 19 21 23 24 25 25 26 26 27 31 32 32 35 38 39 39 45 45 49 50 52 54 55 61 62
CHAPTER 0
Models, Truth and Satisfaction We will use the following symbols: logical symbols: { the connectives ^ ,_ , : , ! , $ called \and", \or", \not", \implies" and \i" respectively { the quantiers 8 , 9 called \for all" and \there exists" { an innite collection of variables indexed by the natural numbers N v0 ,v1 , v2 , : : : { the two parentheses ), ( { the symbol = which is the usual \equal sign" constant symbols : often denoted by the letter c with subscripts function symbols : often denoted by the letter F with subscripts each function symbol is an m-placed function symbol for some natural number m 1 relation symbols : often denoted by the letter R with subscripts each relational symbol is an n-placed relation symbol for some natural number n 1. We now dene terms and formulas. Definition 1. A term is dened as follows: (1) a variable is a term (2) a constant symbol is a term (3) if F is an m-placed function symbol and t1 : : : tm are terms, then F (t1 : : : tm ) is a term. (4) a string of symbols is a term if and only if it can be shown to be a term by a nite number of applications of (1), (2) and (3). Remark. This is a recursive denition. Definition 2. A formula is dened as follows : (1) if t1 and t2 are terms, then t1 = t2 is a formula. (2) if R is an n-placed relation symbol and t1 : : : tn are terms, then R(t1 : : : tn ) is a formula. (3) if ' is a formula, then (:') is a formula (4) if ' and are formulas then so are (' ^ ), (' _ ), (' ! ) and (' $ ) (5) if vi is a variable and ' is a formula, then (9vi )' and (8vi )' are formulas (6) a string of symbols is a formula if and only if it can be shown to be a formula by a nite number of applications of (1), (2), (3), (4) and (5). Remark. This is another recursive denition. :' is called the negation of '. ' ^ is called the conjunction of ' and . ' _ is called the disjunction of ' and . Definition 3. A subformula of a formula ' is dened as follows: 4
0. MODELS, TRUTH AND SATISFACTION
5
(1) ' is a subformula of ' (2) if (:) is a subformula of ' then so is (3) if any one of ( ^ ), ( _ ), ( ! ) or ( $ ) is a subformula of ' , then so are both and (4) if either (9vi ) or (8vi ) is a subformula of ' for some natural number i , then is also a subformula of ' (5) A string of symbols is a subformula of ', if and only if it can be shown to be such by a nite number of applications of (1), (2), (3) and (4). Definition 4. A variable vi is said to occur bound in a formula ' i for some subformula of ' either (9vi ) or (8vi ) is a subformula of '. In this case each occurance of vi in is said to be a bound occurance of vi . Other occurances of vi which do not occur bound in ' are said to be free. Exercise 1. Using the previous denitions as a guide, dene the substitution of a term t for a variable vi in a formula '. Example 1. F2 (v3 v4 ) is a term. ((8v3 )(v3 = v3 ^ v0 = v1 ) _ (9v0 )v0 = v0 ) is a formula. In this formula the variable v3 occurs bound, the variable v1 occurs free, but the variable v0 occurs both bound and free. Exercise 2. Reconsider Exercise 1 in light of substituting the above term for v0 in the formula. Definition 5. A language L is a set consisting of all the logical symbols with perhaps some constant, function and/or relational symbols included. It is understood that the formulas of L are made up from this set in the manner prescribed above. Note that all the formulas of L are uniquely described by listing only the constant, function and relation symbols of L. We use t(v0 : : : vk ) to denote a term t all of whose variables occur among v0 : : : vk . We use '(v0 : : : vk ) to denote a formula ' all of whose free variables occur among v0 : : : vk . Example 2. These would be formulas of any language : For any variable vi : vi = vi for any term t(v0 : : : vk ) and other terms t1 and t2 : t1 = t2 ! t(v0 : : : vi;1 t1 vi+1 : : : vk ) = t(v0 : : : vi;1 t2 vi+1 : : : vk ) for any formula '(v0 : : : vk ) and terms t1 and t2 : t1 = t2 ! '(v0 : : : vi;1 t1 vi+1 : : : vk ) $ '(v0 : : : vi;1 t2 vi+1 : : : vk ) Note the simple way we denote the substitution of t1 for vi . Definition 6. A model (or structure) A for a language L is an ordered pair hA Ii where A is a set and I is an interpretation function with domain the set of all constant, function and relation symbols of L such that: 1. if c is a constant symbol, then I (c) 2 A I (c) is called a constant
0. MODELS, TRUTH AND SATISFACTION
6
2. if F is an m-placed function symbol, then I (F ) is an m-placed function on
A
3. if R is an n-placed relation symbol, then I (R) is an n-placed relation on A. A is called the universe of the model A. We generally denote models with Gothic letters and their universes with the corresponding Latin letters in boldface. One set may be involved as a universe with many dierent interpretation functions of the language L. The model is both the universe and the interpretation function. Remark. The importance of Model Theory lies in the observation that mathematical objects can be cast as models for a language. For instance, the real numbers with the usual ordering < and the usual arithmetic operations, addition + and multiplication along with the special numbers 0 and 1 can be described as a model. Let L contain one two-placed (i.e. binary) relation symbol R0 , two two-placed function symbols F1 and F2 and two constant symbols c0 and c1 . We build a model by letting the universe A be the set of real numbers. The interpretation function I will map R0 to < , i.e. R0 will be interpreted as < . Similarly, I (F1 ) will be + , I (F2 ) will be , I (c0 ) will be 0 and I (c1 ) will be 1. So hA Ii is an example of a model. We now wish to show how to use formulas to express mathematical statements about elements of a model. We rst need to see how to interpret a term in a model. Definition 7. The value tx0 : : : xq ] of a term t(v0 : : : vq ) at x0 : : : xq in the model A is dened as follows: 1. if t is vi then tx0 xq ] is xi , 2. if t is the constant symbol c, then tx0 : : : xq ] is I (c), the interpretation of c in A, 3. if t is F (t1 : : : tm ) where F is an m-placed function symbol and t1 : : : tm are terms, then tx0 : : : xq ] is G(t1 x0 : : : xq ] : : : tm x0 : : : xq ]) where G is the m-placed function I (F ), the interpretation of F in A. Definition 8. Suppose A is a model for a language L. The sequence x0 : : : xq satis es the formula '(v0 : : : vq ) all of whose free and bound variables are among v0 : : : vq , in the model A, written A j= 'x0 : : : xq ] provided we have: 1. if '(v0 : : : vq ) is the formula t1 = t2 , then A j= t1 = t2 x0 : : : xq ] means that t1 x0 : : : xq ] equals t2 x0 : : : xq ], 2. if '(v0 : : : vq ) is the formula R(t1 : : : tn ) where R is an n-placed relation symbol, then A j= R(t1 : : : tn )x0 : : : xq ] means S (t1 x0 : : : xq ] : : : tn x0 : : : xq ]) where S is the n-placed relation I (R), the interpretation of R in A, 3. if ' is (:), then A j= 'x0 : : : xq ] means not A j= x0 : : : xq ], 4. if ' is ( ^ ), then A j= 'x0 : : : xq ] means both A j= x0 : : : xq ] and A j= x0 : : : xq ], 5. if ' is ( _ ) then A j= 'x0 : : : xq ] means either A j= x0 : : : xq ] or A j= x0 : : : xq ],
0. MODELS, TRUTH AND SATISFACTION
7
6. if ' is ( ! ) then A j= 'x0 : : : xq ] means that A j= x0 : : : xq ] implies A j= x0 : : : xq ], 7. if ' is ( $ ) then A j= 'x0 : : : xq ] means that A j= x0 : : : xq ] i A j= x0 : : : xq ], 8. if ' is 8vi , then A j= 'x0 : : : xq ] means for every x 2 A A j= x0 : : : xi;1 x xi+1 : : : xq ], 9. if ' is 9vi , then A j= 'x0 : : : xq ] means for some x 2 A A j= x0 : : : xi;1 x xi+1 : : : xq ]: Exercise 3. Each of the formulas of Example 2 is satised in any model A for any language L by any (long enough) sequence x0 x1 : : : xq of A. This is where you test your solution to Exercise 2. We now prove two lemmas which show that the preceeding concepts are welldened. In the rst one, we see that the value of a term only depends upon the values of the variables which actually occur in the term. In this lemma the equal sign = is used, not as a logical symbol in the formal sense, but in its usual sense to denote equality of mathematical objects | in this case, the values of terms, which are elements of the universe of a model. Lemma 1. Let A be a model for L and let t(v0 : : : vp ) be a term of L. Let x0 : : : xq and y0 : : : yr be sequences from A such that p q and p r, and let xi = yi whenever vi actually occurs in t(v0 : : : vp ). Then tx0 : : : xq ] = ty0 : : : yr ] . Proof. We use induction on the complexity of the term t. 1. If t is vi then xi = yi and so we have tx0 : : : xq ] = xi = yi = ty0 : : : yr ] since p q and p r: 2. If t is the constant symbol c, then tx0 : : : xq ] = I (c) = ty0 : : : yr ] where I (c) is the interpretation of c in A. 3. If t is F (t1 : : : tm) where F is an m-placed function symbol, t1 : : : tm are terms and I (F ) = G, then tx0 : : : xq ] = G(t1 x0 : : : xq ] : : : tm x0 : : : xq ]) and ty0 : : : yr ] = G(t1 y0 : : : yr ] : : : tm y0 : : : yr ]). By the induction hypothesis we have that ti x0 : : : xq ] = ti y0 : : : yr ] for 1 i m since t1 : : : tm have all their variables among fv0 : : : vp g. So we have tx0 : : : xq ] = ty0 : : : yr ]. In the next lemma the equal sign = is used in both senses | as a formal logical symbol in the formal language L and also to denote the usual equality of mathematical objects. This is common practice where the context allows the reader to distinguish the two usages of the same symbol. The lemma conrms that satisfaction of a formula depends only upon the values of its free variables.
0. MODELS, TRUTH AND SATISFACTION
8
Lemma 2. Let A be a model for L and ' a formula of L, all of whose free and bound variables occur among v0 : : : vp . Let x0 : : : xq and y0 : : : yr (q r p) be two sequences such that xi and yi are equal for all i such that vi occurs free in '. Then A j= 'x0 : : : xq ] i A j= 'y0 : : : yr ] Proof. Let A and L be as above. We prove the lemma by induction on the complexity of '. 1. If '(v0 : : : vp ) is the formula t1 = t2 , then we use Lemma 1 to get: A j= (t1 = t2 )x0 : : : xq ] i t1 x0 : : : xq ] = t2 x0 : : : xq ] i t1 y0 : : : yr ] = t2 y0 : : : yr ] i A j= (t1 = t2 )y0 : : : yr ]: 2. If '(v0 : : : vp ) is the formula R(t1 : : : tn ) where R is an n-placed relation symbol with interpretation S , then again by Lemma 1, we get: A j= R(t1 : : : tn )x0 : : : xq ] i S (t1 x0 : : : xq ] : : : tn x0 : : : xq ]) i S (t1 y0 : : : yr ] : : : tn y0 : : : yr ]) i A j= R(t1 : : : tn )y0 : : : yr ]: 3. If ' is (:), the inductive hypothesis gives that the lemma is true for . So, A j= 'x0 : : : xq ] i not A j= x0 : : : xq ] i not A j= y0 : : : yr ] i A j= 'y0 : : : yr ]: 4. If ' is ( ^ ), then using the inductive hypothesis on and we get A j= 'x0 : : : xq ] i both A j= x0 : : : xq ] and A j= x0 : : : xq ] i both A j= y0 : : : yr ] and A j= y0 : : : yr ] i A j= 'y0 : : : yr ]: 5. If ' is ( _ ) then A j= 'x0 : : : xq ] i either A j= x0 : : : xq ] or A j= x0 : : : xq ] i either A j= y0 : : : yr ] or A j= y0 : : : yr ] i A j= 'y0 : : : yr ]: 6. If ' is ( ! ) then A j= 'x0 : : : xq ] i A j= x0 : : : xq ] implies A j= x0 : : : xq ] i A j= y0 : : : yr ] implies A j= y0 : : : yr ] i A j= 'y0 : : : yr ]: 7. If ' is ( $ ) then A j= 'x0 : : : xq ] i we have A j= x0 : : : xq ] i A j= x0 : : : xq ] i we have A j= y0 : : : yr ] i A j= y0 : : : yr ] i A j= 'y0 : : : yr ]: 8. If ' is 8vi , then A j= 'x0 : : : xq ] i for every z 2 A A j= x0 : : : xi;1 z xi+1 : : : xq ] i for every z 2 A A j= y0 : : : yi;1 z yi+1 : : : yr ] i A j= 'y0 : : : yr ]: The inductive hypothesis uses the sequences x0 : : : xi;1 z xi+1 : : : xq and y0 : : : yi;1 z yi+1 : : : yr with the formula .
0. MODELS, TRUTH AND SATISFACTION
9
9. If ' is 9vi , then A j= 'x0 : : : xq ] i for some z 2 A A j= x0 : : : xi;1 z xi+1 : : : xq ] i for some z 2 A A j= y0 : : : yi;1 z yi+1 : : : yr ] i A j= 'y0 : : : yr ]: The inductive hypothesis uses the sequences x0 : : : xi;1 z xi+1 : : : xq and y0 : : : yi;1 z yi+1 : : : yr with the formula . Definition 9. A sentence is a formula with no free variables.
If ' is a sentence, we can write A j= ' without any mention of a sequence from
A since by the previous lemma, it doesn't matter which sequence from A we use.
In this case we say: A satis es ' or A is a model of ' or ' holds in A or ' is true in A If ' is a sentence of L, we write j= ' to mean that A j= ' for every model A for L. Intuitively then, j= ' means that ' is true under any relevant interpretation (model for L). Alternatively, no relevant example (model for L) is a counterexample to ' | so ' is true. Lemma 3. Let '(v0 : : : vq ) be a formula of the language L. There is another formula '0 (v0 : : : vq ) of L such that 1. '0 has exactly the same free and bound occurances of variables as '. 2. '0 can possibly contain :, ^ and 9 but no other connective or quanti er. 3. j= (8v0 ) : : : (8vq )(' $ '0 ) Exercise 4. Prove the above lemma by induction on the complexity of '. Definition 10. A formula ' is said to be in prenex normal form whenever
(1) no variable occuring in ' occurs both free and bound, (2) no bound variable occuring in ' is bound by more than one quantier, and (3) in the written order, all of the quantiers preceed all of the connectives. Remark. (3) is equivalent to saying that in the constructed order, all of the connective steps preceed all of the quantier steps. Lemma 4. Let '(v0 : : : vp ) be any formula of a language L. There is a formula ' of L which has the following properties: 1. ' is in prenex normal form 2. ' and ' have the same free occurances of variables, and 3. j= (8v0 ) : : : (8vp )(' $ ' ) Exercise 5. Prove this lemma by induction on the complexity of '. There is a notion of rank on prenex formulas | the number of alternations of quantiers. The usual formulas of elementary mathematics have prenex rank 0, i.e. no alternations of quantiers. For example: (8x)(8y)(2xy x2 + y2 ):
0. MODELS, TRUTH AND SATISFACTION
10
However, the ; denition of a limit of a function has prenex rank 2 and is much more dicult for students to comprehend at rst sight: 89 8x((0 < ^ 0 < jx ; aj < ) ! jF (x) ; Lj < ): A formula of prenex rank 4 would make any mathematician look twice.
CHAPTER 1
Notation and Examples Although the formal notation for formulas is precise, it can become cumbersome and dicult to read. Condent that the reader would be able, if necessary, to put formulas into their formal form, we will relax our formal behaviour. In particular, we will write formulas any way we want using appropriate symbols for variables, constant symbols, function and relation symbols. We will omit parentheses or add them for clarity. We will use binary function and relation symbols between the arguments rather than in front as is the usual case for \plus", \times" and \less than". Whenever a language L has only nitely many relation, function and constant symbols we often write, for example: L = f< R0 + F1 c0 c1 g omitting explicit mention of the logical symbols (including the innitely many variables) which are always in L. Correspondingly we may denote a model A for L as: < S0 + G1 a0 a1 i A = hA< where the interpretations of the symbols in the language L are given by I (<) = <, I (R0 ) = S0 , I (+) = + , I (F1 ) = G1 , I (c0 ) = a0 and I (c1 ) = a1 . < + 0 1i and Q = hQ < < + 0 1i, where R is the Example 3. R = hR< reals, Q the rationals , are models for the language L = f< + 0 1g. Here < is a binary relation symbol, + and are binary function symbols, 0 and 1 are constant symbols whereas <, + , , 0, 1 are the well known relations, arithmetic functions and constants. Similarly, C = hC + 0 1i, where C is the complex numbers, is a model for the language L = f+ 0 1g. Note the exceptions to the boldface convention for these popular sets. Example 4. Here L = f< + 0 1g, where < is a binary relation symbol, + and are binary function symbols and 0 and 1 are constant symbols. The following formulas are sentences. 1. (8x):(x < x) 2. (8x)(8y):(x < y ^ y < x) 3. (8x)(8y)(8z )(x < y ^ y < z ! x < z ) 4. (8x)(8y)(x < y _ y < x _ x = y) 5. (8x)(8y)(x < y ! (9z )(x < z ^ z < y)) 6. (8x)(9y)(x < y) 7. (8x)(9y)(y < x) 8. (8x)(8y)(8z )(x + (y + z ) = (x + y) + z ) 9. (8x)(x + 0 = x) 11
1. NOTATION AND EXAMPLES
12
(8x)(9y)(x + y = 0) (8x)(8y)(x + y = y + x) (8x)(8y)(8z )(x (y z ) = (x y) z ) (8x)(x 1 = x) (8x)(x = 0 _ (9y)(y x = 1) (8x)(8y)(x y = y x) (8x)(8y)(8z )(x (y + z ) = (x y) + (y z )) 0 6= 1 (8x)(8y)(8z )(x < y ! x + z < y + z ) (8x)(8y)(8z )(x < y ^ 0 < z ! x z < y z ) for each n 1 we have the formula (8x0 )(8x1 ) (8xn )(9y)(xn yn + xn;1 yn;1 + + x1 y + x0 = 0 _ xn = 0) 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
z
k
}|
{
where, as usual, yk abbreviates y y y The latter formulas express that each polynomial of degree n has a root. The following formulas express the intermediate value property for polynomials of degree n: if the polynomial changes sign from w to z , then it is zero at some y between w and z . 21. for each n 1 we have (8x0 ) : : : (8xn )(8w)(8z )(xn wn + xn;1 wn;1 + + x1 w + x0 )
(xn z n + xn;1 z n;1 + + x1 z + x0 ) < 0 ! (9y )(((w < y ^ y < z ) _ (z < y ^ y < w)) ^ (xn y n + xn;1 y n;1 + + x1 y + x0 = 0))] The most fundamental concept is that of a sentence being true when interpreted in a model A. We write this as A j= , and we extend this concept in the following denitions. Definition 11. If is a set of sentences, A is said to be a model of , written A j= , whenever A j= for each 2 . is said to be satis able i there is some A such that A j= . Definition 12. A theory T is a set of sentences. If T is a theory and is a sentence, we write T j= whenever we have that for all A if A j= T then A j= . We say that is a consequence of T . A theory is said to be closed whenever it contains all of its consequences. Definition 13. If A is a model for the language L, the theory of A, denoted by ThA, is dened to be the set of all sentences of L which are true in A, f of L : A j= g This is one way that a theory can arise. Another way is through axioms. Definition 14. T is said to be a set of axioms for T whenever j= for every in T in this case we write j= T . Remark. We will generally assume our theories are closed and we will often describe theories by specifying a set of axioms . The theory will then be all consequences of . Example 5. We will consider the following theories and their axioms:
1. NOTATION AND EXAMPLES
13
1. The theory of Linear Orderings (LOR) which has as axioms sentences 1-4 from Example 4. 2. The theory of Dense Linear Orders (DLO) which has as axioms all the axioms of LOR, and sentence 5, 6 and 7 of Example 4. 3. The theory of Fields (FEI) which has as axioms sentences 8-17 from Example 4. 4. The theory of Ordered Fields (ORF) which has as axioms all the axioms of FEI, LOR and sentences 18 and 19 from Example 4. 5. The theory of Algebraically Closed Fields (ACF) which has as axioms all the axioms of FEI and all sentences from 20 of Example 4, i.e. innitely many sentences, one for each n 1. 6. The theory of Real Closed Ordered Fields (RCF) which has as axioms all the axioms of ORF, and all sentences from 21 of Example 4, i.e. innitely many sentences, one for each n 1. Exercise 6. Show that : 1. Q j= DLO 2. R j= RCF using the Intermediate Value theorem 3. C j= ACF using the Fundamental Theorem of Algebra where Q, R and C are as in Example 3. Remark. The theory of Real Closed Ordered Fields is sometimes axiomatized dierently. All the axioms of ORF are retained, but the sentences from 21 of Example 4, which amount to an Intermediate Value Property, are replaced by the sentences from 20 for odd n and the sentence (8x)(0 < x ! (9y)y2 = x) which states that every positive element has a square root. A signicant amount of algebra would then be used to verify the Intermediate Value Property from these axioms.
CHAPTER 2
Compactness and Elementary Submodels Theorem 1. The Compactness Theorem (Malcev) A set of sentences is satis able i every nite subset is satis able. Proof. There are several proofs. We only point out here that it is an easy consequence of the following, a theorem which appears in all elementary logic texts: Proposition. The Completeness Theorem (Godel, Malcev) A set of sentences is consistent i it is satis able. Although we do not here formally dene \consistent", it does mean what you think it does. In particular, a set of sentences is consistent if and only if each nite subset is consistent. Remark. The Compactness Theorem is the only one for which we do not give a complete proof. If the reader has not previously seen the Completeness Theorem, there are other proofs of the Compactness Theorem which may be more easily absorbed: set theoretic (using ultraproducts), topological (using compact spaces, hence the name) or Boolean algebraic. However these topics are too far aeld to enter into the proofs here. We will use the Compactness Theorem as a starting point | in fact, all that follows can be seen as its corollaries. Exercise 7. Suppose T is a theory for the language L and is a sentence of L such that T j= . Prove that there is some nite T 0 T such that T 0 j= . Recall that T j= i T f:g is not satisable. Definition 15. If L, and L0 are two languages such that L L0 we say that 0 L is an expansion of L and L is a reduction of L0 Definition 16. Given a model A for the language L, we can expand it to a model A0 of L0 by giving appropriate interpretations to the symbols in L0 n L. We say that A0 is an expansion of A to L0 and that A is a reduct of A0 to L. We also use the notation A0 jL for the reduct of A0 to L. Theorem 2. If a theory T has arbitrarily large nite models, then it has an in nite model. Proof. Consider new constant symbols ci for i 2 N , the usual natural numbers, and expand from L, the language of T , to L0 = L fci : i 2 N g. Let = T f:ci = cj : i 6= j i j 2 N g: We rst show that every nite subset of has a model by interpreting the nitely many relevant constant symbols as dierent elements in an expansion of some nite model of T . Then we use compactness to get a model A0 of . 14
2. COMPACTNESS AND ELEMENTARY SUBMODELS
15
The model that we require is for the language L, so we take A to be the reduct of A0 to L.
< 0 1i, the set of all sentences of Example 6. Number theory is ThhN + <
< 0 1i, the standard model which we which are true in hN + < all learned in school. Theorem 3. (T. Skolem) There exist non-standard models of number theory. Proof. Add a new constant symbol c to L. Consider
L = f+ < 0 1g
z
n
}|
{
Th(hN + < 0 1i ) f1 + 1 + + 1 < c : n 2 N g and use the Compactness Theorem. The interpretation of the constant symbol c will not be a natural number. Definition 17. Two models A and A0 for L are said to be isomorphic whenever there is a bijection f : A ! A0 such that
1. for each n-placed relation symbol R of L and corresponding interpretations S of A and S 0 of A0 we have S (x1 : : : xn ) i S 0 (f (x1 ) : : : f (xn )) for all x1 : : : xn in A 2. for each n-placed function symbol F of L and corresponding interpretations G of A and G0 of A0 we have f (G(x1 : : : xn )) = G0 (f (x1 ) : : : f (xn )) for all x1 : : : xn in A 3. for each constant symbol c of L and corresponding constant elements a of A and a0 of A0 we have f (a) = a0 . We write A = A0 . This is an equivalence relation. Definition 18. Two models A and A0 for L are said to be elementarily equivalent whenever we have that for each sentence of L A j= i A0 j= We write A A0 . This is another equivalence relation. Exercise 8. Suppose f : A ! A0 is an isomorphism and ' is a formula such that A j= 'a0 : : : ak ] for some a0 : : : ak from A then A0 j= 'f (a0 ) : : : f (ak )]. Use this to show that A = A0 implies A A0 . Definition 19. A model A0 is called a submodel of A i 6= A0 A and 1. each n-placed relation S 0 of A0 is the restriction to A0 of the corresponding relation S of A, i. e. S 0 = S \ (A0 )n 2. each m-placed function G0 of A0 is the restriction to A0 of the corresponding function G of A, i. e. G0 = G (A0 )m 3. each constant of A0 is the corresponding constant of A. We write A0 A. Definition 20. Let A and B be two models for L. We say A is an elementary submodel of B and B is an elementary extension of A and we write A B whenever 1. A B and
2. COMPACTNESS AND ELEMENTARY SUBMODELS
16
2. for all formulas '(v0 : : : vk ) of L and all a0 : : : ak 2 A A j= 'a0 : : : ak ] i B j= 'a0 : : : ak ]: Exercise 9. Prove that if A B then A B and A B. Example 7. Let N be the usual natural numbers with < as the usual ordering. < i and A = hN n f0g<
2. COMPACTNESS AND ELEMENTARY SUBMODELS
17
1. If t is the variable vi then both values are just ai . 2. If t is the constant symbol c then the values are equal because c has the same interpretation in A and in Ak . 3. If t is F (t1 : : : tm ) where F is a function symbol and t1 : : : tm are terms such that each value ti a0 : : : ap ] is the same in both A and Ak , then the value F (t1 : : : tm )a0 : : : ap ] in A is G(t1 a0 : : : ap ] : : : tm a0 : : : ap ]) where G is the interpretation of F in A and the value of F (t1 : : : tm )a0 : : : ap ] in Ak is Gk (t1 a0 : : : ap ] : : : tm a0 : : : ap ]) where Gk is the interpretation of F in Ak . But Gk is the restriction of G to Ak so these values are equal. In order to show that each Ak A it will suce to prove the following statement for each formula '(v0 : : : vp ) of L. \ For all k 2 N and all a0 : : : ap in Ak : A j= 'a0 : : : ap ] i Ak j= 'a0 : : : ap ]:" Claim. The statement is true whenever ' is t1 = t2 where t1 and t2 are terms. Proof of Claim. Fix k 2 N and a0 : : : ap in Ak . A j= (t1 = t2 )a0 : : : ap ] i t1 a0 : : : ap ] = t2 a0 : : : ap ] in A i t1 a0 : : : ap ] = t2 a0 : : : ap ] in Ak i Ak j= (t1 = t2 )a0 : : : ap ]: Claim. The statement is true whenever ' is R(t1 : : : tn ) where R is a relation symbol and t1 : : : tn are terms. Proof of Claim. Fix k 2 N and a0 : : : ap in Ak . Let S be the interpretation of R in A and Sk be the interpretation in Ak Sk is the restriction of S to Ak . A j= R(t1 : : : tn )a0 : : : ap ] i S (t1 a0 : : : ap ] : : : tn a0 : : : ap ]) i Sk (t1 a0 : : : ap ] : : : tn a0 : : : ap ]) i Ak j= R(t1 : : : tn )a0 : : : ap ] Claim. If the statement is true when ' is , then the statement is true when
' is :.
Proof of Claim. Fix k 2 N and a0 : : : ap in Ak . A j= (:)a0 : : : ap ] i not A j= a0 : : : ap ] i not Ak j= a0 : : : ap ] i Ak j= (:)a0 : : : ap ]:
2. COMPACTNESS AND ELEMENTARY SUBMODELS
18
Claim. If the statement is true when ' is 1 and when ' is 2 then the statement is true when ' is 1 ^ 2 . Proof of Claim. Fix k 2 N and a0 : : : ap in Ak . A j= (1 ^ 2 )a0 : : : ap ] i A j= 1 a0 : : : ap ] and A j= 2 a0 : : : ap ] i Ak j= 1 a0 : : : ap ] and Ak j= 2 a0 : : : ap ] i Ak j= (1 ^ 2 )a0 : : : ap ]: Claim. If the statement is true when ' is then the statement is true when '
is 9vi .
Proof of Claim. Fix k 2 N and a0 : : : ap in Ak . Note that
A = fAj : j 2 Ng.
A j= 9vi a0 : : : ap ] i A j= 9vi a0 : : : aq ] where q is the maximum of i and p (by Lemma 2),
i A j= a0 : : : ai;1 a ai+1 : : : aq ] for some a 2 A i A j= a0 : : : ai;1 a ai+1 : : : aq ] for some a 2 Al for some l k i Al j= a0 : : : ai;1 a ai+1 : : : aq ] since the statement is true for , i Al j= 9vi a0 : : : aq ] i Ak j= 9vi a0 : : : aq ] since Ak Al i Ak j= 9vi a0 : : : ap ] (by Lemma 2): By induction on the complexity of ', we have proven the statement for all formulas ' which do not contain the connectives _, ! and $ or the quantier 8. To verify the statement for all ' we use Lemma 3. Let ' be any formula of L. By Lemma 3 there is a formula which does not use _, !, $ nor 8 such that j= (8v0 ) : : : (8vp )(' $ ): Now x k 2 N and a0 : : : ap in Ak . We have A j= (' $ )a0 : : : ap ] and Ak j= (' $ )a0 : : : ap ]: A j= 'a0 : : : ap ] i A j= a0 : : : ap ] i Ak j= a0 : : : ap ] i Ak j= 'a0 : : : ap ] which completes the proof of the theorem. Lemma 5. (The Tarski-Vaught Condition) Let A and B be models for L with A B. The following are equivalent: (1) A B
2. COMPACTNESS AND ELEMENTARY SUBMODELS
19
(2) for any formula (v0 : : : vq ) and any i q and any a0 : : : aq from A: if there is some b 2 B such that B j= a0 : : : ai;1 b ai+1 : : : aq ] then we have some a 2 A such that B j= a0 : : : ai;1 a ai+1 : : : aq ]: Proof. Only the implication (2) ) (1) requires a lot of proof. We will prove that for each formula '(v0 : : : vp ) and all a0 : : : ap from A we will have: A j= 'a0 : : : ap ] i B j= 'a0 : : : ap ] by induction on the complexity of ' using only the negation symbol :, the connective ^ and the quantier 9 (recall Lemma 3). 1. The cases of formulas of the form t1 = t2 and R(t1 : : : tn ) come immediately from the fact that A B. 2. For negation: suppose ' is : and we have it for , then A j= 'a0 : : : ap ] i not A j= a0 : : : ap ] i not B j= a0 : : : ap ] i B j= 'a0 : : : ap ]: 3. The ^ case proceeds similarly. 4. For the 9 case we consider ' as 9vi . If A j= 9vi a0 : : : ap ], then the inductive hypothesis for and the fact that A B ensure that B j= 9vi a0 : : : ap ]. It remains to show that if B j= 'a0 : : : ap ] then A j= 'a0 : : : ap ]. Assume B j= 9vi a0 : : : ap ]. By Lemma 2, B j= 9vi a0 : : : aq ] where q is the maximum of i and p. By the denition of satisfaction, there is some b 2 B such that B j= a0 : : : ai;1 b ai+1 : : : aq ]: By (2), there is some a 2 A such that B j= a0 : : : ai;1 a ai+1 : : : aq ]: By the inductive hypothesis on , for that same a 2 A, A j= a0 : : : ai;1 a ai+1 : : : aq ]: By the denition of satisfaction, A j= 9vi a0 : : : aq ]: Finally, by Lemma 2, A j= a0 : : : ap ]. Recall that jBj is used to represent the cardinality, or size, of the set B. Note that since any language L contains innitely many variables, jLj is always innite, but may be countable or uncountable depending on the number of other symbols. We often denote an arbitrary innite cardinal by the lower case Greek letter . Theorem 5. (Downward Lowenheim-Skolem Theorem) Let B be a model for L and let be any cardinal such that jLj < jBj. Then B has an elementary submodel A of cardinality . Furthermore if X B and jX j , then we can also have X A.
2. COMPACTNESS AND ELEMENTARY SUBMODELS
20
Proof. Without loss of generosity assume jX j = . We recursively dene sets Xn for n 2 N such that X = X0 X1 Xn and such that for each formula '(v0 : : : vp ) of L and each i p and each a0 : : : ap from Xn such that B j= 9vi 'a0 : : : ap ] we have x 2 Xn+1 such that B j= 'a0 : : : ai;1 x ai+1 : : : ap ]: Since jLj and each formula of L is a nite string of symbols from L, there are at most many formulas of L. So there are at most elements of B that need to be added to each Xn and so, without loss of generosity each jXn j = . Let A = fXn : n 2 Ng then jAj = . Since A is closed under functions from B and contains all constants from B, A gives rise to a submodel A B. The Tarski-Vaught Condition is used to show that A B. Theorem 6. (The Upward Lowenheim-Skolem Theorem) Let A be an in nite model for L and be any cardinal such that jLj and jAj < . Then A has an elementary extension of cardinality . Proof. For each a 2 A, let ca be a new constant symbol let L0 = L fca : a 2 Ag: Note that sentences of L0 are just formulas of L with all free variables replaced by constant symbols. In addition, add many new constant symbols to L0 to make L00 . Dene to be the following set of sentences of L00 : f:d = d0 : d and d0 are distinct new constant symbols of L00 n L0 g f : is a sentence of L0 obtained from the formula '(v0 : : : vp ) of L by replacing each free variable vi by the constant symbol cai and A j= 'a0 : : : ap ]g By interpreting ca as a and the d's as distinct elements of A we can transform A into a model of any nite subset of . Using the Compactness Theorem, we obtain a model D00 for L00 such that D00 j= . Note that D00 has size at least and that for any sentence of L0 , D00 j= i 2 . Obtain a model C00 for L00 from D00 by simply switching elements of the universe of D00 with A to ensure that for each a 2 A the interpretation of ca in C00 is a. Hence the universe of C00 contains A and C00 j= . Let C be the reduct of C00 to L. The following argument will show that A C. Let ' be any formula of L and a0 : : : ap any elements from A. Let be the sentence of L0 formed by replacing free occurances of vi with cai . We have A j= 'a0 : : : ap ] i 2 i D00 j= i C00 j= i C j= 'a0 : : : ap ]: However, C may have size strictly larger than . In this case we obtain our nal B by using the previous theorem to get B C with A B. It is now straightforward to conclude that A B.
2. COMPACTNESS AND ELEMENTARY SUBMODELS
21
Definition 23. A theory T for a language L is said to be complete whenever for each sentence of L either T j= or T j= :. Lemma 6. A theory T for L is complete i any two models of T are elementarily equivalent. Proof. ()) easy. (() easy. Definition 24. A theory T is said to be categorical in cardinality whenever any two models of T of cardinality are isomorphic. We also say that T is categorical. The most interesting cardinalities in the context of categorical theories are @0 , the cardinality of countably innite sets, and @1, the rst uncountable cardinal. Exercise 11. Show that DLO is @0 -categorical. There are two well-known proofs. One uses a back-and-forth construction of an isomorphism. The other constructs, by recursion, an isomorphism from the set of dyadic rational numbers between 0 and 1: n f m : m is a positive integer and n is an integer 0 < n < 2m g 2 onto a countable dense linear order without endpoints. Now use the following theorem to show that DLO is complete. Theorem 7. (The L os-Vaught Test) Suppose that a theory T has only in nite models for a language L and that T is
-categorical for some cardinal jLj. Then T is complete. Proof. We will show that any two models of T are elementarily equivalent. Let A of cardinality 1 , and B of cardinality 2 , be two models of T . If 1 < use the Upward Lowenheim-Skolem Theorem to get A0 such that 0 jA j = and A A0 . If 1 > use the Downward Lowenheim-Skolem Theorem to get A0 such that 0 jA j = and A0 A. Either way, we can get A0 such that jA0 j = and A0 A. Similarly, we can get B0 such that jB0 j = and B0 B. Since T is -categorical, A0 = B0 . Hence A B. Recall that the characteristic of a eld is the prime number p such that z
p
}|
{
1+1+
+1 = 0 provided that such a p exists, and, if no such p exists the eld has characteristic 0. All of our best-loved elds: Q , R and C have characteristic 0. On the other hand, elds of characteristic p include the nite eld of size p (the prime Galois eld). Theorem 8. The theory of algebraically closed elds of characteristic 0 is complete. Proof. We use the L os-Vaught Test and the following Lemma. Lemma 7. Any two algebraically closed elds of characteristic 0 and cardinality @1 are isomorphic.
2. COMPACTNESS AND ELEMENTARY SUBMODELS
22
Proof. Let A be such a eld containing the rationals Q = hQ + 0 1i as a prime subeld. In a manner completely analogous to nding a basis for a vector space, we can nd a transcendence basis for A, that is, an indexed subset fa : 2 I g A such that A is the algebraic closure of the subeld A0 generated by fa : 2 I g but no a is in the algebraic closure of the subeld generated by the rest: fa : 2 I and 6= g. Since the subeld generated by a countable subset would be countable and the algebraic closure of a countable subeld would also be countable, we must have that the transcendence base is uncountable. Since jAj = @1 , the least uncountable cardinal, we must have in fact that jI j = @1 . Now let B be any other algebraically closed eld of characteristic 0 and size @1 . As above, obtain a transcendence basis fb : 2 J g with jJ j = @1 and its generated subeld B0 . Since jI j = jJ j, there is a bijection g : I ! J which we can use to build an isomorphism from A to B. Since B has characteristic 0, a standard theorem of algebra gives that the rationals are isomorphically embedded into B. Let this embedding be: f : Q ,! B: We extend f as follows: for each 2 I , let f (a ) = bg( ) , which maps the transcendence basis of A into the transcendence basis of B. We now extend f to map A0 onto B0 as follows: Each element of A0 is given by p(a 1 : : : a m ) q(a 1 : : : a m ) where p and q are polynomials with rational coecients and the a's come, of course, from the transcendence basis. Let f map such an element to p!(bg( 1 ) : : : bg( m ) ) q!(bg( 1 ) : : : bg( m ) ) where p! and q! are polynomials whose coecients are the images under f of the rational coecients of p and q. The nal extension of f to all of A and B comes from the uniqueness of algebraic closures. Remark. Lemma 7 is also true when 0 is replaced by any xed characteristic and @1 by any uncountable cardinal. Theorem 9. Let H be a set of sentences in the language of eld theory which are true in algebraically closed elds of arbitrarily high characteristic. Then H holds in some algebraically closed eld of characteristic 0. Proof. A eld is a model in the language f+ 0 1g of the axioms of eld theory. Let ACF be the set of axioms for the theory of algebraically closed elds see Example 5. For each n 2, let n denote the sentence z
n
}|
{
:(1 + 1 + + 1) = 0
Let = ACF H fn : n 2g Let 0 be any nite subset of and let m be the largest natural number such that m 2 0 or let m = 1 by default.
2. COMPACTNESS AND ELEMENTARY SUBMODELS
23
Let A be an algebraically closed eld of characteristic p > m such that A j= H then in fact A j= 0 . So by compactness there is B such that B j= . B is the required eld. Corollary 1. Let C denote, as usual, the complex numbers. Every one-toone polynomial map f : C m ! C m is onto. Proof. A polynomial map is a function of the form f (x1 : : : xm ) = hp1 (x1 : : : xm ) : : : pm(x1 : : : xm )i where each pi is a polynomial in the variables x1 : : : xm . We call max f degree of pi : i mg the degree of f . Let L be the language of eld theory and let mn be the sentence of L which expresses that \each polynomial map of m variables of degree < n which is one-toone is also onto". We wish to show that there are algebraically closed elds of arbitrarily high characteristic which satisfy H = fmn : m n 2 N g. We will then apply Theorem 9, Theorem 8, Lemma 6 and Exercise 6 and be nished. Let p be any prime and let Fp be the prime Galois eld of size p. The algebraic closure F~p is the countable union of a chain of nite elds Fp = A0 A1 A2 Ak Ak+1
obtained by recursively adding roots of polynomials. We nish the proof by showing thatmeach hF~pm + 0 1i satises H. Given any polynomial map f : (F~p ) ! (F~p ) which is one-to-one, we show that f is also onto. Given any elements b1 : : : bm 2 F~p , there is some Ak containing b1 : : : bm as well as all the coecients of f. Since f is one-to-one, f Am Amk ! Amk is a one-to-one polynomial map. k :m m Hence, since Ak is nite, f Ak is onto and so there are a1 : : : am 2 Ak such that f (a1 : : : am ) = hb1 : : : bmi. Therefore f is onto. Thus, for each prime number p and each m n 2 N , mn holds in a eld of characteristic p, i.e. hF~p + 0 1i satises H.
It is a signicant problem to replace \one-to-one" with \locally one-to-one".
CHAPTER 3
Diagrams and Embeddings Let A = hA Ii be a model for a language L and X A. Expand L to = L fca : a 2 X g by adding new constant symbols to L. We can expand A to a model AX = hA I 0 i for LX by choosing I 0 extending I such that I 0 (ca ) = a for each a 2 X . We sometimes write this as hA cx ix2X . We often deal with the case X = A, to obtain AA . Exercise 12. Let A and B be models for L with X A B. Prove: (i) if A B then AX BX . (ii) if A = B then AX = BX . (iii) if A B then AX BX . Hint: A j= 'a1 : : : ap ] i AA j= ' where ' is the sentence of LA formed by replacing each free occurance of vi with cai . Definition 25. Let A be a model for L. 1. The elementary diagram of A is ThAA , the set of all sentences of LA which hold in AA . 2. The diagram of A, denoted by 4A, is the set of all those sentences in ThAA without quantiers. Remark. There is a notion of atomic formula, which is a formula of the form t1 = t2 or R(t1 : : : tn ) where t1 : : : tn are terms. Sometimes 4A is dened to be the set of all atomic formulas and negations of atomic formulas which occur in ThAA . However this is not substantially dierent from Denition 25, since the reader can quickly show that for any model B, B j= 4A in one sense i B j= 4A in the other sense. Definition 26. A is said to be isomorphically embedded in B whenever 1. there is a model C and an isomorphism f such that f : A ! C and C B or 2. there is a model D and an isomorphism g such that A D and g : D ! B Exercise 13. Prove that, in fact, 1 and 2 are equivalent conditions. Definition 27. A is said to be elementarily embedded in B whenever 1. there is a model C and an isomorphism f such that f : A ! C and C B LX
24
3. DIAGRAMS AND EMBEDDINGS
25
2. there is a model D and an isomorphism g such that A D and g : D ! B Exercise 14. Again, prove that, in fact, 1 and 2 are equivalent. Theorem 10. (The diagram lemmas) Let A and B be models for L.
1. A is isomorphically embedded in B i B can be expanded to a model of 4A . 2. A is elementarily embedded in B i B can be expanded to a model of Th(AA ). Proof. We sketch the proof of 1. ()) If f is as in 1 of Denition 26 above, then hB f (a)ia2A j= 4A. (() If hB ba ia2A j= 4A , then let f (a) = ba . Exercise 15. Give a careful proof of part 2 of the theorem.
We now apply these notions to graph theory and to calculus. The natural language for graph theory has one binary relation symbol which we call E (to suggest the word \edge"), and the following two axioms: (8x)(8y)E (x y) $ E (y x) (8x):E (x x). A graph is, of course, a model of graph theory. Corollary 2. Every planar graph can be four coloured. Proof. We will have to use the famous result of Appel and Haken that every nite planar graph can be four coloured. Model Theory will take us from the nite to the innite. We recall that a planar graph is one that can be embedded, or drawn, in the usual Euclidean plane and to be four coloured means that each vertex of the graph can be assigned one of four colours in such a way that no edge has the same colour for both endpoints. Let A be an innite planar graph. Introduce four new unary relation symbols: R G B Y (for red, green, blue and yellow). We wish to prove that there is some expansion A0 of A such that A0 j= where is the sentence in the expanded language: (8x)R(x) _ G(x) _ B (x) _ Y (x)] ^ (8x)R(x) ! :(G(x) _ B (x) _ Y (x))] ^ : : : ^ (8x)(8y ):(R(x) ^ R(y ) ^ E (x y )) ^
which will ensure that the interpretations of R G B and Y will four colour the graph. Let = 4A fg. Any nite subset of has a model, based upon the appropriate nite subset of A. By the compactness theorem, we get B j= . Since B j= , the interpretations of R G B and Y four colour it. By the diagram lemma A is isomorphically embedded in the reduct of B, and this isomorphism delivers the four-colouring of A. A graph with the property that every pair of vertices is connected with an edge is called complete. At the other extreme, a graph with no edges is called discrete. A very important theorem in nite combinatorics says that most graphs contain an
3. DIAGRAMS AND EMBEDDINGS
26
example of one or the other as a subgraph. A subgraph of a graph is, of course, a submodel of a model of graph theory. Corollary 3. (Ramsey's Theorem) For each n 2 N there is an r 2 N such that if G is any graph with r vertices, then either G contains a complete subgraph with n vertices or a discrete subgraph with n vertices. Proof. We follow F. Ramsey who began by proving an innite version of the theorem (also called Ramsey's Theorem). Claim. Each in nite graph G contains either an in nite complete subgraph or an in nite discrete subgraph. Proof of Claim. By force of logical necessity, there are two possiblities: (1) there is an innite X G such that for all x 2 X there is a nite Fx X such that E (x y) for all y 2 X n Fx , (2) for all innite X G there is a x 2 X and an innite Y X such that :E (x y ) for all y 2 Y . If (1) occurs, we recursively pick x1 2 X , x2 2 X n Fx1 , x3 2 X n (Fx1 Fx2 ), etc, to obtain an innite complete subgraph. If (2) occurs we pick x0 2 G and Y0 G with the property and then recursively choose x1 2 Y0 and Y1 Y0 , x2 2 Y1 and Y2 Y1 and so on, to obtain an innite discrete subgraph.
We now use Model Theory to go from the innite to the nite. Let be the sentence, of the language of graph theory, asserting that there is no complete subgraph of size n. (8x1 : : : 8xn ):E (x1 x2 ) _ :E (x1 x3 ) _ _ :E (xn;1 xn )]: Let be the sentence asserting that there is no discrete subgraph of size n. (8x1 : : : 8xn )E (x1 x2 ) _ E (x1 x3 ) _ _ E (xn;1 xn )]: Let T be the set consisting of , and the axioms of graph theory. If there is no r as Ramsey's Theorem states, then T has arbitrarily large nite models. By Theorem 2, T has an innite model, contradicting the claim. The following theorem of A. Robinson nally solved the centuries old problem of innitesimals in the foundations of calculus. Theorem 11. (The Leibniz Principle) There is an ordered eld R called the hyperreals, containing the reals R and an in nitesimal number such that any statement about the reals which holds in R also holds in R. < 0 1 i. We will make the statement of the theorem Proof. Let R be hR + < precise by proving that there is some model B, in the same language L as R and with the universe called R , such that R B and there is b 2 R such that 0 < b < a for each positive a 2 R.
3. DIAGRAMS AND EMBEDDINGS
27
For each real number a, we introduce a new constant symbol ca , and in addition another new constant symbol d. Let be the set of sentences in the expanded language given by: ThRR f0 < d < ca : a is a positive real g We can obtain a model C j= by the compactness theorem. Let C0 be the reduct of C to L. By the elementary diagram lemma R is elementarily embedded in C0 , and so there is a model B for L such that C0 = B and R B. Remark. This idea is extremely useful in understanding calculus. An element
x 2 R is said to be in nitesimal whenever ;r < x < r for each positive r 2 R. 0 is innitesimal. Two elements x y 2 R are said to be in nitely close, written x y whenever x ; y is innitesimal. Note: x is innitesimal i x 0. An element x 2 R is said to be nite whenever ;r < x < r for some positive r 2 R. Else it is
in nite. Each nite x 2 R is innitely close to some real number, called the standard part of x, written st(x). To dierentiate f , for each M x 2 R generate M y = f (x+ M x) ; f (x). Then ; My 0 f (x) = st Mx whenever this exists and is the same for each innitesimal M x 6= 0. The increment lemma states that if y = f (x) is dierentiable at x and M x 0, then M y = f 0 (x) M x + " M x for some innitesimal ". Proofs of the usual theorems of calculus are now easier. The following theorem is considered one of the most fundamental results of mathematical logic. We give a detailed proof. Theorem 12. (Robinson Consistency Theorem) Let L1 and L2 be two languages with L = L1 \L2 . Suppose T1 and T2 are satis able theories in L1 and L2 respectively. Then T1 T2 is satis able i there is no sentence of L such that T1 j= and T2 j= :. Proof. The direction ) is easy and motivates the whole theorem. We begin the proof in the ( direction. Our goal is to show that T1 T2 is satisable. The following claim is a rst step. Claim. T1 f sentences of L : T2 j= g is satis able. Proof of Claim. Using the compactness theorem and considering conjunctions, it suces to show that if T1 j= 1 and T2 j= 2 with 2 a sentence of L, then f1 2 g is satisable. But this is true, since otherwise we would have 1 j= :2 and hence T1 j= :2 and so :2 would be a sentence of L contradicting our hypothesis.
The basic idea of the proof from now on is as follows. In order to construct a model of T1 T2 we construct models A j= T1 and B j= T2 and an isomorphism f : AjL ! BjL between the reducts of A and B to the language L, witnessing that AjL = BjL. We then use f to carry over interpretations of symbols in L1 n L from A to B , giving an expansion B of B to the language L1 L2 . Then, since B jL1 = A and B jL2 = B we get B j= T1 T2 . The remainder of the proof will be devoted to constructing such an A, B and f . A and B will be constructed as unions of elementary chains of An's and Bn 's while f will be the union of fn : An ,! Bn .
3. DIAGRAMS AND EMBEDDINGS
28
We begin with n = 0, the rst link in the elementary chain. Claim. There are models A0 j= T1 and B0 j= T2 with an elementary embedding f0 : A0 jL ,! B0 jL. Proof of Claim. Using the previous claim, let A0 j= T1 f sentences of L : T2 j= g We rst wish to show that Th(A0 jL)A0 T2 is satisable. Using the compactness theorem, it suces to prove that if 2 Th(A0 jL)A0 then T2 fg is satisable. For such a let ca0 : : : can be all the constant symbols from LA0 n L which appear in . Let ' be the formula of L obtained by replacing each constant symbol cai by a new variable ui . We have A0 jL j= 'a0 : : : an ] and so A0 jL j= 9u0 : : : 9un ' By the denition of A0 , it cannot happen that T2 j= :9u0 : : : 9un ' and so there is some model D for L2 such that D j= T2 and D j= 9u0 : : : 9un '. So there are elements d0 : : : dn of D such that D j= 'do : : : dn ]. Expand D to a model D for L2 LA0 , making sure to interpret each cai as di . Then D j= , and so D j= T2 fg. Let B0 j= Th(A0 jL)A0 T2 . Let B0 be the reduct of B0 to L2 clearly B0 j= T2 . Since B0 jL can be expanded to a model of Th(A0 jL)A0 , the Elementary Diagram Lemma gives an elementary embedding f0 : A0 jL ,! B0 jL and nishes the proof of the claim. The other links in the elementary chain are provided by the following result. Claim. For each n 0 there are models An+1 j= T1 and Bn+1 j= T2 with an elementary embedding fn+1 : An+1 jL ,! Bn+1 jL such that An An+1 Bn Bn+1 fn+1 extends fn and Bn range of fn+1 :
A0
B0
#f0
A1
B1
#f1
An
An+1
Bn
Bn+1
#fn
#fn+1
The proof of this claim will be discussed shortly. Assuming the claim, let S S S A = n2N An , B = n2N Bn and f = n2N fn . The Elementary Chain Theorem gives that A j= T1 and B j= T2 . The proof of the theorem is concluded by simply verifying that f : AjL ! BjL is an isomorphism. The proof of the claim is long and quite technical it would not be inappropriate to omit it on a rst reading. The proof, of course, must proceed by induction on
3. DIAGRAMS AND EMBEDDINGS
29
n. The case of a general n is no dierent from the case n = 0 which we state and prove in some detail. Claim. There are models A1 j= T1 and B1 j= T2 with an elementary embedding f1 : A1 jL ,! B1 jL such that A0 A1 , B0 B1 , f1 extends f0 and B0 range of f1. A0 A1 #f0
#f1
B0 B1 Proof of Claim. Let A+0 be the expansion of A0 to the language L+1 = L1 fca : a 2 A0 g formed by interpreting each ca as a;2 A0 A+ 0 is just another notation for (A0 )A0 . The elementary diagram of A+0 is Th A+0 A+0 . Let B0 be the expansion of B0 jL to the language L = L fca : a 2 A0 g fcb : b 2 B0 g formed by interpreting each ca as f0 (a) 2 B0 and each cb as b 2 B0 . ;
We wish to prove that Th A+0 A+0 ThB0 is satisable. By the compactness ; theorem it suces to prove that Th A+0 A+0 fg is satisable for each in ThB0 . For such a sentence , let ca0 : : : cam cb0 : : : cbn be all those constant symbols occuring in but not in L. Let '(u0 : : : um w0 : : : wm ) be the formula of L obtained from by replacing each constant symbol cai by a new variable ui and each constant symbol cbi by a new variable wi . We have B0 j= so B0 jL j= 'f0 (a0 ) : : : f0 (am ) b0 : : : bn ] So B0 jL j= 9w0 : : : 9wn 'f0 (a0 ) : : : f0 (am )] Since f0 is an elementary embedding we have : A0 jL j= 9w0 : : : 9wn 'a0 : : : am ] Let '^(w0 : : : wn ) be the formula of L+1 obtained by replacing occurances of ui in '(u0 : : : um w0 : : : wn ) by cai then A+0 j= 9w0 : : : 9wn '^. So, of course, ; + A0 A+0 j= 9w0 : : : 9wn '^ and this means that there are d0 : : : dn in A+0 = A0 such that (A+0 )A+0 j= '^d0 : : : dn ]: ; + We can now expand A0 A+0 to a model D by interpreting each cbi as di to obtain ; D j= and so Th A+0 A+0 fg is satisable. ; Let E j= Th A+0 A+0 ThB0 . By the elementary diagram lemma A+0 is elementarily embedded into EjL+1 . So there is a model A+1 for L+1 with A+0 A+1 and an isomorphism g : A+1 ! EjL+1 . Using g we expand A+1 to a model A01 isomorphic to E. Let A1 denote A01 jL we have A1 j= ThB0 . ;
We now wish to prove that Th (A1 )A1 Th B+0 B+0 is satisable, where B+0 is the common expansion of B0 and B0 to the language L2+ = L2 fca : a 2 A0 g fcb : b 2 B0 g:
3. DIAGRAMS AND EMBEDDINGS
30
By the compactness theorem, it suces to show that ; Th B+0 B+0 fg
is satisable for each in Th (A1 )A1 . Let cx0 : : : cxn be all those constant symbols which occur in but are not in L . Let (u0 : : : un ) be the formula of L obtained from by replacing each cxi with a new variable ui . Since (A1 )A1 j= we have A1 j= x0 : : : xn ], and so A1 j= 9u0 : : : 9un : Also A1 j= ThB0 and ThB0 is a complete theory in the language L hence 9u0 : : : 9un is in ThB0 . Thus B0 j= 9u0 : : : 9un and so ; + B0 B+0 j= 9u0 : : : 9un and therefore there are b0 : : : bn in B+0 = B0 such that ; + B0 B+0 j= b0 : : : bn]: ;
We can now expand B+0 B+0 to a model F by interpreting each cxi as bi then ; F j= and Th B+0 B+0 fg is satisable. ; Let G j= Th (A1 )A1 Th B+0 B+0 . By the elementary diagram lemma B+0 is elementarily embedded into GjL+2 . So there is a model B+1 for L+2 with B+0 B+1 and an isomorphism h : B+1 ! GjL+2 . Using h we expand B+1 to a model B01 isomorphic to G. Let B1 denote B01 jL . Again by the elementary diagram lemma A1 is elementarily embedded into B1 . Let this be denoted by f1 : A1 ,! B1 : Let a 2 A0 we will show that f0 (a) = f1 (a). By denition we have B0 j= (v0 = ca )f0 (a)] and so B+0 j= (v0 = ca )f0 (a)]: Since B+0 B+1 , B+1 j= (v0 = ca )f0 (a)] and so B1 j= (v0 = ca )f0 (a)]: Now A+0 j= (ca = v1 )a] and A+0 A+1 so A+1 j= (ca = v1 )a] so A1 j= (ca = v1 )a]: Since f1 is elementary, B1 j= (ca = v1 )f1 (a)] so B1 j= (v0 = v1 )f0 (a) f1 (a)] and so f0 (a) = f1(a). Thus f1 extends f0. Let b 2 B0 we will prove that b = f1 (a) for some a 2 A1 . By denition we have: B0 j= (v0 = cb )b] so B+0 j= (v0 = cb )b]. Since B+0 B+1 B+1 j= (v0 = cb )b] so B1 j= (v0 = cb )b]. On the other hand, since (9v1 )(v1 = cb ) is always satised, we have: A1 j= (9v1 )(v1 = cb ) so there is a 2 A1 such that A1 j= (v1 = cb )a]: Since f1 is elementary, B1 j= (v1 = cb )f1 (a)] so B1 j= (v0 = v1 )b f1 (a)] so b = f1(a). Thus B0 range of f1 . We now let A1 be A+1jL1 and let B1 be B+1 jL2 . We get A0 A1 and B0 B1 and f1 : A1 jL ! B1 jL remains an elementary embedding. This completes the proof of the claim. Exercise 16. The Robinson Consistency Theorem was originally stated as:
3. DIAGRAMS AND EMBEDDINGS
31
Let T1 and T2 be satisable theories in languages L1 and L2 respectively and let T T1 \T2 be a complete theory in the language L1 \ L2 . Then T1 T2 is satisable in the language L1 L2 . Show that this is essentially equivalent to our version in Theorem 12 by rst proving that this statement follows from Theorem 12 and then also proving that this statement implies Theorem 12. Of course, for this latter argument you are looking for a proof much shorter than our proof of Theorem 12 however it will help to use the rst claim of our proof in your own proof. Theorem 13. (Craig Interpolation Theorem) Let ' and be sentences such that ' j= . Then there exists a sentence , called the interpolant, such that ' j= and j= and every relation, function or constant symbol occuring in also occurs in both ' and . Exercise 17. Show that the Craig Interpolation Theorem follows quickly from the Robinson Consistency Theorem. Also, use the Compactness Theorem to show that Theorem 12 follows quickly from Theorem 13.
CHAPTER 4
Model Completeness The quantier 8 is sometimes said to be the universal quanti er and the quantier 9 to be the existential quanti er. A formula ' is said to be quanti er free whenever no quantiers occur in '. A formula ' is said to be universal whenever it is of the form 8x0 : : : 8xk where is quantier free. A formula ' is said to be existential whenever it is of the form 9x0 : : : 9xk where is quantier free. A formula ' is said to be universal-existensial whenever it is of the form 8x0 : : : 8xk 9y0 : : : 9yk where is quantier free. We extend these notions to theories T whenever each axiom of T has the property. Remark. Note that each quantier free formula ' is trivially equialent to the existential formula 9vi ' where vi does not occur in '. Exercise 18. Let A and B be models for L with A B. Verify the following four statements: (i) A B i BA j= Th(AA ) i AA j= Th(BA ): (ii) A B i BA j= 4A i BA j= for each quantier free of Th(AA ): (iii) A B i BA j= for each existential of Th(AA ): (iv) A B i AA j= for each universal of Th(BA ): Definition 28. A model A of a theory T is said to be existentially closed if whenever A B and B j= T , we have AA j= for each existential of Th(BA ): Remark. If A is existentially closed and A0 = A then A0 is also existentially closed. Definition 29. A theory T is said to be model complete whenever T 4A is complete in the language LA for each model A of T . Theorem 14. ( A. Robinson ) Let T be a theory in the language L. The following are equivalent: (1) T is model complete, (2) T is existentially complete, i.e. each model of T is existentially closed. (3) for each formula '(v0 : : : vp ) of L there is a universal formula (v0 : : : vp ) such that T j= (8v0 : : : 8vp )(' $ ) (4) for all models A and B of T , A B implies A B. Proof. (1) ) (2): Let A j= T and B j= T with A B. Clearly AA j= 4A it is also easy to see that BA j= 4A. Now by (1), T 4A is complete and both AA and BA are models of this theory so they are elementarily equivalent. 32
4. MODEL COMPLETENESS
33
So let be any sentence of LA (existential or otherwise). If BA j= then AA j= and (2) follows. (2) ) (3): Lemma 4 shows that it suces to prove it for formulas ' in prenex normal form. We do this by induction on the prenex rank of ' which is the number of alternations of quantiers in '. The rst step is prenex rank 0. Where only universal quantiers are present the result is trivial. The existential formula case is non-trivial it is the following claim: Claim. For each existential formula '(v0 : : : vp ) of L there is a universal formula (v0 : : : vp ) such that T j= (8v0 ) : : : (8vp )(' $ ) Proof of Claim. Add new constant symbols c0 : : : cp to L to form L = L fc0 : : : cp g and to form a sentence ' of L obtained by replacing each instance of vi in ' with the corresponding ci ' is an existential sentence. It suces to prove that there is a universal sentence of L such that T j= ' $ . Let ; = funiversal sentences of L such that T j= ' ! g We hope to prove that there is some 2 ; such that T j= ! ' . Note, however, that any nite conjunction 1 ^ 2 ^ ^ n of sentences from ; is equivalent to a sentence in ; which is simply obtained from 1 ^ 2 ^ ^ n by moving all the quantiers to the front. Thus it suces to prove that there are nitely many sentences 1 2 : : : n from ; such that T j= 1 ^ 2 ^ ^ n ! ' : If no such nite set of sentences existed, then each T f1 2 : : : n g f:' g
would be satisable. By the compactness theorem, T ; f:' g would be satisable. Therefore it just suces to prove that T ; j= ' . In order to prove that T ; j= ' , let A be any model of T ;. Form LA as usual but ensure that fc0 : : : cp g fca : a 2 Ag so that L LA . Let = T f' g 4A: We wish to show that is satisable. By the compactness theorem it suces to consider T f' g where is a conjunction of nitely many sentences of 4A. Let be the formula obtained from by exchanging each constant symbol from LA n L occuring in for a new variable ua . So A j= 9ua0 : : : 9uam (ua0 : : : uam ): But then A is not a model of the universal sentence 8ua0 : : : 8uam :(ua0 : : : uam ). Recalling that A j= ;, we are forced to conclude that this universal sentence is not in ; and so not a consequence of T f' g. So T f' g f9ua0 : : : 9uam (ua0 : : : uam )g must be satisable, and any model of this can be expanded to a model of T f' g. Thus is satisable for the language LA .
4. MODEL COMPLETENESS
34
Let C j= . By the diagram lemma, there is a model B for L such that AjL B and B = CjL. Thus both AjL and B are models of T . Furthermore BA = C so that BA j= ' . We now use (2) to get that (AjL)A j= ' . But (AjL)A is just AA and so A j= ' . This means T ; j= ' and nishes the proof of the claim. We will now do the general cases for the proof of the induction on prenex rank. There are two cases, corresponding to the two methods available for increasing the number of alternations of quantiers: (a) the addition of universal quantiers (b) the addition of existential quantiers. For the case (a), suppose '(v0 : : : vp ) is 8w0 : : : 8wm (v0 : : : vp w0 : : : wm ) and has prenex rank lower than ' so that we have by the inductive hypothesis that there is a quantier free formula (v0 : : : vp w0 : : : wm x0 : : : xn ) with new variables x0 : : : xn such that T j= (8v0 : : : 8vp 8w0 : : : 8wm )( $ 8x0 : : : 8xn ) Therefore, case (a) is concluded by noticing that this gives us T j= (8v0 : : : 8vp )(8w0 : : : 8wm $ 8w0 : : : 8wm 8x0 : : : 8xn ): Exercise 19. Check this step using the denition of satisfaction. For case (b), suppose '(v0 : : : vp ) is 9w0 : : : 9wn (v0 : : : vp w0 : : : wm ) and has prenex rank less than '. Here we will use the inductive hypothesis on : which of course also has prenex rank less than '. We obtain a quantier free formula (v0 : : : vp w0 : : : wm x0 : : : xn ) with new variables x0 : : : xn such that T j= (8v0 : : : 8vp 8w0 : : : 8wm )(: $ 8x0 : : : 8xn ) So T j= (8v0 : : : 8vp )(8w0 : : : 8wm : $ 8w0 : : : 8wm 8x0 : : : 8xn ) And T j= (8v0 : : : 8vp)(9w0 : : : 9wm $ 9w0 : : : 9wm 9x0 : : : 9xn :) Now 9w0 : : : 9wm 9x0 : : : 9xn : is an existential formula, so by the claim there is a universal formula such that T j= (8v0 : : : 8vp )(9w0 : : : 9wm 9x0 : : : 9xn : $ ): Hence T j= (8v0 : : : 8vp )(9w0 : : : 9wn $ ) which is the nal result which we needed. (3) ) (4) Let A j= T and B j= T with A B. Let ' be a formula of L and let a0 : : : ap be in A such that B j= 'a0 : : : ap ] Obtain a universal formula such that T j= (8v0 : : : 8vp )(' $ ) so B j= a0 : : : ap ] Since A B A j= a0 : : : ap ]
4. MODEL COMPLETENESS
35
and so A j= 'a0 : : : ap ] and A B. (4) ) (1): Let A j= T . We will show that T 4A is complete by showing that for any model B for LA , B j= T 4A implies B j= Th(AA ). Letting B be such a model, we note that BjL, the restriction of B to L, can be expanded to B, a model of 4A. So by the diagram lemma A is isomorphically embedded in BjL. Furthermore, by checking the proof of the diagram lemma we can ensure that there is an f : A ,! BjL such that for each a 2 A, f (a) is the interpretation of ca in B. (Recall that LA = L fca : a 2 Ag). Moreover, as in Exercise 13, there is a model D for L such that A D and an isomorphism g : D ! BjL with the property that for each a 2 A, g(a) is the interpretation of ca in B. Now let 2 Th(AA ), so that AA j= . Let '(u0 : : : uk ) be the formula of L obtained by replacing each occurance of cai in by the new variable ui . We have A j= 'a0 : : : ak ] Since A D we can use (4) to get A D and so we have D j= 'a0 : : : ak ]. With the isomorphism g we get that BjL j= 'g(a0 ) : : : g(ak )] and since g(ai ) is the interpretation of cai in B we have B j= . Thus B j= Th(AA ) and this proves (1). Example 9. We will see later that the theory ACF is model complete. But ACF is not complete because the characteristic of the algebraically closed feild can vary among models of ACF and the assertion that \I have characteristic p" can easily be expressed as a sentence of the language of ACF. Exercise 20. Suppose that T is a model complete theory in L and that either 1. any two models of T are isomorphically embedded into a third or 2. there is a model of T which is isomorphically embedded in any other. Then prove that T is complete. Example 10. Let N be the usual natural numbers and < the usual ordering. Let B = hN
4. MODEL COMPLETENESS
36
Proof. W.L.O.G. we assume that T is satisable. We use conditions (1) and (2) to prove the following: Claim. T has existentially closed models of each in nite size . Proof of Claim. By the Lowenheim-Skolem Theorems we get A0 j= T with jA0 j = . We recursively construct a chain of models of T of size
A0 A1 : : : An An+1
with the property that if B j= T and An+1 B and is an existential sentence of Th(BAn ), then (An+1 )An j= . Suppose An is already constructed we will construct An+1. Let n be a maximally large set of existential sentences of LAn such that for each nite 0 n there is a model C for LAn such that C j= 0 T 4An By compactness T n 4An has a model D and without loss of generosity An D. By the Downward Lowenheim-Skolem Theorem we get E such that An E, jEj = and E D. Let An+1 = EjL we will show that An+1 has the required properties. Since E D, E j= T 4An and so A An+1 (See Exercise 18). Let B j= T with An+1 B and be an existential sentence of Th(BAn ) we will show that (An+1 )An j= . Since n consists of existential sentences and D E (An+1 )An BAn we have (see Exercise 18) that BAn j= n . The maximal property of n then forces to be in n because if 2= n then there must be some nite 0 n for which there is no C such that C j= 0 fg T 4An but BAn is such a C! Now since 2 n and E D j= n we must have E = (An+1 )An j= : Now let A be the union of the chain. By hypothesis A j= T . It is easy to check that jAj = . To check that A is existentially closed, let B j= T with A B and let be an existential sentence of ThBA . Since can involve only nitely many constant symbols, is a sentence of LAn for some n 2 N . Thus An+1 A B gives that (An+1 )An j= . Since is existential (see Exercise 18 again) we get that A j= . This completes the proof of the claim. We now claim that T is model complete using Theorem 14 by showing that every model A of T is existentially closed. There are three cases to consider: 1. jAj =
2. jAj >
3. jAj <
where T is -categorical. Case (1). Let A be an existentially closed model of T of size . Then there is an isomorphism f : A ! A . Hence A is existentially closed. Case (2). Let be an existential sentence of LA and B j= T such that A B and BA j= . Let X = fa 2 A : ca occurs in g. By the Downward LowenheimSkolem Theorem we can nd A0 such that A0 A, X A0 and jA0 j = . Now by Case (1) A0 is existentially closed and we have A0 B and in LA0 so A0A0 j= . But since 2 Th(A0A0 ) and A0 A we have AA j= .
4. MODEL COMPLETENESS
37
Case (3). Let and B be as in case (2). By the Upward Lowenheim-Skolem Theorem we can nd A0 such that A A0 and jA0j = . By case (1) A0 is existentially closed. Claim. There is a model B0 such that A0 B0 and BA B0A . Assuming this claim, we have B0 j= T and B0A j= and by the fact that A0 is existentially closed we have A0A0 j= . Since A A0 we have AA j= . The following lemma implies the claim and completes the proof of the theorem. Lemma 8. Let A, B and A0 be models for L such that A B and A A0 . Then there is a model B0 for L such that A0 B0 and BA B0A . Proof. Let A, B, A0 and L be as above. Note that since A B we have
BA j= 4A and so AA BA . Let be a sentence from 4A0 . Let fdj : 0 j mg be the constant symbols from LA0 n LA appearing in . Obtain a quantier free formula '(u0 : : : um) of LA by exchanging each dj in with a new variable ui . Since A0A0 j= we have A0A j= 9u0 : : : 9um': Since A A0 we have AA A0A and so AA j= 9u0 : : : 9um ': Since AA BA , BA j= 9u0 : : : 9um ': Hence for some b0 : : : bm in B, BA j= 'b0 : : : bm ]. Expand BA to be a model BA for the w language LA fdj : 0 j mg by interpreting each dj as bj . Then BA j= and so Th(BA ) f g is satisable. This shows that ThBA is satisable for each nite subset 4A0 . By the Compactness Theorem there is a model C j= 4A0 ThBA . Using the Diagram Lemma for the language LA we obtain a model B0 for L such that A0A B0A and B0A = CjLA . Hence B0A j= ThBA and so B0A BA . Exercise 21. Suppose A A0 are models for L. Prove that for each sentence
of LA , if 4A0 j= then 4A j= .
Exercise 22. Prove that if T has a universal-existential set of axioms, then the union of a chain of models of T is also a model of T . Remark. The converse of this last exercise is also true it is called the ChangL os- Suszko Theorem. Theorem 16. The following theories are model complete: 1. dense linear orders without endpoints. (DLO) 2. algebraically closed elds. (ACF) Proof. (DLO): This theory has a universal existential set of axioms so that it is closed under unions of chains. It is @0 -categorical (by Exercise 11) so Lindstrom's test applies. (ACF): We rst prove that for any xed characteristic p, the theory of algebraically closed elds of characteristic p is model complete. The proof is similar to that for DLO, with @1 -categoricity (Lemma 7 ). Let A B be algebraically closed elds. They must have the same characteristic p. Therefore A B. Corollary 4. Any true statement about the rationals involving only the usual ordering is also true about the reals.
4. MODEL COMPLETENESS
38
<11 i and B = hR<<22 i where <1 and <2 are the usual Proof. Let A = hQ < orderings. The precise version of this corollary is: A B. This follows from Theorem 14 and Theorem 16 and the easy facts that A j= DLO, B j= DLO and A B. The reader will appreciate the power of these theorems by trying to prove A B directly, without using them. Corollary 5. (Hilbert's Nullstellensatz)
Let be a nite system of polynomial equations and inequations in several variables with coe cients in the eld A. If has a solution in some eld extending A then has a solution in the algebraic closure of A. Proof. Let be the existential sentence of the language LA which asserts the fact that there is a solution of . Suppose has a solution in a eld B with A B. Then BA j= . So B0A j= where B0 is the algebraic closure of B. Let A0 be the algebraic closure of A. Since A B, we have A0 B0 . By Theorem 16, ACF is model complete, so A0 B0 . Hence A0A B0A and 0 AA j= .
CHAPTER 5
The Seventeenth Problem We will give a complete proof later that RCF, the theory of real closed ordered elds, is model complete. However, by assuming this result now, we can give a solution to the seventeenth problem of the list of twenty-three problems of David Hilbert's famous address to the 1900 International Congress of Mathematicians in Paris. Corollary 6. (E. Artin) Let q(x1 : : : xn ) be a rational function with real coe cients, which is positive definite. i.e. q(a1 : : : an ) 0 for all a1 : : : an 2 R Then there are nitely many rational functions with real coe cients f1(x1 : : : xn ), : : : , fm (x1 : : : xn ) such that
q(x1 : : : xn ) =
m X j =1
(fj (x1 : : : xn ))2
We give a proof of this theorem after a sequence of lemmas. The rst lemma just uses calculus to prove the special case of the theorem in which q is a polynomial in only one variable. This result probably motivated the original question. Lemma 9. A positive de nite real polynomial is the sum of squares of real polynomials. Proof. We prove this by induction on the degree of the polynomial. Let p(x) 2 Rx] with degree deg(p) 2 and p(x) 0 for all real x. Let p(a) = minfp(x) : x 2 Rg, so p(x) = (x ; a)q(x) + p(a) and p0 (a) = 0 for some polynomial q. But p0 (a) = (x ; a)q0 (x) + q(x)]x=a = q(a) so q(a) = 0 and q(x) = r(x)(x ; a) for some polynomial r(x). So p(x) = p(a) + (x ; a)2 r(x): For all real x we have (x ; a)2 r(x) = p(x) ; p(a) 0: Since r is continuous, r(x) 0 for all real x, and deg(r) = deg(p) ; 2. So, by Pn induction r(x) = i=1 (ri (x))2 where each ri (x) 2 Rx]. So p(x) = p(a) +
n X i=1 39
(x ; a)2 (ri (x))2 :
5. THE SEVENTEENTH PROBLEM
i.e. p(x) =
hp
i2
p(a) +
n X i=1
40
(x ; a)ri (x)]2 :
The following lemma shows why we deal with sums of rational functions rather than sums of polynomials. Lemma 10. x4 y2 + x2 y4 ; x2 y2 + 1 is positive de nite, but not the sum of squares of polynomials. Proof. Let the polynomial be p(x y). A little calculus shows that the mini26 and conrms that p is positive denite. mum value of p is 27 Suppose
p(x y) =
l X i=1
(qi (x y))2
where qi (x y) are polynomials, each of which is the sum of terms of the form axm yn . First consider powers of x and the largest exponent m which can occur in any of the qi . Since no term of p contains x6 or higher powers of x, we see that we must have m 2. Considering powers of y similarly gives that each n 2. So each qi (x y) is of the form: ai x2 y2 + bi x2 y + ci xy2 + di x2 + ei y2 + fi xy + gi x + hi y + ki for some coecients ai bi ci di ei fi gi hi and ki . Comparing coecients of x4 y4 in p and the sum of the qi2 gives 0=
l X i=1
a2i
so each ai = 0. Comparing the coecients of x4 and y4 gives that each di = 0 = ei . Now comparing the coecients of x2 and y2 gives that each gi = 0 = hi . Now comparing the coecients of x2 y2 gives ;1 =
which is impossible.
l X i=1
fi2
The next lemma is easy but useful. Lemma 11. The reciprocal of a sum of squares is a sum of squares. Proof. For example 1 = A2 + B 2 = A 2+ B 2 A2 + B 2 (A2 + B 2 )2 A2 + B 2 A2 + B 2 The following lemma is an algebraic result of E. Artin and O. Schreier, who invented the theory of real closed elds.
5. THE SEVENTEENTH PROBLEM
41
(5) for any c 2 B n f0g either c 2 P or ;c 2 P . Once P has been obtained, we dene
Let P0 = :
i=1
c2i ;
m X j =1
9 =
d2j b : l m 2 N ci 2 B dj 2 B not all zero
We claim that (1), (2), (3) P and (4) holdPfor P0 . (1) and (3) are obvious. In l 2 2 order to verify (2), note that if m j =1 dj b = i=1 ci , then by the previous lemma about reciprocals of sums of squares, b would be a sum of squares. Now (4) holds by denition of P0 , noting that c2i (;d2j b) = ;(ci dj )2 b and (;d2j b)(;d2k b) = (dj dk b)2 . We now construct larger and larger versions of P0 to take care of requirement (5). We do this in the following way. Suppose P0 P1 , P1 satises (1), (2), (3) and (4), and c 2= P1 . We dene P2 to be: fp(;c) : p is a polynomial with coecients in P1 g: It is easy to see that ;c 2 P2 , P1 P2 and that (1), (3) and (4) hold for P2 . To show that (2) holds for P2 we suppose that p(;c) = 0 and bring forth a contradiction. Considering even and odd exponents we obtain: p(x) = q(x2 ) + xr(x2 ) for some polynomials q and r with coecients in P1 . If r(c2 ) = 0 then q(c2 ) = 0. But q(c2 ) is in P1 , which is a contradiction. On the other hand, if r(c2 ) 6= 0 then 0 = p(;c) = q(c2 ) ; cr(c2 ) which means that 2 1 2 2 c = q(c ) r(c ) r(c2 ) and since each of the factors on the right hand side is in P1 we get a contradiction. Now we need:
5. THE SEVENTEENTH PROBLEM
42
Lemma 13. Every ordered eld can be embedded as a submodel of a real closed ordered eld. Proof. It suces to prove that for every ordered eld A there is an ordered eld B such that A B and for each natural number n 1, B j= n where n is the sentence in the language of eld theory which formally states: If p is a polynomial of degree at most n and w < y such that p(w) < 0 < p(y) then there is an x such that w < x < y and p(x) = 0. Consider the statement called IH(n): For any ordered eld E there is an ordered eld F such that E F and E j= n . IH(1) is true since any ordered eld E j= 1 . We will prove below that for each n, IH(n) implies IH(n + 1). Given our model A j= ORF, we will then be able to construct a chain of models:
A B1 B2 : : : Bn Bn+1
such that each Bn j= ORF fn g. Let B be the union of the chain. Since the theory ORF is preserved under unions of chains (see Exercise 22), B j= ORF. Furthermore, the nature of the sentences n allows us to conclude that for each n, B j= n and so B j= RCF. All that remains is to prove that for each n, IH(n) implies IH(n + 1). We rst make a claim: Claim. If E j= ORF fn g and p is a polynomial of degree at most n + 1 with coe cients from E and a < d are in E such that p(a) < 0 < p(d) then there is a model F such that E F, F j= ORF and there is b 2 such that a < b < d and p(b) = 0. Let us rst see how this claim helps us to prove that IH(n) implies IH(n+1). Let E j= ORF we will use the claim to build a model F such that E F and F j= n+1 . We rst construct a chain of models of ORF E = E0 E1 : : : Em Em+1
such that for each m and each polynomial p of degree at most n +1 with coecients from Em and each pair of a, d of elements of Em such that p(a) < 0 < p(d) there is a b 2 Em+1 such that a < b < d and p(b) = 0. Suppose Em has been constructed we construct Em+1 as follows: let m be the set of all existential sentences of LEm of the form (9x)(ca < x ^ x < cd ^ p(x) = 0) where p is a polynomial of degree at most n + 1 and such that ca , cd and the coecients of the polynomial p are constant symbols from LEm and (Em )Em j= p(ca ) < 0 ^ 0 < p(cd) We claim that ORF 4Em m is satisable.
5. THE SEVENTEENTH PROBLEM
43
Using the Compactness Theorem, it suces to nd, for each nite subset of m , a model C such that Em C and C j= ORF f1 : : : k g: By IH(n), obtain a model F1 such that Em F1 and F1 j= ORF fn g. By the claim, obtain a model F2 such that F1 F2 and F2 j= ORF f1 g. Again by IH(n), obtain F3 such that F2 F3 and F3 j= ORF fn g. Again by the claim, obtain F4 such that F3 F4 and F4 j= ORF f2 g. Continue in this manner, getting models of ORF Em F1 : : : F2k with each F2j j= j . Since each j is existential, we get that F2k is a model of each j (see Exercise 18). Let D j= ORF 4Em m and then use the Diagram Lemma to get Em+1 such that Em Em+1 , Em+1 j= ORF and Em+1 j= m , thus satisfying the required property concerning polynomials from Em . Let F be the union of the chain. Since ORF is a universal-existential theory, F j= ORF (see Exercise 22) and F j= n+1 by construction. So IH(n + 1) is proved. We now nish the entire proof by proving the claim. Proof of Claim. If p(x) = 0 for some x in E such that a < x < d then we can let F = E. Otherwise, introduce a new element b to E where the place of b in the ordering is given by: b = supremumft 2 E : t < d and p(t) < 0g: Note that continuity-style considerations show that b 6= d. We now show that since E j= n the polynomial p cannot be factored in E. Suppose p(x) = q(x) s(x). The denition of b allows us to nd a1 and d1 such that a1 < b < d1 and p(a1 ) < 0 < p(d1 ) and such that, other than possibly b, q and s have no roots in the interval of E between a1 and d1 . Now since p(a1 ) p(d1 ) < 0 either q(a1 ) q(d1 ) < 0 or s(a1 ) s(d1 ) < 0 and q and s each have degree n, forcing b to be an element of E. The fact that p is irreducible over E means that we can extend hE + 0 1i by quotients of polynomials in b of degree n to form a eld hF + 0 1i in the usual way. We leave the details to the reader. Note that the construction cannot force q(b) = 0 for any polynomial q(x) with coecients from E of degree n. This is because we could take such a q(x) of lowest degree and divide p(x) by it to get p(x) = q(x) s(x) + r(x) where degree of r < degree of q. This means that r(x) = 0 constantly and so p could have been factored over E. Now we must expand hF + 0 1 i to an ordered eld F while preserving the order of E. We are aided in this by the fact that if q is a polynomial of degree at most n with coecients from E then there are a1 and a2 in E such that a1 < b < a2 and q doesn't change sign between a1 and a2 this comes from the fact that E j= n . f1 : : : k g
5. THE SEVENTEENTH PROBLEM
44
Proof of the Corollary. Using Lemma 11 we see that it suces to prove the corollary for a polynomial p(x1 : : : xn ) such that p(a1 : : : an ) 0 for all a1 : : : an 2 R. Let B = hR(x1 : : : xn ) + 0 1i be the eld of \rational functions". Note that B contains the reduct of R to f+ 0 1g as a subeld, where R is dened as in Example 3 as the usual real numbers. By Lemma 12, if p is not the sum of squares in B, then we can nd an ordering
Hilbert also asked: If the coecients of a positive denite rational function are rational numbers (i.e. it is an element of Q (x1 : : : xn )) is it in fact the sum of squares of elements of Q (x1 : : : xn )? < 0 1i be The answer is \yes" and the proof is very similar. Let Q = hQ + : < the ordered eld of rationals as in Example 3. Lemma 12 holds for A = Q and B = hQ (x1 : : : xn ) + 0 1 i by Lemma 11 every positive rational number is the sum of squares since every positive integer is the sum of squares n = 1 + 1 + + 1. Exercise 23. Finish the answer to Hilbert's question by making any appropriate changes to the proof of the corollary. Hint: create an ordering on R(x1 : : : xn ) so that B0 and R are each submodels.
CHAPTER 6
Submodel Completeness Definition 30. A theory T is said to admit elimination of quanti ers in L whenever for each formula '(v0 : : : vp ) of L there is a quantier free formula (v0 : : : vp ) such that: T j= (8v0 : : : 8vp )('(v0 : : : vp ) $ (v0 : : : vp )) Remark. There is a ne point with regard to the above denition. If ' is actually a sentence of L there are no free variables v0 : : : vp . So T j= ' $ for some quantier free formula with no free variables. But if L has no constant symbols, there are no quantier free formulas with no free variables. For this reason we assume that L has at least one constant symbol, or we restrict to those formulas ' with at least one free variable. This will become relevant in the proof of Theorem 17 for (2) ) (3). Exercise 24. If T admits elimination of quantiers in L and L has no constant symbols, show that for each sentence of L there is a quantier free formula (v0 ) such that T j= $ 8v0 $ 9v0 Definition 31. A theory T is said to be submodel complete whenever T 4A is complete in LA for each submodel A of a model of T . Exercise 25. Use Theorem 14 and the following theorem to nd four proofs that every submodel complete theory is model complete. Theorem 17. Let T be a theory of a language L. The following are equivalent: (1) T is submodel complete (2) If B and C are models of T and A is a submodel of both B and C, then every existential sentence which holds in BA also holds in CA . (3) T admits elimination of quanti ers (4) whenever A B, A C, B j= T and C j= T there is a model D such that both BA and CA are elementarily embedded in DA . Proof. (1) ) (2) Let B j= T and C j= T with A B and A C. Then BA j= T 4A and CA j= T 4A. So (1) and Lemma 6 give BA CA . Thus (2) is in fact proved for all sentences, not just existential ones. (2) ) (3) Lemma 4 shows that it suces to prove (3) for formulas in prenex normal form. We do this by induction on the prenex rank of '. This claim is the rst step. Claim. For each existential formula '(v0 : : : vp ) of L there is a quanti er free formula '(v0 : : : vp ) such that T j= (8v0 : : : 8vp )(' $ ) 45
6. SUBMODEL COMPLETENESS
46
Proof of Claim. Add new constant symbols c0 : : : cp to L to form L = L fc0 : : : cp g
and to form a sentence ' of L obtained by replacing each instance of vi in ' with the corresponding ci ' is an existential sentence. It suces to prove that there is a quantier free sentence of L such that T j= ' $ : Let S = f quantier free sentences of L : T j= ' ! g: It suces to nd some in S such that T j= ! ' . Since a nite conjunction of sentences of S is also in S , it suces to nd 1 : : : n in S such that T j= 1 ^ ^ n ! ' : If no such nite subset f1 : : : n g of S exists, then each T f1 : : : n g f:' g
would be satisable. So it suces to prove that T S j= ' . Let C j= T S with the intent of proving that C j= ' . Let A be the least submodel of C in the sense of the language L . That is, every element of A is the interpretation of a constant symbol from L fc0 : : : cp g or built from these using the functions of C. We can ensure that L LA . Let P = f of 4A : is a sentence of L g: We wish to show that T f' g P is satisable. By compactness, it suces to consider T f' g where is a sentence in P . If this set is not satisable then T j= ' ! : so that by denition of S we have : 2 S and hence C j= : . But this is impossible since A C means that CA j= 4A. Let B0 j= T f' g P . The interpretations of fc0 : : : cp g generate a submodel of B0 isomorphic to A. So there is a model B for L such that B = B0 and A B. In order to invoke (2) we use the restrictions AjL, BjL and CjL of A, B and C to the language L. We have BjL j= T , CjL j= T , AjL BjL and AjL CjL. ' is an existential sentence of L LA and since B0 j= ' we have (BjL)A j= ' . So by (2), (CjL)A j= ' and nally C j= ' which completes the proof of the claim. We now do the general cases for the proof of the induction on prenex rank. There are two cases, corresponding to the two methods available for increasing the number of alternations of quantiers: (a) the addition of universal quantiers (b) the addition of existential quantiers. For case (a), suppose '(v0 : : : vp ) is 8w0 : : : 8wm(v0 : : : vp w0 : : : wm ) and has prenex rank lower than '. Then : also has prenex rank lower than ' and we can use the inductive hypothesis on : to obtain a quantier free formula 1 (v0 : : : vp w0 : : : wm ) such that T j= (8v0 : : : 8vp )(8w0 : : : 8wm )(: $ 1 ) So T j= (8v0 : : : 8vp )(9w0 : : : 9wm : $ 9w0 : : : 9wm 1 )
6. SUBMODEL COMPLETENESS
47
By the claim there is a quantier free formula 2 (v0 : : : vp ) such that T j= (8v0 : : : 8vp )(9w0 : : : 9wm 1 $ 2 ) So T j= (8v0 : : : 8vp )(9w0 : : : 9wm : $ 2 ) So T j= (8v0 : : : 8vp )(8w0 : : : 8wm $ :2 ) and so :2 is the quantier free formula equivalent to '. For case (b), suppose '(v0 : : : vp ) is 9w0 : : : 9wm (v0 : : : vp w0 : : : wm ) and has prenex rank lower than '. We use the inductive hypothesis on to obtain a quantier free formula 1 (v0 : : : vp w0 : : : wm ) such that T j= (8v0 : : : 8vp )(8w0 : : : 8wm )( $ 1 ) So T j= (8v0 : : : 8vp )(9w0 : : : 9wm $ 9w0 : : : 9wm 1 ) By the claim there is a quantier free formula 2 (v0 : : : vp ) such that T j= (8v0 : : : 8vp )(9w0 : : : 9wm 1 $ 2 ) So T j= (8v0 : : : 8vp )(9w0 : : : 9wm $ 2 ) and so 2 is the quantier free formula equivalent to '. This completes the proof. (3) ) (4) Let A B, A C, B j= T and C j= T . Using the Elementary Diagram Lemma it will suce to show that Th(BB ) Th(CC ) is satisable. Without loss of generosity, we can ensure that LB \ LC = LA . By the Robinson Consistency Theorem, it suces to show that there is no sentence of LA such that both: Th(BB ) j= and Th(CC ) j= : Suppose is such a sentence, Th(BB ) j= . Let fca0 : : : cap g be the set of constant symbols from LA n L appearing in . Let '(v0 : : : vp ) be obtained from by exchanging each cai for a new variable ui . Let (v0 : : : vp ) be the quantier free formula from (3): T j= (8v0 : : : 8vp )(' $ ) Let be the result of substituting cai for each ui in . is also quantier free. Since BB j= , B j= 'a0 : : : ap ]. Since B j= T , B j= a0 : : : ap ] and so BA j= . Since is quantier free and AA BA we have AA j= since AA CA we then get that CA j= . Hence C j= a0 : : : ap ] and then since C j= T we then get that C j= 'a0 : : : ap ]. But then this means that CA j= and so CC j= so is in Th(CC ) and we are done. (4) ) (1) Let B j= T and A B we show that T 4A is complete. Noting that BA j= T 4A , we see that it suces by Lemma 6 to show that BA C0 for each C0 j= T 4A . For each such C0 , by the Diagram Lemma, there is a model C for L such that A C and CA = C0 . Then C j= T so by (4) there is a D into which both BA and CA are elementarily embedded. In particular BA DA CA so we are done. Example 11. (Chang and Keisler) Let T be the theory in the language L = fU V W R S g where U , V and W are
6. SUBMODEL COMPLETENESS
48
unary relation symbols and R and S are binary relation symbols having axioms which state that there are innitely many things, that U V W is everything, that U , V and W are pairwise disjoint, that R is a one-to-one function from U onto V and that S is a one-to-one function from U V onto W . Exercise 26. Show that T above is complete and model complete but not submodel complete. Hints: For completeness, use the L os-Vaught test and for model completeness use Lindstrom's test. For submodel completeness use (2) of the theorem with B j= T and A B where a 2 A = fb 2 B : B j= W (v0 )b]g along with the sentence (9v0 )(U (v0 ) ^ S (v0 ca )): Remark. We will prove that each of the following theories admits elimination of quantiers: 1. dense linear orders with no end points (DLO) 2. algebraically closed elds (ACF) 3. real closed ordered elds (RCF) C. H. Langford proved elimination of quantiers for DLO in 1924. The cases of ACF and RCF were more dicult and were done by A. Tarski. Thus, by Exercise 25, we will have model completeness of RCF which was promised at the beginning of Chapter 5. Exercise 27. Use part (4) of the previous theorem and the fact that RCF admits elimination of quantiers to prove that RCF is complete another result originally due to A. Tarski. Hint: Show that Q of Example 3 can be isomorphically embedded into any real closed eld and then use (4) from Theorem 17. Exercise 28. Let T be the theory DLO in the language L = f< c1 c2 g where c1 and c2 are constant symbols. Use the fact that DLO admits elimination of quantiers in its own language f
6. SUBMODEL COMPLETENESS
49
As an application of quantier elimination of RCF we have: Corollary 8. (The Tarski-Seidenberg Theorem) The projection of a semi-algebraic set in Rn to Rm for m < n is also semialgebraic. The semi-algebraic sets of Rn are de ned to be all those subsets of Rn which can be obtained by repeatedly taking unions and intersections of sets of the form fhx1 : : : xn i 2 Rn : p(x1 : : : xn ) = 0g and fhx1 : : : xn i 2 Rn : q(x1 : : : xn ) < 0g where p and q are polynomials with real coe cients. Proof. We rst need two simple results which we state as exercises. Let L be the language of RCF augumented with a constant symbol for each element of the reals R. Let T be RCF considered as a theory in this language. Exercise 29. T admits elimination of quantiers as a theory in the language L . < 0 1i be the usual model of the reals then RR is a model Let R = hR + < for the language L . Exercise 30. A set X Rn is semi-algebraic i there is a quantier free formula '(v1 : : : vn ) of L such that X = fhx1 : : : xn i : RR j= 'x1 : : : xn ]g: Now, in order to prove the corollary, let X Rn be semi-algebraic and let ' be its associated quantier free formula. The projection Y of X into Rm is Y = fhx1 : : : xm i : 9wm+1 : : : 9wn hx1 : : : xm xm+1 : : : xn i 2 X g = fhx1 : : : xm i : RR j= 9vm+1 : : : 9vn 'x1 : : : xm ]g Since T admits elimination of quantiers, there is a quantier free formula of L such that T j= (8v1 : : : 8vm )(9vm+1 : : : 9vn ' $ ) So RR j= 9vm+1 : : : 9vn 'x1 : : : xm ] i RR j= x1 : : : xm ]: So Y = fhx1 : : : xm i : RR j= x1 : : : xm ]g and by the exercise, Y is semi-algebraic.
CHAPTER 7
Model Completions Closely related to the notions of model completeness and submodel completeness is the idea of a model completion. Definition 32. Let T T be two theories in a language L. T is said to be a model completion of T whenever T 4A is satisable and complete in LA for each model A of T . Lemma 14. Let T be a theory in a language L. (1) If T is a model completion of T , then for each A j= T there is a B j= T such that A B. (2) If T is a model completion of T , then T is model complete. (3) If T is model complete, then it is a model completion of itself. (4) If T1 and T2 are both model completions of T , then T1 j= T2 and T2 j= T1 . Proof. (1) Easy. Just use the diagram lemma and the word \satisable" in the denition of model completion. (2) Easier. (3) Easiest. (4) This needs a proof. Let A j= T2 . It will suce to prove that A j= T1 . Let A0 = A. since A0 j= T and T1 is a model completion of T we obtain, from (1), a model A1 j= T1 such that A0 A1. Similarly, since A1 j= T and T2 is a model completion of T we obtain A2 j= T2 such that A1 A2 . Continuing in this manner we obtain a chain: A0 A1 A2 : : : An An+1
Let B be the union of the chain, fAn : n 2 N g. Each even A2n j= T2 . By (2) and (4) of Theorem 14 we get that for each n, A2n A2n+2 and by the Elementary Chain Theorem A0 B. Similarly A1 B. so A0 A1 and hence A j= T1 . Remark. Part (4) of the above lemma shows that model completions are essentially unique. That is, if model completions T1 and T2 of T are closed theories in the sense of Denition 12 then T1 = T2 . Since there is no loss in assuming that model completions are closed theories, we speak of the model completion of a theory T . Lemma 15. If T T are theories for a language L such that for each A j= T there is a B j= T such that A B, then the following are equivalent: (1) T is the model completion of T . (2) For each A j= T , B j= T and C j= T such that A B and A C we have a model D such that both BA and CA are elementarily embedded into DA . 50
7. MODEL COMPLETIONS
51
(3) For each A j= T , B j= T and C j= T such that A B and A C we have a model D such that BA DA and CA is elementarily embedded into DA . (4) For each A j= T , B j= T and C j= T such that A B and A C we have a model D such that BA is isomorphically embedded into DA and C D. Proof. (1) ) (2) By the Elementary Diagram Lemma it suces to prove that the union of the elementary diagrams of BA and CA , is satisable. By the Robinson Consistency Theorem it suces to show that there is no sentence of LA such that ThBA j= and ThCA j= : . Indeed, if ThBA j= then BA j= . Now T 4A is a complete theory in LA and both BA j= T 4A and CA j= T 4A so BA CA . Therefore CA j= and hence is in ThCA . (2) ) (3) and (3) ) (4) easily follow from the denitions. (4) ) (1) We rst show that T is model complete using Theorem 14 we show that T is existentially complete. Let A j= T we show that A is existentially closed. Let B j= T such that A B and let be an existential sentence of LA with BA j= our aim is to prove that AA j= . We invoke (4) with C = A to get a model D such that A D and an isomorphic embedding f : BA ! DA . Since is existential it is of the form 9v0 : : : 9vp ' for some quantier free formula '(v0 : : : vp ) of LA . BA j= 9v0 : : : 9vp ' So for some b0 : : : bp in B we have BA j= 'b0 : : : bp ]: By Exercises 8 and 18 we have DA j= 'f (b0 ) : : : f (bp )] and so DA j= 9v0 : : : 9vp ': Now A D implies that AA DA so AA j= 9v0 : : : 9vp ': Hence AA j= and T is model complete. We now show that T is the model completion of T . Let A j= T by the hypothesis on T and T we have that T 4A is satisable. We show that T 4A is complete in LA by showing that for each B j= T and C j= T with A B and A C we have BA CA . Letting B and C be as above, we invoke (4) to obtain a model D such that BA is isomorphically embedded into DA and C D. C D gives that D j= T . The isomorphic embedding gives us a model E such that B E and DA = EA . So E j= T . Using model completeness of T and Theorem 14 we can conclude that B E. We have: BA EA DA CA and we are done. Let's compare the denitions of model completion and submodel complete. Let T be the model completion of T . Then T will be submodel complete provided
7. MODEL COMPLETIONS
52
that every submodel of a model of T is a model of T . Unfortunately this is not always the case. However this seems like a promising approach to show submodel completeness (and hence elimination of quantiers) of some theories T | we just need to show that T is the model completion of some theory T and T has the property that every submodel of a model of T is also a model of T . Since T T , it would be enough to show that every submodel of a model of T is again a model of T . And this is indeed the case whenever T is a universal theory, that is, whenever T has a set of axioms consisting of universal sentences. Our ultimate aim is to show that DLO, ACF and RCF are submodel complete. We will in fact show that these theories are the model completions of LOR, FEI and ORF respectively. See Example 5 to recall the axioms for these theories. Now LOR is a universal theory but FEI and ORF are not. The culprits are the existence axioms for inverses: 8x9y (x + y = 0) and 8x9y (y x = 1) In fact, a submodel A of a eld B is only a commutative ring, not necessarily a subeld. Nevertheless, A generates a subeld of B in a unique way. This motivates the following denition. Definition 33. A theory T is said to be almost universal whenever A B, B j= T and A C, C j= T imply there are models D and E such that D j= T , A D B and E j= T , A E C and DA = EA . Example 12. LOR is almost universal since any universal theory T is almost universal | just let D = E = A and note A j= T . Example 13. FEI is almost universal | just let D and E be the subelds of B and C, respectively, generated by A. The isomorphism DA = EA is the natural one obtained from the identity map on A. Example 14. ORF is almost universal | again just let D and E be the ordered subelds of B and C, respectively, generated by A. The extension of the identity map on A to the isomorphism DA = EA is aided by the fact that the order placement of the inverse of an element a is completely determined by the order placement of a. Theorem 18. Let T and T be theories of the language L such that T is almost universal and T is the model completion of T . Then T is submodel complete. Proof. We show that condition (2) of Theorem 17 is satised. Let B and C be models of T with A a submodel of both B and C. We will show that, in fact, BA CA . Now T T so B j= T and C j= T . Since T is almost universal there are models D and E of T such that A D B, A E C and DA = EA . So BD j= T 4D and CE j= T 4E. Now BD is a model for the language LD whereas CE is a model for LE . We wish to obtain a model C0 for LD which \looks exactly like" CE . We just let C0 be C and in fact let C0 jLA = CE jLA . The interpretation of a constant symbol cd 2 LD n LA is the interpretation of ce 2 LE n LA in CE where the isomorphism DA = EA takes d to e.
7. MODEL COMPLETIONS
53
Now D j= T and since T is the model completion of T , T 4D is complete. The isomorphism DA = EA ensures that C0 j= T 4D. So BD C0 . Hence 0 BD jLA C jLA that is, BA CA . The way to show that DLO, ACF and RCF admit elimination of quantiers is now clear. We will use Theorem 17 and 18. This reduces to showing that DLO, ACF and RCF are the model completions of LOR, FEI and ORF respectively. To do this we will use Lemma 15, so we rst need to show that each pair of these theories satisfy the general hypothesis of Lemma 15: if A j= T then there is a B j= T such that A B. For the case T = LOR and T = DLO is easy every linear order can be enlarged to a dense linear order without endpoints by judiciously placing copies of the rationals into the linear order. The case T = FEI and T = ACF is just the well known fact that every eld has an algebraic closure. The case T = ORF and T = RCF is just Lemma 13. So all that remains of the quest to prove elimination of quantiers for DLO, ACF and RCF is to verify condition (4) of Lemma 15 in each of these cases. We rephrase this condition slightly as: For each A j= T , B j= T and C j= T with A B and A C there is a D such that C D and an isomorphic embedding f : B ,! D such that f A is the identity on A. At this point the reader may already be able to verify this condition for one or more of the pairs T = LOR and T = DLO, T = FEI and T = ACF, or T = ORF and T = RCF. However the remainder of this chapter is devoted to a uniform method. Definition 34. Let L be a language and (v0 ) a set of formulas of L in the free variable v0 . A model A for L is said to realize (v0 ) whenever there is some a 2 A such that A j= 'a] for each '(v0 ) in (v0 ). Definition 35. The set of formulas (v0 ) in the free variable v0 , is said to be a type of the model A whenever (1) every nite subset of (v0 ) is realized by A (2) (v0 ) is maximal with respect to (1). Remark. Every set of formulas (v0 ) having property (1) of the denition of type can be enlarged to also have property (2). Lemma 16. Suppose A is an in nite model for a language L. Let X A and let (v0 ) be a type of AX in the language LX . Then there is a B such that A B and BX realizes (v0 ). Proof. Let T = ThAA (c) where c is a new constant symbol and (c) = f'(c) : ' 2 (v0 )g and of course '(c) is '(v0 ) with c replacing v0 . By denition of type, for each nite T 0 T , there is an expansion A0 of A such that A0 j= T 0 . The Elementary Diagram Lemma and the Compactness Theorem will complete the proof.
7. MODEL COMPLETIONS
54
Lemma 17. Suppose A is an in nite model for a language L. There is a model B for L such that A B and BA realizes each type of AA in the language LA . Proof. Let f (v0 ) : 2 I g enumerate all types of AA in the language LA . For each 2 I introduce a new constant symbol c and let (c ) = f'(c ) : ' 2 (v0 )g: Let = f (c ) : 2 I g. Let 0 be any nite subset. Claim. 0 ThAA is satis able for the language LA fc : 2 I g. Proof of Claim. Let 1 (v0 ) : : : n (v0 ) be nitely many types such that 0 1 (c0 ) 2 (c1 ) n (c n ): By Lemma 16 there is a model A1 such that A A1 and (A1 )A realizes 1 (v0 ). Using Lemma 16 repeatedly, we can obtain A A1 A2 An such that each (Aj )A realizes j (v0 ). Now A An so (An )A j= ThAA . It is easy to check that since each Aj An, An realizes each j (v0 ) and furthermore so does (An )A . So we can expand (An )A to the language LA fc 1 : : : c n g to satisfy 0 ThAA .
By the claim and the Compactness Theorem, there is a model C j= ThAA . By the Elementary Diagram Lemma, A is elementarily embedded into CjL, the restriction of C to the language L. Therefore there is a model B for L such that A B and BA = CjLA . It is now straightforward to check that BA realizes each type (v0 ). Definition 36. A model A for L is said to be -saturated whenever we have that for each X A with jX j < , AX realizes each type of AX . Recall that + is dened to be the cardinal number just larger than . So a model A will be + -saturated whenever we have that for each X A with jX j , AX realizes each type of AX . In particular, if B is any innite set, A will be jB j+ saturated whenever we have that for each X A with jX j jB j, AX realizes each type of AX . Remark. A model A is said to be saturated whenever it is jAj-saturated, < i is saturated to where jAj is the size of the universe of A. For example, hQ < < iX . By prove this let X be a nite subset of Q and let (v0 ) be a type of hQ < Lemma 16 and the Downward Lowenheim-Skolem Theorem get a countable B such < iX BX and B realizes (v0 ). Use the hint for Exercise 11 to show that that hQ < < iX < iX . hQ < = BX and then note that this means that (v0 ) is realized in hQ < Lemma 18. (R. Vaught) Suppose C is an in nite model for L and B is an in nite set. There is a jBj+ saturated model D such that C D.
7. MODEL COMPLETIONS
55
Proof. We build an elementary chain
C = C0 C1 C2 Cn n 2 N such that for each n 2 N (Cn+1 )Cn realizes each type of (Cn )Cn . This comes immediately by repeatedly applying Lemma 17. Let D be the union of the chain the Elementary Chain Theorem assures us that C D and indeed each Cn D. Let X D with jX j jBj and let (v0 ) be a type of DX . If X Cn for some n, then (v0 ) is a type of (Cn )X since (Cn )X DX . Now (v0 ) can be enlarged to a type of (Cn )Cn which is realized in (Cn+1 )Cn and so (v0 ) is realized in (Cn+1 )Cn . Since (Cn+1 )Cn DCn , we can easily check that (v0 ) is realized in DCn . Since (v0 ) involves only constant symbols associated with X , we have that DX realizes (v0 ). We have almost proved that D is jBj+ -saturated, but not quite, because there is no guarantee that if X D = fCn : n 2 N g and jX j jBj, then X Cn for some n. However, there would be no problem if X was nite. The problem with innite X is that the elementary chain is not long enough to catch X . The solution is to upgrade the notion of an elementary chain to include chains which are indexed by any well ordered set, not just the natural numbers. We sketch < i to the the appropriate generalization of the above argument from the case of hN < case of an arbitrary well ordered set hI
2 I with < . The union of the chain up to E = fC : 2 I and < g falls under the scope of an upgraded Elementary Chain Theorem (which is proved exactly as Theorem 4) and so C E for each 2 I with < . We now use Lemma 17 as before to get C such that E C and (C )E realizes each type of EE . As before, let D = fC : 2 I g be the union of the entire chain and by the upgraded Elementary Chain Theorem C D. Also as before, DX realizes each type of DX for each X D such that X C for some 2 I . But now we can complete the proof of the lemma by choosing a well ordered set hI jBj. Definition 37. We say that B is a simple extension of A whenever
1. A B and 2. there is some b 2 B such that no properly smaller submodel of B contains A fbg.
7. MODEL COMPLETIONS
56
Theorem 19. (Blum's Test) Suppose T T are theories of a language L. Suppose further that: (1) T is an almost universal theory (2) every model of T can be extended to a model of T and (3) for each A j= T , B a submodel of a model of T , C j= T such that C is jBj+ saturated, A C and B is a simple extension of A, there is an isomorphic embedding f : B ! C such that f A is the identity on A. Then: (4) for each A j= T , B j= T and C j= T with A B and A C there is a model D such that C D and an isomorphic embedding f : B ! D such that f A is the identity on A, (5) T is the model completion of T and (6) T admits elimination of quanti ers. Proof. Because of Lemma 15, Theorem 17 and Theorem 18, (5) and (6) follow from (1), (2) and (4). We will therefore only need to prove (4). Let A, B and C be as in (4). Using Lemma 18 we obtain a jBj+ -saturated model D such that C D. We wish to nd an isomorphic embedding f : B ,! D which is the identity on A. Let f be a maximal element of fg : for some B0 B g is an isomorphic embedding from B0 into D such that g A is the identity on Ag in the sense that no other such g properly extends f . We will prove that this f satises condition (4). The proof is by contradiction suppose f : B0 ,! D and B0 6= B. Claim. There is a model G such that B0 G B, G j= T and a model H such that G H and an isomorphism j : H ! D such that j B0 = f . Proof of Claim. From the isomorphic embedding f : B0 ,! D we get a model E such that B0 E and an isomorphism e : E ! D such that e B0 = f . We have B0 E and B0 B with both E j= T and B j= T . By condition (1) there are models F and G of T such that B0 F E, B0 G B and FB0 = GB0 . This gives an isomorphic embedding g : G ,! E such that g B0 is the identity map. From g we get a model H such that G H and an isomorphism h : H ! E such that h G = g. Now let j = e h. Thus j is an isomorphism from H to D such that j B0 = e h B0 = e g B0 = e B0 = f which nishes the proof of the claim.
Once we have the claim, there are two cases: G 6= B and G = B. For the case G 6= B, there must be some b 2 B n G and we use b to form the simple extension B00 of G by b. Now use condition (3) on G, B00 and H to obtain an embedding k : B00 ,! H which is the identity map on G. Now j k extends f , which is a contradiction. For the case G = B, the function j G extends f and gives the contradiction.
7. MODEL COMPLETIONS
57
The following lemma completes the proofs that each of the theories DLO, ACF and RCF admit elimination of quantiers. Lemma 19. Each of the following three pairs of theories T and T satisfy condition (3) of Blum's Test. (1) T = LOR theory of linear orderings. T = DLO, theory of dense linear orderings without endpoints. (2) T = FEI, theory of elds. T = ACF, theory of algebraically closed elds. (3) T = ORF, theory of ordered elds. T = RCF, theory of real closed elds. Proof of (1). Let A and B be linear orders, with B = A fbg and A B. Let C be a jBj+ -saturated dense linear order without endpoints with A C. We wish to nd an isomorphic embedding f : B ! C which is the identity on A. Consider a type of CA containing the following formulas: ca < v0 for each a 2 A such that a < b v0 < ca for each a 2 A such that b < a Since C is a dense linear order without endpoints each nite subset of the type can be realized in CA . Saturation now gives some t 2 C realizing this type. We set f (b) = t and we are nished. Proof of (2). Let A be a eld and B a simple extension of A witnessed by b such that B is a submodel of a eld (a commutative ring). Let C be a jBj+ -saturated algebraically closed eld such that A C. We wish to nd an isomorphic embedding f : B ! C which is the identity on A. There are two cases: (I) b is algebraic over A, (II) b is transcedental over A. Case(I). Let p be a polynomial with coecients from A such that p(b) = 0 but b is not the root of any such polynomial of lower degree. Since C is algebraically closed there is a t 2 C such that p(t) = 0. We extend the identity map f on A to make f (b) = t. We extend f to the rest of B by letting f (r(b)) = r(t) for any polynomial r with coecients from A. It is straightforward to show that f is still a well-dened isomorphic embedding. las:
Case (II). Let us consider a type of CA containing the following set of formuf:(p(v0 ) = 0)g
where p is a polynomial with coecients in fca : a 2 Ag. Since C is algebraically closed, it is innite and hence each nite subset is realized in CA . Saturation will now give some t 2 C such that t realizes the type. We set f (b) = t. Since t is transcedental over A, the extension of f to all of B comes easily from the fact that every element of B n A is the value at b of some polynomial function with coecients from A.
7. MODEL COMPLETIONS
58
Proof of (3). Let A be an ordered eld and B be a simple extension of A witnessed by b such that B is a submodel of an ordered eld (an ordered commutative ring). Let C be a jBj+ -saturated real closed eld such that A C. We wish to nd an isomorphic embedding f : B ! C which is the identity on A. There are two cases: (I) b is algebraic over A. (II) b is transcedental over A. Case (I). Since b is algebraic over A we have a polynomial p with coecients in A such that p(b) = 0. All other elements of the universe of the simple extension B are of the form q(b) where q is a polynomial with coecients in A. Before beginning the main part of the proof we need some algebraic facts. Claim. Let D be a real closed ordered eld and q(x) be a polynomial over D of degree n. Then for any e 2 D we have: n q (m) (e) X (x ; e)m q(x) = m ! m=0
where q(m) stands for the polynomial which is the m-th derivative of q. Proof of Claim. This is Taylor's Theorem from Calculus unfortunately we cannot use Calculus to prove it because we are in D, not necessarily the reals R. However the reader can check that the Binomial Theorem gives the identity for the special cases of q(x) = xn and that these special cases readily give the full result.
Claim. Let D be a real closed ordered eld and q(x) a polynomial over D with e 2 D and q(e) = 0. If there is an a < e such that q(x) > 0 for all a < x < e then q0 (e) 0. If there is an a > e such that q(x) > 0 for all e < x < a then q0 (e) 0. Here q0 is the rst derivative of q. Proof of Claim. From the previous claim we get ! n q (m) (e) q(x) ; q(e) = q0 (e) + (x ; e) X m ; 2 (x ; e) x;e m=2 m!
for any x 6= e in D. By choosing x close enough to e we can ensure that the entire right hand side has the same sign as q0 (e). A proof by contradiction now follows readily. Claim. Let D be a real closed ordered eld and q(x) be a polynomial over D with e 2 D and q(e) = 0. If w and z are in D such that w < e < z and q(w) q(z ) > 0 then there is a d in D such that w < d < z and q0 (d) = 0.
7. MODEL COMPLETIONS
59
Proof of Claim. Without loss of generosity q(w) > 0 and q(z ) > 0. Since q has only nitely many roots, we can pick d1 to be the least x such that w < x e and q(x) = 0. Since q(x) 6= 0 for all w < x < d1 , the Intermediate Value Property of Real Closed Ordered Fields shows that q cannot change sign here and so q(x) > 0 for all w < x < d1 . By the previous claim, q0 (d1 ) 0. A similar argument with z shows that there is a d2 such that e d2 < z and q0 (d2 ) 0. If d1 = e = d2 take d = e. If d1 < d2 the Intermediate Value Property gives a d with the required properties. Claim. Let D be a real closed ordered eld with an ordered eld E D. Let f : E ! C be an isomorphic embedding into a real closed ordered eld. Let q be a polynomial with coe cients in E such that fx 2 D : q0 (x) = 0g E. Let d 2 D n E be such that q(d) = 0 but d is not a root of a polynomial with coe cients from E which has lower degree. Then f can be extended over the sub eld of D generated by E fdg. Proof of Claim. Since the nitely many roots of q0 from D actually lie in E, we can get e1 and e2 in E such that e1 < d < e2 and q0(x) 6= 0 for all x in D such that e1 < x < e2 . Furthermore for all x in E we have q(x) 6= 0. We can now apply the previous claim to get that q(w) q(z ) < 0 for all w and z in E such that e1 < w < d < z < e2 . We now move to the real closed ordered eld C and the isomorphic embedding f . For each w and z in E such that e1 < w < d < z < e2 we have f (w) < f (z ) and q(f (w)) q(f (z )) < 0. By the Intermediate Value property of C we get, for each such w and z , a y 2 C such that f (w) < y < f (z ) and q(y) = 0. Since q has only nitely many roots there is some t 2 C such that q(t) = 0, f (w) < t for all e1 < w < d and t < f (z ) for all d < z < e2 . We now extend f by letting f (d) = t and f (r(d)) = r(t) for any polynomial r with coecients from E. It is straightforward to check that the extension is a well-dened isomorphic embedding of the simple extension of E by d into C. We
use the fact that ORF is almost universal to extend the isomorphic embedding to all of the subeld of D generated by E fdg, since we can rephrase the denition of almost universal as follows: Whenever C j= T , D j= T , E0 D and f : E0 ,! C is an isomorphic embedding, then there is a model E00 j= T such that E0 E00 D and f extends over E00 .
It is now time for the main part of the proof of this case. Using Lemma 13, let D be a real closed ordered eld with B D. We have a polynomial p with coecients from A such that p(b) = 0. By induction on the degree of p, we can show that there is a sequence of elements d0 : : : dm = b of elements of D, a sequence of subelds of D: A = E0 E1 : : : Em+1 with each dj 2 Ej+1 n Ej and corresponding isomorphic embeddings fj : Ej ! C
7. MODEL COMPLETIONS
60
coming from the previous claim and having the property that f0 is the identity and fj+1 extends fj . In this way we extend the identity map f0 : A0 ,! C until we reach fm+1 : Em+1 ,! C. We then note that since b 2 Em+1 we have B Em+1 and we are nished. Case (II). Let us consider a type of CA containing the following formulas: ca < v0 for all a 2 A with a < b
CA .
v0 < ca for all a 2 A with b < a :(p(v0 ) = 0) for all polynomials p with coecients in fca : a 2 Ag Since each interval of C is innite, each nite subset of this type is realized by
Saturation now gives t 2 C which realizes this type. We put f (b) = t. We can now extend f on the rest of B n A, since each such element is the value at b of a polynomial function with coecients from A.
Question. Suppose K is the reduct of p a real closed ordered eld to the language of eld theory. Can you show that K ;1] is algebraically closed using Model Theory and the Fundamental Theorem of Algebra?
Bibliography 1. J. Barwise (ed.), Handbook of Mathematical Logic, North Holland, 1997. 2. J. L. Bell and A. B. Slomson, Models and Ultraproducts, North Holland, 1969. 3. Felix E. Browder (ed.), Mathematical developments arising from Hilbert's problems, Proceedings of Symposia in Pure Mathematics, vol. XXVIII - Parts 1 and II, AMS, 1976. 4. S. Buechler, Essential Stability Theory, Perspectives in Mathematical Logic, Springer, 1996. 5. C. C. Chang and H. J. Keisler, Model Theory, second ed., North Holland, 1977. 6. G. Cherlin, Model Theoretic Algebra, Selected Topics, LNM521, Springer-Verlag, 1976. 7. N. Jacobson, Basic Algebra I, W. H. Freeman, 1985. 8. H. J. Keisler, Foundations of Innitesimal Calculus, Prindle, Weber and Schmidt, 1976. 9. M. D. Morley (ed.), Studies in Model Theory, MAA Studies in Mathematics, MAA, 1973. 10. A. Robinson, Introduction to Model Theory and the Metamathematics of Algebra, second ed., North-Holland, 1965. 11. , Non Standard Analysis, North Holland, 1966. 12. G. E. Sacks, Saturated Model Theory, W. A. Benjamin Inc., 1972. 13. D. H. Saracino and V. B. Weispfenning (eds.), Model theory and algebra: A Memorial Tribute to Abraham Robinson, LNM498, Springer Verlag, 1975. 14. S. Shelah, Classication Theory and the Numbers of Nonisomorphic models, second ed., North Holland, 1990. 15. J. R. Shoeneld, Mathematical Logic, Addison-Wesley, 1967. 16. A. Tarski, A Descision Method for Elementary Algebra and Geometry, second ed., The Rand Corporation, 1957.
61
Index A B, 18 A = fAn : n 2 Ng, 19 ThA, 14 ThAA , 27 j=, 14 , 18 A jL , 17 , 17 tx0 : : : xq ], 7 hC + 0 1i, 13 hQ << + 0 1i, 13 hR < + 0 1i, 13 hN + < 0 1i, 18 A. Robinson, 35 ACF, 14 submodel complete, 57 algebraically closed elds axioms,theory of, 14 almost universal, 57, 64 axioms, 14 0
elimination of quantiers, 49 existentially closed, 35 expansion language, 17 model, 17 FEI, 14 almost universal, 57 elds axioms,theory of, 14 formula, 5 free variable, 6 isomorphic models, 18 isomorphically embedded model, 27 language, 6 Leibniz Principle, 29 Lindstrom's Test, 38 linear orders axioms,theory of, 14 LOR, 14 almost universal, 57 L os-Vaught Test, 24 Lowenheim-Skolem Theorems Downward, 23 Upward, 23 model, 6 satises, 7 model complete theory, 35 model completion, 55 submodel complete, 57 Number Theory, 18 number theory non-standard models, 18 ordered eld, 45 ordered elds axioms,theory of, 14 ORF, 14 almost universal, 57 prenex normal form, 10 rational numbers, 13 RCF, 14 submodel complete, 57
0
Blum's Test, 60 bound variable, 6 categorical -categorical theory, 24 chain of models, 19 elementary, 19 Compactness Theorem, 17 complete theory, 24 Completeness Theorem, 17 complex, 13 Craig Interpolation Theorem, 33 dense linear orders without endpoints axioms,theory of, 14 diagram lemmas, 27 DLO, 14 submodel complete, 57 elementarily embedded model, 27 elementarily equivalent models, 18 Elementary Chain Theorem, 19 elementary diagram, 27 elementary extension, 18 elementary submodel, 18
62
INDEX
real closed ordered eld, 45 real closed ordered elds axioms, theory, 15 axioms,theory of, 14 Intermediate Value Property, 15 real numbers, 13 realize, 58 reduction language, 17 model, A jL , 17 Robinson Consistency Theorem, 30 satisfaction A j= , 14 saturated -saturated model, 59 sentence, 10 simple extension, 60 subformula, 5 submodel, 18 submodel complete, 49 submodel complete theory, 49 T. Skolem, 18 Tarski's Elementary Chain Theorem, 19 Tarski-Vaught Condition, 21 term, 5 theory, 14 almost universal, 57 model completion, 55 theory of A, 14 type, 58 variable, 5 0
0
63