Set Theory - UCLA Mathematics

1 Set TheoryAndrew MarksJuly 22, 2020 These notes cover introductory set Theory . Starred sections below are op-tional. They discuss interesting Mathematics connected to concepts covered inthe course. A huge thanks to Spencer Unger for enlightening conversations, andthe students in the class who asked excellent questions, and corrected countlesstypos in the midst of a global Independence in modern set Theory * ..62 The axioms Classes and von Neumann-Bernays-G odel set Theory * .. 123 Wellorderings144 Ordinals165 Transfinite induction and Goodstein s theorem * .. 236 The cumulative hierarchy257 The Mostowski collapse288 The axiom of Fragments of the axiom of choice* .. 319 Cardinality Cardinality in models of the axiom of determinacy* .. Resurrecting Tarski s Theory of cardinal algebras*.

2 3610 Cofinality3811 Cardinal arithmetic The singular cardinals hypothesis* .. 44112 Filters and Measurable cardinals* .. 4913 The Ax-Grothendieck theorem * .. 5414 Clubs and stationary sets5515 Applications of Fodor: -systems and Silver s theorem5916 Compactness and incompactness in set Theory * .. 6417 Suslin trees and 6618 Models of set Theory and absoluteness6919 The reflection theorem7520 G odel s constructible G odel operations and fine structure* .. 8121 Condensation inLandGCH8322V=Limplies 8623 Land large Finding right universe of set Theory * .. 9024 The basics of forcing9125 Forcing = truth9526 The consistency of CH9821 IntroductionSet Theory began with Cantor s proof in 1874 that the natural numbers do nothave the same cardinality as the real numbers. Cantor s original motivationwas to give a new proof of liouville s theorem that there are non-algebraic realnumbers1.

3 However, Cantor soon began researching set Theory for its own by 1878 he had articulated the continuum problem: whether there isany cardinality between that of the natural numbers and the real s ideas had a profound influence on Mathematics , and by 1900, Hilbertincluded the continuum problem as the first in his famous list of 23 problemsfor Mathematics in the 20th recall Cantor s definition of cardinality. IfXandYare sets, say thatXhas cardinality less than or equal toYand write|X| |Y|if there is aninjective function fromXtoY. Say thatXandYhave thesame cardinalityand write|X|=|Y|if there is a bijection fromXtoY. These definitions agreewith our usual ways of counting the number of elements of finite sets. Cantor sinsight was to also use these definitions to compare the size of infinite recall a few basic facts about cardinality2:Exercise a nonempty set, then|X| |Y|if and only if there is asurjection that a setXis finite if it has the same cardinality as a set of the form{1.}

4 ,n}for some natural numbern. IfXis not finite, say smallest size of infinite set isN(see Exercise ). Finally, say a setXiscountableif|X| |N|.Exercise a set, eitherXhas the same cardinality as a finite set,or|N| |X|.Exercise (A countable union of countable sets is countable.).IfXiis acountable set for everyi N, then iXiis an infinite set, andYis a countable set, then|X|=|X Y|.Exercise (Cantor-Shr oder-Bernstein).|X|=|Y|if and only if|X| |Y|and|Y| |X|.We writeX YifXis asubsetofY. That is, z(z X z Y).P(X)denotes the collection of all subsets ofX:P(X) ={Y:Y X}.1 Recall that a real number is called algebraic if is a root of a nonzero polynomial withrational coefficients. For example, 2 is algebraic since is a root of the equationx2 showed that the cardinality of the real numbers is greater than that of the algebraicnumbers.

5 Thus, there must be non-algebraic this section, we freely use the axiom of choice3 Exercise that there is a bijection fromP(N)to the real numbersR.[Hint: First, there is a bijection fromRto(0,1). Then show there is a bijectionfrom(0,1)toP(N)using binary expansions and Exercise ]Using this bijection betweenP(N) andR, we can quickly prove thatNhasstrictly smaller cardinality thanP(N) (and henceR). Supposef:N P(N)is any function. Thenfis not ontoP(N). We prove this by constructing asubset ofNthat is not in ran(f). LetD={n N:n / f(n)}. Then this setDdiagonalizes againstf. Sincen D n / f(n),Dcannot equalf(n) for anyn. Hence,D / ran(f) andfis not 1: Cantor s diagonal argument. In this figure we re identifying subsets ofNwith infinite binary sequences by letting the where thenth bit of the infinitebinary sequence be 1 ifnis an element of the exact same argument generalizes to the following fact:Exercise that for every setX, there is no surjectionf:X P(X).

6 [Hint: defineD={x X:x / f(x)}. Then showD / ran(f).]Thus, given any setX, its powersetP(X) has larger cardinality. Cantorhad realized that as a consequence of this, there can be no universal set: a setcontaining all other sets. Every set would inject (via the identity function) intoa universal set. But Exercise shows that the powerset of the universal setcould not inject into the universal Russell traced through Cantor s argument (lettingfbe the identityfunction andXbe a supposed universal set), and isolated what is now knownas Russell s paradox. IfD={x:x / x},then isD D? IfD / D, thenD Dby definition, contradiction. But ifD D, thenD / Dby definition, s writings about this paradox caused a brief crisis in the foundationsof set Theory . Allowing ourselves to construct a set containing all mathemati-cal objects satisfying some given property leads to contradictions.

7 What sets,then, should we be allowed to construct? Is the whole enterprise of set theoryinconsistent?The resolution to Russell s paradox that set theorists have adopted is the socalled iterative conception of set theory3. All sets are arranged into a cumulativehierarchy. We begin with a simple collection of sets, and then apply some basicoperations to iteratively create more sets. This produces the hierarchyVof allsets. The precise set existence axioms we will use will be discussed in the nextsection. They are known as Zermelo-Frankel set Theory orZF. We useZFCtodenoteZF+ the axiom of choice. The first part of this class will be discussingthese axioms ofZFCand axiomatic set 2: A picture of the set theoretic universe, known asV. At step , weconstruct all sets of rank .V denotes all sets of rank less than .Note that we will never define what a setisin these notes.

8 We re taking anaxiomatic principles about sets, but not allof them. We caution that it is very false to say a set is an element of a modelof set Theory . First, this would be circular; a model is defined in model theoryusing sets. Second, there are strange models of set Theory , which we wouldn twant to use to define what sets are. It would be similarly false to say that anatural number is an element of a model ofPA; there are nonstandard modelsofPAwith infinite elements greater than any natural alternatives toZFChave been also explored such as Russell s type Theory , or Quine snew foundations. They are rarely considered in modern set , G odel s incompleteness theorem says that it s hopeless to try and axiomatize alltrue sentences about the natural numbers. It is similarly hopeless to try and axiomatize alltrue principles about point in examining models of set Theory for us will not be to build the correct model.

9 Rather, our goal in examining models of set Theory will be tounderstand what the axioms of set Theory can Independence in modern set Theory *In the second part of our class, we ll begin to discuss some topics around inde-pendence in set reaction to Russell s paradox, many mathematicians hoped to find a foun-dation for set Theory that could be proved to be free of paradoxes. G odels workin 1931 shattered this hope; we can never prove that theZFCaxioms of settheory are consistent using simple means. G odel showed that any computableset of axioms which can interpret and prove basic theorms about the naturalnumbers cannot prove its own consistency. From a modern viewpoint, mathe-matical theories are arranged along a hierarchy of consistency strength, whereT1 CONT2if Con(T2) Con(T1). That is, the consistency ofT2implies theconsistency 3: A picture of some common theories arranged by their important class of set theoretic assumptions with strong consistencystrength are large cardinal assumptions.

10 These are assumptions that there exist very large cardinal numbers. For example, aninaccessible cardinalis anuncountable cardinal number so that is regular (cf( ) = ) and is astronglimit( < implies 2 < ). Informally, this means cannot be reachedfrom below by adding smaller cardinals or applying the powerset operation tosmaller cardinals. If is an inaccessible cardinal, then if we stop building the set-theoretic universe at stage ( if we takeV ), then we obtain a model + there exists an inaccessible cardinal proves there is a model ofZFC, by G odel s completeness theorem ,ZFC+ there exists an inaccessible cardinal implies Con(ZFC), and thereforeZFCcannot prove there is an inaccessible car-dinal. This is a typical phenomenon. If is a large cardinal, then the uni-6verse restricted to height satisfiesZFC, and more generally will contain many smaller large other interesting set theoretical statements end up being equivalentin consistency strength to large cardinal assumptions.