AN INTRODUCTION TO SET THEORY - University of Toronto

1 AN INTRODUCTION TO SET THEORYP rofessor William A. R. WeissOctober 2, 20082 Contents0 Introduction71 LOST112 FOUND193 The Axioms of Set Theory234 The Natural Numbers315 The Ordinal Numbers416 Relations and Orderings537 Cardinality598 There Is Nothing Real About The Real Numbers659 The Universe7334 CONTENTS10 Reflection7911 Elementary Submodels8912 Constructibility10113 The Axioms of ZFC .. Tentative Axioms .. 118 CONTENTS5 PrefaceThese notes for a graduate course in set THEORY are on their way to be-coming a book. They originated as handwritten notes in a course at theUniversity of Toronto given by Prof. William Weiss. Cynthia Church pro-duced the first electronic copy in December 2002. James Talmage Adamsproduced the copy here in February 2005.

2 Chapters 1 to 9 are close to fi-nal form. Chapters 10, 11, and 12 are quite readable, but should not beconsidered as a final draft. One more chapter will be 0 IntroductionSet THEORY is the true study of infinity. This alone assures the subject of aplace prominent in human culture. But even more, Set THEORY is the milieuin which mathematics takes place today. As such, it is expected to providea firm foundation for the rest of mathematics. And it does up to a point;we will prove theorems shedding light on this the fundamentals of Set THEORY are known to all mathemati-cians, basic problems in the subject seem elementary. Here are three simplestatements about sets and functions. They look like they could appear on ahomework assignment in an undergraduate For any two setsXandY, either there is a one-to-one function fromXintoYor a one-to-one function If there is a one-to-one function fromXintoYand also a one-to-onefunction fromYintoX, then there is a one-to-one function IfXis a subset of the real numbers, then either there is a one-to-onefunction from the set of real numbers intoXor there is a one-to-onefunction fromXinto the set of rational won t appear on an assignment, however, because they are quite dif-78 CHAPTER 0.

3 INTRODUCTION ficult to prove. Statement (2) is true; it is called the Schroder-BernsteinTheorem. The proof , if you haven t seen it before, is quite tricky but never-theless uses only standard ideas from the nineteenth century. Statement (1)is also true, but its proof needed a new concept from the twentieth century,a new axiom called the Axiom of (3) actually was on a homework assignment of sorts. It wasthe first problem in a tremendously influential list of twenty-three problemsposed by David Hilbert to the 1900 meeting of the International Congress ofMathematicians. Statement (3) is a reformulation of the famous ContinuumHypothesis. We don t know if it is true or not, but there is hope that thetwenty-first century will bring a solution.

4 We do know, however, that anothernew axiom will be needed here. All these statements will be discussed laterin the Elementary Set THEORY is well-known and straightforward, themodern subject, Axiomatic Set THEORY , is both conceptually more difficultand more interesting. Complex issues arise in Set THEORY more than anyother area of pure mathematics; in particular, Mathematical logic is used ina fundamental way. Although the necessary logic is presented in this book,it would be beneficial for the reader to have taken a prior course in logicunder the auspices of mathematics, computer science or philosophy. In fact,it would be beneficial for everyone to have had a course in logic , but mostpeople seem to make their way in the world without order to introduce one of the thorny issues, let s consider the set ofall those numbers which can be easily described, say in fewer then twentyEnglish words.

5 This leads to something called Richard s Paradox. The set{x:xis a number which can be describedin fewer than twenty English words}must be finite since there are only finitely many English words. Now, thereare infinitely many counting numbers ( , the natural numbers) and so theremust be some counting number (in fact infinitely many of them) which are notin our set. So there is a smallest counting number which is not in the set. Thisnumber can be uniquely described as the smallest counting number whichcannot be described in fewer than twenty English words . Count them 14words. So the number must beinthe set. But it can t be in the set. That s9a contradiction. What is wrong here?Our naive intuition about sets is wrong here. Not every collection ofnumbers with a description is a set.

6 In fact it would be better to stay awayfrom using languages like English to describe sets. Our first task will be tobuild a new language for describing sets, one in which such contradictionscannot also need to clarify exactly what is meant by set . What is a set?We do not know the complete answer to this question. Many problems arestill unsolved simply because we do not know whether or not certain objectsconstitute a set or not. Most of the proposed new axioms for Set THEORY areof this nature. Nevertheless, there is much that we do know about sets andthis book is the beginning of the 0. INTRODUCTIONC hapter 1 LOSTWe construct a language suitable for describing symbols:variablesv0, v1, v2, ..equality symbol =membership symbol logical connectives , , , , quantifiers , parentheses (,)The atomic formulasare strings of symbols of the form:(vi vj) or (vi=vj)The collection of formulas of set theoryis defined as follows:1.

7 An atomic formula is a If is any formula, then ( ) is also a If and are formulas, then ( ) is also a 1. LOST4. If and are formulas, then ( ) is also a If and are formulas, then ( ) is also a If and are formulas, then ( ) is also a If is a formula andviis a variable, then ( vi) is also a If is a formula andviis a variable, then ( vi) is also a , any formula is built up this way from atomic formulas and afinite number of applications of the inferences 2 through that we have specified a language of set THEORY , we could specifya proof system. We will not do this here seendifferent logic books forndifferent proof systems. However, these are essentially all the same satisfying the completeness theorem(due to K.)

8 G odel) which essentially saysthat any formula either has a proof or it has an interpretation in which itis false (but not both!). In all these proof systems we have the usual logicalequivalences which are common to everyday mathematics. For example:For any formulas and :( ( ( ))) is equivalent to ;( ) is equivalent to (( ) ( ));( ) is equivalent to (( ) );( ) is equivalent to (( ) ( ));( vi) is equivalent to ( ( vi)( )); and,( ) is equivalent to ( ).The complete collection of subformulasof a formula is defined as fol-lows:1. is a subformula of ;2. If ( ) is a subformula of , then so is ;3. If ( ) is a subformula of , then so are and ;134. If ( ) is a subformula of , then so are and ;5.

9 If ( ) is a subformula of , then so are and ;6. If ( ) is a subformula of , then so are and ;7. If ( vi) is a subformula of andviis a variable, then is a subformulaof ; and,8. If ( vi) is a subformula of andviis a variable, then is a subformulaof .Note that the subformulas of are those formulas used in the constructionof .To say that a variablevioccurs boundin a formula means one of thefollowing two conditions holds:1. For some subformula of , ( vi) is a subformula of ; or,2. For some subformula of , ( vi) is a subformula of .The result, , of substitutingthe variablevjfor each bound occurrenceof the variableviin the formula is defined by constructing a for eachsubformula of as follows:1.

10 If is atomic, then is ;2. If is ( ) for some formula , then is ( );3. If is ( ) for some formula , then is ( );4. If is ( ) for some formula , then is ( );5. If is ( ) for some formula , then is ( );6. If is ( ) for some formula , then is ( );7. If is ( vk) for some formula then is just ( vk) ifk6=i, butifk=ithen is ( vj) where is the result of substitutingvjforeach occurrence ofviin ; and,14 CHAPTER 1. LOST8. If is ( vk) for some formula then is just ( vk) ifk6=i, butifk=ithen is ( vj) where is the result of substitutingvjforeach occurrence ofviin .That a variablevioccurs freein a formula means that at least one ofthe following is true:1. is an atomic formula andvioccurs in ;2.