William Weiss and Cherie D’Mello - math.toronto.edu

1 Fundamentals of Model TheoryWilliam Weiss and Cherie D MelloDepartment of MathematicsUniversity of Torontoc 2015 and C. D Mello1 IntroductionModel Theory is the part of mathematics which shows how to apply logic tothe study of structures in pure mathematics. On the one hand it is the ultimateabstraction; on the other, it has immediate applications to every-day 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 isinterpreted. This isn t necessarily due to mathematics itself, but is a consequenceof the language that we use to express mathematical at first seems like a deficiency in our language, can actually be shaped intoa powerful tool for understanding mathematics. This book provides an introductionto Model Theory which can be used as a text for a reading course or a summerproject at the senior undergraduate or graduate level.

2 It is also a primer which willgive someone a self contained overview of the subject, before diving into one of themore encyclopedic standard graduate reader who is familiar with the cardinality of a set and the algebraicclosure of a field can proceed without worry. Many readers will have some acquain-tance with elementary logic, but this is not absolutely required, since all necessaryconcepts from logic are reviewed in Chapter 0. Chapter 1 gives the motivating ex-amples; it is short and we recommend that you peruse it first, before studying themore technical aspects of Chapter 0. Chapters 2 and 3 are selections of some of themost important techniques in Model Theory. The remaining chapters investigatethe relationship between Model Theory and the algebra of the real and complexnumbers. Thirty exercises develop familiarity with the definitions and consolidateunderstanding of the main proof the book we present applications which cannot easily be foundelsewhere in such detail.

3 Some are chosen for their value in other areas of mathe-matics: Ramsey s Theorem, the Tarski-Seidenberg Theorem. Some are chosen fortheir immediate appeal to every mathematician: existence of infinitesimals for cal-culus, 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 inthe solution of a problem from high school algebra. In each case, the derivationis shorter than any which tries to avoid logic. More importantly, the methods ofModel Theory display clearly the structure of the main ideas of the proofs, showinghow theorems of logic combine with theorems from other areas of mathematics toproduce stunning theorems here are all are more than thirty years old and due in great partto the cofounders of the subject, Abraham Robinson and Alfred Tarski.

4 However,we have not attempted to give a history. When we attach a name to a theorem, itis simply because that is what mathematical logicians popularly call bibliography contains a number of texts that were helpful in the prepa-ration of this manuscript. They could serve as avenues of further study and inaddition, they contain many other references and historical notes. The more recenttitles were added to show the reader where the subject is moving today. All areworth a book began life as notes for William Weiss s graduate course at the Uni-versity of Toronto. The notes were revised and expanded by Cherie D Mello and2 William Weiss , based upon suggestions from several graduate students. The elec-tronic version of this book may be downloaded and further modified by anyone forthe purpose of learning, provided this paragraph is included in its entirety and solong as no part of this book is sold for 0.

5 Models, Truth and Satisfaction4 Formulas, Sentences, Theories and Axioms4 Prenex Normal Form9 Chapter 1. Notation and Examples11 Chapter 2. Compactness and Elementary Submodels14 The Compactness Theorem14 Isomorphisms, elementary equivalence and complete theories15 The Elementary Chain Theorem16 The L owenheim-Skolem Theorem19 The Lo s-Vaught Test20 Every complex one-to-one polynomial map is onto22 Chapter 3. Diagrams and Embeddings24 Diagram Lemmas25 Every planar graph can be four coloured25 Ramsey s Theorem26 The Leibniz Principle and infinitesimals27 The Robinson Consistency Theorem27 The Craig Interpolation Theorem31 Chapter 4. Model Completeness32 Robinson s Theorem on existentially complete theories32 Lindstr om s Test35 Hilbert s Nullstellensatz37 Chapter 5. The Seventeenth Problem39 Positive definite rational functions are the sums of squares39 Chapter Completeness45 Elimination of quantifiers45 The Tarski-Seidenberg Theorem48 Chapter 7.

6 Model Completions50 Almost universal theories52 Saturated models54 Blum s Test55 Bibliography60 Index613 CHAPTER 0 Models, Truth and SatisfactionWe will use the following symbols: logical symbols: the connectives , , , , called and , or , not , implies and iff respectively the quantifiers , called for all and there exists an infinite collection of variables indexed by the natural numbersNv0,v1,v2, .. the two parentheses ), ( the symbol = which is the usual equal sign constant symbols : often denoted by the lettercwith subscripts function symbols : often denoted by the letterFwith subscripts; eachfunction symbol is an m-placed function symbol for some natural numberm 1 relation symbols : often denoted by the letterRwith subscripts; eachrelational symbol is an n-placed relation symbol for some natural numbern now define terms and defined as follows:(1) a variable is a term(2) a constant symbol is a term(3) ifFis an m-placed function symbol andt1.

7 ,tmare terms, thenF( ) is a term.(4) a string of symbols is a term if and only if it can be shown to be a termby a finite number of applications of (1), (2) and (3). is a recursive defined as follows :(1) ift1andt2are terms, then (t1=t2) is a formula.(2) ifRis an n-placed relation symbol andt1,..,tnare terms, then(R( )) is a formula.(3) if is a formula, then ( ) is a formula(4) if and are formulas then so are ( ), ( ), ( ) and ( )(5) ifviis a variable and is a formula, then ( vi) and ( vi) are formulas(6) a string of symbols is a formula if and only if it can be shown to be aformula by a finite number of applications of (1), (2), (3), (4) and (5). is another recursive definition. is called the negation of ; is called the conjunction of and ; and is called the disjunction of and.

8 40. MODELS, TRUTH AND a formula is defined as follows:(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 ( vi) or ( vi) is a subformula of for some natural numberi,then is also a subformula of (5) A string of symbols is a subformula of , if and only if it can be shown tobe such by a finite number of applications of (1), (2), (3) and (4). variableviis said to occurboundin a formula iff for somesubformula of either ( vi) or ( vi) is a subformula of . In this case eachoccurrence ofviin ( vi) or ( vi) is said to be abound occurrenceofvi. Otheroccurrences ofviwhich do not occur bound in are said to (v3) is a term, whereFis a unary function symbol.(( v3)(v0=v3) ( v0)(v0=v0))is a formula. In this formula the variablev3only occurs bound but the variablev0occurs both bound and the previous definitions as a guide, define the substitutionof a termtfor a variableviin a formula.

9 In particular, demonstrate how tosubstitute the term for the variablev0in the formula of the example a set consisting of all the logical symbols withperhaps some constant, function and/or relational symbols included. It is under-stood that the formulas ofLare made up from this set in the manner prescribedabove. Note that all the formulas ofLare uniquely described by listing only theconstant, function and relation symbols uset(v0,..,vk) to denote a termtall of whose variables occur amongv0,.., use (v0,..,vk) to denote a formula all of whose free variables occuramongv0,.., would be formulas of any language : For any variablevi: (vi=vi) for any termt(v0,..,vk) and other termst1andt2:((t1=t2) (t(v0,..,vi 1,t1,vi+1,..,vk) =t(v0,..,vi 1,t2,vi+1,..,vk))) for any formula (v0,..,vk) and termst1andt2:((t1=t2) ( (v0.)))

10 ,vi 1,t1,vi+1,..,vk) (v0,..,vi 1,t2,vi+1,..,vk)))Note the simple way we denote the substitution (or structure)Afor a languageLis an ordered pair A,I whereAis a nonempty set andIis aninterpretation functionwith domainthe set of all constant, function and relation symbols ofLsuch that:(1) ifcis a constant symbol, thenI(c) A;I(c) is called a constant0. MODELS, TRUTH AND SATISFACTION6(2) ifFis an m-placed function symbol, thenI(F) is an m-placed functiononA(3) ifRis an n-placed relation symbol, thenI(R) is an n-placed relation called theuniverseof the modelA. We generally denote models withGothic letters and their universes with the corresponding Latin letters in set may be involved as a universe with many different interpretation functionsof the languageL. The model isboththe universeandthe interpretation importance of Model Theory lies in the observation that mathe-matical objects can be cast as models for a language.