The Foundations of Mathematics

1 The Foundations of Mathematicsc 2005,2006,2007 Kenneth KunenKenneth KunenOctober 29, 2007 Contents0 Prerequisites .. Logical Notation .. Why Read This Book? .. The Foundations of Mathematics ..5I Set .. Axioms .. Remarks on Presentation.. theory is the theory of everything .. , Comprehension, Pairing, Union .. , Functions, Discrete Mathematics .. Remarks .. and Recursion on the Ordinals .. Power Sets .. Cardinals .. The Axiom of Choice (AC) .. Cardinal Arithmetic .. The Axiom of Foundation .. Real Numbers and Symbolic Entities ..73II Model Theory and Proof Plan .. Historical Introduction to Proof Theory .. NON-Historical Introduction to Model Theory.

2 Polish Notation .. First-Order Logic Syntax .. Abbreviations .. First-Order Logic Semantics .. Further Semantic Notions .. Tautologies .. Formal Proofs .. Some Strategies for Constructing Proofs .. The Completeness Theorem .. More Model Theory .. Equational Varieties and Horn Theories .. Extensions by Definitions .. Elementary Submodels .. Other Proof Theories .. 142 III Recursion Theory143 Bibliography144 chapter PrerequisitesIt is assumed that the reader knows basic undergraduate Mathematics . Specifically:You should feel comfortable thinking about abstract mathematical structures suchas groups and fields. You should also know the basics of calculus, including some of thetheory behind the basics, such as the meaning of limit and thefact that the setRof realnumbers is uncountable, while the setQof rational numbers is should also know the basics of logic, as is used in elementary includes truth tables for boolean expressions, and theuse of predicate logic inmathematics as an abbreviation for more verbose English Logical NotationOrdinary mathematical exposition uses an informal mixtureof English words and logicalnotation.

3 There is nothing deep about such notation; it isjust a convenient abbrevia-tion which sometimes increases clarity (and sometimes doesn t). In chapter II, we shallstudy logical notation in a formal way, but even before we getthere, we shall use logicalnotation frequently, so we comment on it example, when talking about the real numbers, we might say x[x2>4 [x >2 x < 2]],or we might say in English, that for allx, ifx2>4 then eitherx >2 orx < logical notation uses the propositional connectives , , , , to abbreviate,respectively, the English or , and , not , implies , and iff (if and only if). It alsouses thequantifiers, xand xto abbreviate the English for allx and there existsx .Note that when using a quantifier, one must always have in mindsome intendeddomain of discourse, oruniverseover which the variables are ranging.

4 Thus, in the3 chapter 0. INTRODUCTION4above example, whether we use the symbolic x or we say in English, for allx , itis understood that we mean for all real numbersx. It also presumes that the variousfunctions ( x2) and relations ( ,<) mentioned have some understood meaningon this intended domain, and that the various objects mentioned (4 and 2) are in thedomain. !y is shorthand for there is auniquey . For example, again using the realnumbers as our universe, it is true that x[x >0 !y[y2=x y >0]] ;( )that is, every positive number has a unique positive square root. If instead we used therational numbers as our universe, then statement ( ) would be ! could be avoided, since !

5 Y (y) is equvalent to the longer expression y[ (y) z[ (z) z=y]], but since uniqueness statements are so common in math-ematics, it is useful to have some shorthand for ( ) is asentence, meaning that it has no free variables. Thus, if theuniverse is given, then ( ) must be either true or false. The fragment !y[y2=x y >0]is aformula, and makes an assertion about the free variablex; in a given universe, itmay be true of some values ofxand false of others; for example, inR, it is true of 3 andfalse of exposition will often omit quantifiers, and leave it to the reader to fillthem in. For example, when we say that the commutative law,x y=y x, holds inR, we are really asserting the sentence x,y[x y=y x].

6 When we say the equationax+b= 0 can always be solved inR(assuminga6= 0) , we are really asserting that a,b[a6= 0 x[a x+b= 0]].We know to use a a,bbut an xbecause a,b come from the front of the alphabetand x from near the end. Since this book emphasizes logic, we shall try to be moreexplicit about the use of state here for reference the usual truth tables for , , , , :Table 1: Truth Tables TTTTTTTFTFFFFTTFTFFFFFTT TFFTNote that in Mathematics , is always equivalent to . For example,7<8 1 + 1 = 2 and 8<7 1 + 1 = 2 are both true; despite the English renderingCHAPTER 0. INTRODUCTION5of implies , there is no causal connection between 7<8 and the value of 1 + 1. Also,note that or in Mathematics is always inclusive; that is is true if one or both of , are true, unlike the informal English in Stop or I ll shoot!

7 Why Read This Book?This book describes some basic ideas in set theory, model theory, proof theory, andrecursion theory; these are all parts of what is called mathematical logic. There arethree reasons one might want to read about this:1. As an introduction to For its applications in topology, analysis, algebra, AI, Because the Foundations of Mathematics is relevant to If you plan to become a logician, then you will need this material to understandmore advanced work in the Set theory is useful in any area of math dealing with uncountable sets; modeltheory is closely related to algebra. Questions about decidability come up frequently inmath and computer science.

8 Also, areas in computer science such as artificial intelligenceand databases often use notions from model theory and proof The title of this book is Foundations of Mathematics , and there are a numberof philosophical questions about this subject. Whether or not you are interested in thephilosophy, it is a good way to tie together the various topics, so we ll begin with The Foundations of MathematicsThe Foundations of Mathematics involves theaxiomatic method. This means that inmathematics, one writes down axioms and proves theorems from the axioms. The justi-fication for the axioms (why they are interesting, or true in some sense, or worth studying)is part of the motivation, or physics, or philosophy, not part of the Mathematics .

9 Themathematics itself consists of logical deductions from are three examples of the axiomatic method. The first twoshould be knownfrom high school or college 1:Geometry. Theuseof geometry (in measurement, construction, etc.)is prehistoric , and probably evolved independently in various cultures. The axiomaticdevelopment was first (as far as we know) developed by the ancient Greeks from 500 to300 BC, and was described in detail by Euclid around 300 BC. InhisElements[12], helisted axioms and derived theorems from the axioms. We shallnot list all the axioms ofgeometry, because they are complicated and not related to the subject of this book. Onesuch axiom (see Book I, Postulate 1) is that any two distinct points determine a uniqueCHAPTER 0.

10 INTRODUCTION6line. Of course, Euclid said this in Greek, not in English, but we could also say it usinglogical notation, as in Section : x,y[[Point(x) Point(y) x6=y] !z[Line(z) LiesOn(x,z) LiesOn(y,z)]].The intended domain of discourse, or universe, could be all geometric 2:Group Theory. The groupidea, as applied to permutations and alge-braic equations, dates from around 1800 (Ruffini 1799, Abel 1824, Galois 1832). Theaxiomatic treatment is usually attributed to Cayley (1854)(see [4], Vol 8). We shall listall the group axioms because they are simple and will providea useful example for us aswe go on. Agroupis amodel(G; ) for the axiomsGP={ 1, 2}: 1. xyz[x (y z) = (x y) z] 2. u[ x[x u=u x=x] x y[x y=y x=u]]Here, we re saying thatGis a set and is a function fromG GintoGsuch that 1and 2hold inG(with x meaning for allx G , soGis our universe, as discussedin Section ).