Set Theory Notes - 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*.

2 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* .. 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 *.

3 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.

4 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.

5 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,..,n}for some natural numbern. IfXis not finite, say smallest size of infinite set isN(see Exercise ).

6 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.

7 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. 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).

8 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).

9 [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.

10 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. 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.