A Course on Set Theory

  • Published on

  • View

  • Download


A Course on Set TheorySet theory is the mathematics of innity and part of the core curriculum formathematics majors. This book blends theory and connections with other parts ofmathematics so that readers can understand the place of set theory within the widercontext. Beginning with the theoretical fundamentals, the author proceeds to illustrateapplications to topology, analysis and combinatorics, as well as to pure set theory.Concepts such as Boolean algebras, trees, games, dense linear orderings, ideals, ltersand club and stationary sets are also developed.Pitched specically at undergraduate students, the approach is neither esoteric norencyclopedic. The author, an experienced instructor, includes motivating examples andover 100 exercises designed for homework assignments, reviews and exams. It isappropriate for undergraduates as a course textbook or for self-study. Graduatestudents and researchers will also nd it useful as a refresher or to solidify theirunderstanding of basic set theory.ernest schi mmerli ng is a Professor of Mathematical Sciences at CarnegieMellon University, Pennsylvania.A Course on Set TheoryERNEST SCHIMMERLINGCarnegie Mellon University, Pennsylvaniacambri dge uni versi ty pressCambridge, New York, Melbourne, Madrid, Cape Town,Singapore, S ao Paulo, Delhi, Tokyo, Mexico CityCambridge University PressThe Edinburgh Building, Cambridge CB2 8RU, UKPublished in the United States of America by Cambridge University Press, New Yorkwww.cambridge.orgInformation on this title: www.cambridge.org/9781107008175C E. Schimmerling 2011This publication is in copyright. Subject to statutory exceptionand to the provisions of relevant collective licensing agreements,no reproduction of any part may take place without the writtenpermission of Cambridge University Press.First published 2011Printed in the United Kingdom at the University Press, CambridgeA catalogue record for this publication is available from the British LibraryLibrary of Congress Cataloguing in Publication dataISBN 978-1-107-00817-5 HardbackISBN 978-1-107-40048-1 PaperbackCambridge University Press has no responsibility for the persistence oraccuracy of URLs for external or third-party internet websites referred to inthis publication, and does not guarantee that any content on such websites is,or will remain, accurate or appropriate.ContentsNote to the instructor page viiAcknowledgements x1 Preliminaries 12 ZFC 73 Order 223.1 Wellorderings 233.2 Ordinal numbers 283.3 Ordinal arithmetic 414 Cardinality 534.1 Cardinal numbers 534.2 Cardinal arithmetic 604.3 Conality 675 Trees 825.1 Topology fundamentals 825.2 The Baire space 855.3 Illfounded and wellfounded trees 965.4 Innite games 1055.5 Ramsey theory 1155.6 Trees of uncountable height 1196 Dense linear orderings 1256.1 Denitions and examples 1256.2 Rational numbers 1286.3 Real numbers 1317 Filters and ideals 1417.1 Motivation and denitions 1417.2 Club and stationary sets 153vi ContentsAppendix Summary of exercises on Boolean algebra 163Selected further reading 164Bibliography 166Index 167Note to the instructorThis book was written for an undergraduate set theory course,which is taught at Carnegie Mellon University every spring. Itis aimed at serious students who have taken at least one proof-based mathematics course in any area. Most are mathematics orcomputer science majors, or both, but life and physical science,engineering, economics and philosophy students have also donewell in the course. Other students have used this book to learnthe material on their own or as a refresher. Mastering this bookand learning a bit of mathematical logic, which is not included,would prepare the student for a rst-year graduate level set theorycourse in the future. The book also contains the minimum amountof set theory that everyone planning to go on in math should know.I have included slightly more than the maximum amount ofmaterial that I have covered in a fteen-week semester. But I donot reach the maximum every time; in fact, only once. For a slowerpace or shorter academic term, one of several options would be toskip Sections 5.6 and 7.2, which are more advanced.There are over one hundred exercises, more than enough foreight homework assignments, two midterm exams, a nal examand review problems before each exam. Exercises are located atthe ends of Chapters 1, 2, 3, 4 and 6. They are also dispersedthroughout Chapters 5 and 7. This slight lack of uniformity istied to the presentation and ultimately makes sense.In roughly the rst half of the book, through Chapter 4, I de-velop ordinal and cardinal arithmetic starting from the axioms ofZermeloFraenkel Set Theory with the Axiom of Choice (ZFC). Inother words, this is not a book on what some call naive set theory.There is one minor way in which the presentation is not entirelyviii Note to the instructorrigorous. Namely, in listing the axioms of ZFC, I use the impreciseword property instead of the formal expression rst-order formulabecause mathematical logic is not a prerequisite for the course.Some other textbooks develop the theory of cardinality for aslong as possible without using the Axiom of Choice (AC). I donot take this approach because it adds technicalities, which arenot used later in the course, and gives students the misleadingimpression that AC is controversial. By assuming AC from thestart, I am able to streamline the theory of cardinality. I may notehow AC has been used in a proof but I do not belabor the point.Once, when an alternate proof without AC exists, it is outlined inan exercise.The second half of the book is designed to give students a senseof the place of set theory within mathematics. Where I draw con-nections to other elds, I include all the necessary backgroundmaterial. Some of the other areas that come up in Chapter 5 aretopology, metric spaces, trees, games and Ramsey theory. Thereal numbers are constructed using Dedekind cuts in Chapter 6.Chapter 7 introduces the student to lters and ideals, and takes upthe combinatorics of uncountable sets. There is no section specif-ically on Boolean algebra but it is one of the recurring themes inthe exercises throughout the book. For the readers convenience,I have briey summarized the results on Boolean algebra in theAppendix. All of this material is self-contained.As I mentioned, before starting this book, students should haveat least one semesters worth of experience reading and writingproofs in any area of mathematics; it does not matter which area.They should be comfortable with sets, relations and functions,having seen and used them at a basic level earlier. They shouldknow the dierence between integers, rational numbers and realnumbers, even if they have not seen them explicitly constructed.And they should have experience with recursive denitions alongthe integers and proofs by induction on the integers. These no-tions come up again here but in more sophisticated ways than ina rst theoretical mathematics course. There are no other pre-requisites. However, because of the emphasis on connections toother elds, students who have taken courses on logic, analysis,algebra, or discrete mathematics will enjoy seeing how set theoryand these other subjects t together. The unifying perspective ofNote to the instructor ixset theory will give students signicant advantages in their futuremathematics courses.AcknowledgementsAs an undergraduate, I studied from Elements of set theory byHerbert Enderton and Set theory: an introduction to independenceproofs by Kenneth Kunen. When I started teaching undergraduateset theory, I recommended Introduction to set theory by KarelHrbacek and Thomas Jech to my students. The reader who knowsthese other textbooks will be aware of their positive inuence.This book began as a series of handouts for undergraduate stu-dents at Carnegie Mellon University. Over the years, they foundtypographical errors and indicated what needed more explana-tion, for which I am grateful. I also thank Michael Klipper forproofreading a draft of the book in Spring 2008, when he was agraduate student in the CMU Doctor of Philosophy program.During the writing of this book, I was partially supported byNational Science Foundation Grant DMS-0700047.1PreliminariesIn one sense, set theory is the study of mathematics using thetools of mathematics. After millennia of doing mathematics, math-ematicians started trying to write down the rules of the game.Since mathematics had already fanned out into many subareas,each with its own terminology and concerns, the rst task wasto nd a reasonable common language. It turns out that every-thing mathematicians do can be reduced to statements about sets,equality and membership. These three concepts are so fundamen-tal that we cannot dene them; we can only describe them. Aboutequality alone, there is little to say other than two things areequal if and only if they are the same thing. Describing sets andmembership has been trickier. After several decades and somefalse starts, mathematicians came up with a system of laws thatreected their intuition about sets, equality and membership, atleast the intuition that they had built up so far. Most importantly,all of the theorems of mathematics that were known at the timecould be derived from just these laws. In this context, it is com-mon to refer to laws as axioms, and to this particular system asZermeloFraenkel Set Theory with the Axiom of Choice, or ZFC.In the rst unit of the course, through Chapter 4, we examine thissystem and get some practice using it to build up the theory ofinnite numbers.In another sense, set theory is a part of mathematics like anyother, rich in ideas, techniques and connections to other areas.This perspective is emphasized more than the foundational aspectsof set theory throughout the course but especially in the secondhalf, Chapters 57. There, our choice of topics within set theory is2 Preliminariesdesigned to give the reader an impression of the depth and breadthof the subject and where it ts within the whole of mathematics.To get started, we review some basic notation and terminology.We expect that the reader is familiar with the following notionsbut perhaps has not seen them expressed in exactly the same way.Ordered pairs are used everywhere in mathematics, for example,to refer to points on the plane in geometry. The precise meaningof (x, y) is left to the imagination in most other courses but weneed to be more specic.Denition 1.1 (x, y) = x, x, y is the ordered pair withrst coordinate x and second coordinate y.It is convenient that (x, y) is dened in terms of sets. After all,this is set theory, so everything should be a set! The main pointof the denition is that from looking at x, x, y we can tellwhich is the rst coordinate and which is the second coordinate.Namely, if x, x, y has exactly two elements, then the rstcoordinate isx = the unique z such that z x, x, yand the second coordinate isy = the unique z ,= x such that x, z x, x, y.And, if x, x, y has just one element, which can only happenif x = y, then the rst and second coordinates are bothx = the unique z such that z x.To understand this formula, keep in mind thatx, y = y, xandx, x = x.In particular,x, x, x = x, x = xand x is the only element of x.Denition 1.2 A B = (x, y) [ x A and y B is theCartesian product of A and B.Preliminaries 3Denition 1.3 R is a relation from A to B i R is a subset ofAB, that isR AB.Sometimes, if we know that R is a relation, then we write xRyinstead of (x, y) R. For example, we write2 < not(2, ) 2, thenVn is a transitive set that is not an ordinal.It is important to have a reasonably good picture of where weare headed before plunging into technical facts about ordinals. Asyou read this paragraph, beware of the signicant work requiredto justify this description of the ordinals, work that is capturedby Lemmas 3.18, 3.19, 3.20, 3.21 and 3.22, and results on ordinal3.2 Ordinal numbers 31addition in the next section. Here is the picture you should havein mind. Starting from the empty set, we use the operation at successor stages and take unions at limit stages to generate allthe ordinals beginning with the natural numbers 0 = , 1 = 0,2 = 0, 1, 3 = 0, 1, 2, etc. The next ordinal after all the naturalnumbers is the set of natural numbers, = 0, 1, 2, . . . .After comes the innite sequence of ordinals + 1 = 0, 1, 2, . . . , + 2 = 0, 1, 2, . . . , , + 1 + 3 = 0, 1, 2, . . . , , + 1, + 2...followed by innitely more ordinals + = 0, 1, 2, . . . , , + 1, + 2, . . . + + 1 = 0, 1, 2, . . . , , + 1, + 2, . . . , + + + 2 = 0, 1, 2, . . . , , + 1, + 2, . . . , +, + + 1...after which comes the ordinal + +.Skipping ahead, we eventually get to + + +and, somewhat later, to = + + + .The list of ordinals never ends. Notice that, for natural numbers,the membership relation coincides with the usual strict linearordering < on the natural numbers, and that this pattern contin-ues through the ordinals we have listed above. Namely,0 1 2 3 + 1 + 2 + 3 .32 OrderReturning now to a rigorous exposition, we make the followinggeneral notational rules.Denition 3.17 If and are ordinals, then we may write < and ( < or = ).This convention will allow us to write0 < 1 < 2 < 3 < < < + 1 < + 2 < + 3 < with the same meaning as0 1 2 3 + 1 + 2 + 3 once we nish developing the theory of ordinals.Next are some important basic principles about ordinals towhich we have alluded above. The proofs might seem confusingthe rst time through because they involve all three notions: ,


View more >