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

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. Say thatXandYhave thesame cardinalityand write|X|=|Y|if there is a bijection fromXtoY.

5 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 ). Finally, say a setXiscountableif|X| |N|.Exercise a set, eitherXhas the same cardinality as a finite set,or|N| |X|.

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

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

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

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

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