### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Selected Topics Set Theory MATH 580

BSU

GPA 3.72

### View Full Document

## 6

## 0

## Popular in Course

###### Class Notes

##### HIST 1200 (History, Steven Watts, Survey of American History Since 1865)

###### Elizabeth Ronecker

verified elite notetaker

## Popular in Mathematics (M)

This 45 page Class Notes was uploaded by Breanne Schaden PhD on Saturday October 3, 2015. The Class Notes belongs to MATH 580 at Boise State University taught by Staff in Fall. Since its upload, it has received 6 views. For similar materials see /class/218012/math-580-boise-state-university in Mathematics (M) at Boise State University.

## Popular in Mathematics (M)

## Reviews for Selected Topics Set Theory

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/03/15

MODELS OF SET THEORY STEFAN GESCHKE CONTENTS First order logic and the axioms of set theory Syntax Semantics A i A i and i F 39 of and the 39 theorems The axioms Review of basic set theory Classes Wellfounded relations and recursion Ordinals7 cardinals and arithmetic The consistency of the Axiom of Foundation Elementary Submodels7 the Re ection Principle7 and the Mostowski Collapse Constructibiltiy De nability The de nition of L and its elementary properties ZF in L V L AC and GCH in L Forcing Partial orderings7 dense sets and lters Generic extensions The forcing relation ZFC in M C CH is independent of ZFC Forcing Forcing CH The countable chain condition and preservation of cardinals Nice names and the size of 2N0 Martinls Axiom Martin s Axiom and Souslin7s Hypothesis The Baire Category Theorem and Martinls Axiom lterated forcing Long iterations References mammmawwmmm 2 STEFAN GESCHKE ll FIRST ORDER LOGIC AND THE AXIOMS OF SET THEORY llll Syntax The language L of set theory is the rstorder language with the binary relationsymbol 6 That is the language L consists of the formulas over the alphabet A n 3 E UVar where Var is a countably in nite set of variables By recursion on the length we de ne what a formula is If I and y are variables then I E y and z y are formulas Such formulas are called atomic If so and 11 are formulas then so are ago and g0 If so is a formula and z is a variable then Ergo is a formula tool We will frequently omit parentheses in a formula if this does not lead to any am biguityl Also we will add parentheses if this improves readabilityl Vzgo abbreviates z go and g0 V abbreviates g0 As usual we will freely use other abbreviations like Q A and Hz 6 y inside a formula Exercise 11 Let I and y be variables and let go and 11 be formulas Write out what the following abbreviations stand for 12 ram Hzeysa This obviously depends on your intuition of what formulas are supposed to mean We discuss the meaning of formulas in Subsection 12 You may use all the previ ously de ned abbreviations A free occurrence of a variable I in a formula go is an occurence of 1 outside the scope of any quanti er 31 Recall that V1 is just an abbreviation If 1 occurs freely in go then I is a free variable of gal We write zl i i i zn instead ofjust go in order to indicate that all the free variables of so are listed among 11 i i i In and that the variables 11 i i i In are pairwise distinctl A sentence is a formula without free variables 12 Semantics We brie y discuss the intended meaning of formulas A structure for the language of set theory is a set X together with a binary relation El In the following let X be a set and E a binary relation on Xi Small letters from the beginning of the alphabet possibly with index such as aa1 i i i amb denote elements of Xi Small letters from the end of the alphabet possibly with index such as I 11 i i i In y are typically variables of the language of set theory Let zlp i i In be a formula The intended meaning of alp i i an is the statement about a1 i i i an that is obtained by replacing every free occurence of r by ai z l i i i n and interpreting the symbol by actual equality and the symbol 6 by the relation El To make this precise by recursion on the length of formulas we de ne whether X E satis es ah i i i an We write X E l ah i i i an for X E satis es a1luan l We abbreviate 11 E zga1a2 by a1 6 a2 and 11 zga1a2 by a1 agi 1 X E l a1 6 a2 iff alEagl 2 X E l a1 a2 iff a1 agl Here the rst is an element of the alphabet of the language of set theory the second has the usual meaning 3 X E l gpa1luan iff X E l7 alp i i an 4 X E l g0 a1luan1ff XE ls0a17m7anl and XE l manual 5 Let I y1l i i yn be a formula Then the free variables of Ergo are among y1l i i ynl Hence we can write 31 y1lu yn instead of 31 Now XvE l 31 lb1vuybnl MODELS OF SET THEORY 3 iff there is an element a of X such that ltXEgt l mm o l l m 13 C l l and 39 A set of sentences is a theory If E is a theory and X E satis es each of the sentences in 2 we say that X E is a model of 2 Similarly if X E satis es a sentence go we say that X E is a model of go A sentence go follows from E if every model of E is a model of go In this case we write 2 l go There is also a notion b E b go means that go is formally provable from E The following statement about the connection between l and b is easily the most important theorem about rst order logic Theorem 12 Completeness Theorem If E is a theory and go is a sentence then 2 l go i E b go We are going to use the Completeness Theorem freely without referring to it explicitly Since formal proofs have a nite length a formal proof of go from 2 only uses nitely many sentences from 2 Hence using the completeness theorem we obtain Corollary 13 Compactness Theorem If E is a theory and go a sentence then 2 l go i there is a nite theory 20 Q 2 such that 20 l go A theory 2 is consistent if it does not lead to a contradiction ie if there is no sentence go such that both go and go are provable from 2 Corollary 14 A theory 2 is consistent i it has a model Proof Suppose X is not consistent Let go be a sentence such that both go and go follow from 2 Now if M X E is a model of 2 then M l go and M l go But this contradicts the de nition of M l go Now suppose that 2 does not have a model and let go be any sentence Since 2 does not have a model every model of 2 satis es both go and go Hence go and go both follow from E and thus 2 is inconsistent We will frequently use Corollary 15 A theory 2 is consistent i every nite subset of E has a model Exercise 16 Give a proof of Corollary 15 14 quot of quot and the 39 l theorems Prac tically all of mathematics can be formulated in the language of set theory Hence all one has to do in order to come up with a sound foundation of mathematics is to nd a system of axioms ie a theory with the following properties 1 The axioms re ect our intuitive understanding of the concept set 2 Practically all mathematical statements that are generally regarded as prov able actually follow from the axioms 3 The axioms are consistent Note that the demands 1 and 2 are slightly vague but there is common agreement that there is a system of axioms that satis es 173 namely Zermelo Froenkel Set Theory ZF together with the Axiom of Choice AC ZFACZFC Since 1 and 2 are open to different interpretations all we can say is that most mathematicians agree that ZFC is a suitable system of axioms 3 is a very precise statement but if all of mathematics takes place within ZFC we should be able to prove the consistency ZFC from ZFC itself Unfortunately as Godel has shown this is not possible In fact Godel has shown that for every system of axioms satisfying 4 STEFAN GESCHKE l and 2 in a precise sense7 3 is not provable from the axioms This is the Second lncompleteness Theorem Godels First lncompleteness Theorem says that if ZFC or any similar theory is consistent7 then there are sentences so such that neither g0 nor 1 follow from it Such a sentence go is called independent over ZFC The main goal of this course is to show that the Continuum Hypothesis CH is independent over ZFC 15 The axioms The axioms of ZFC are the following we use some obvious abreviations 1 Set Existence 311 0 2 Extensionality VszVzz E z lt gt 2 E y A z y 3 Foundation Vzz 0 A By E 1V2 6 12 4 Separation really a scheme of axioms For every formula g0z7 yh yn without a free occurrence of y Vyl VynVZHszz E y lt gt z E 2 g0z7 yl 7yn is an axiom 5 Pairing VIVy32z E 2 y E 2 6 Union VFHAVY E FY Q A 7 Replacement again a scheme of axioms For every formula g0z7 y yl yn7 without a free occurence of y W1 VynVAVI 6 AHYWW y 117 i 7 A HYVI E A y E Yg0zyy1 7yn is an axiom Here 3 means there is exactly one In nity A 00 V 319 6 z AVy E zy U E 9 Power set VIHsz2 Q I A 2 E y 10 Choice V13RR is a wellordering of I For the Axiom of Choice recall that a binary relation S on a set X is well ordering if S is a linear order on X and every nonempty set Y Q X has a minimal element with respect to 3 See also De nition Exercise 17 Write out the formulas lego I D and z y U 2 Exercise 18 Write out the formula R is a wellordering of 1 Note that since Separation and Replacement are schemes and not just single axioms7 ZFC consists of in nitely many axioms MODELS OF SET THEORY 5 2 REVIEW OF BASIC SET THEORY 21 Classes Assume that we live in a universe of sets that satis es all the axioms of ZFCi This is the usual framework in which mathematics takes place A class C is a collection of all sets with a certain property More precisely7 if 17 M7 i i i 7 yn is a formula and 1217 i i i 71277 are sets7 then C a a7b17ui7bn is a class7 the class de ned by z7y17i i i 7y and the parameters 217 i i i 712W The class C a a7 1217 i i i 7 1277 is identi ed with a set 5 iff a7 1217 i i i 7 In is equivalent to a 6 c A class that does not correspond to a set in this way is a proper class We now consider the same situation7 but inside a structure M X7 E for the language of set theory that we can look at from the outside The variables of our language range over elements of the structure7 iiei7 they are interpreted by elements of the structure7 the sets of Mi lf 1217 i i i 7 bn are elements of X and 17 M7 i i i 7 yn is a formula7 then C a E X M a7 1217 i i 7177 is a class of M7 the class de ned by the formula z7y17i i i 7 yn with the parameters 217 i i 7 1277 Note that looking at M from the outside7 C is a set C can correspond to an element of X in the following way It might happen that for some 5 E X we have that for all a 6 M7 M a6 5 42gt M a7b17ui7bn7 iiei7 C a E X aEc This is the situation in which we identify C with c If R is a binary relation and b is a set7 then extRb a aRb is the extension of b with respect to R or the Rextensz39on of bi Note that the Axiom of Extensionality just says that two sets are the same iff they have the same Eextensioni This can be written as Vzextez In other words7 every set is uniquely determined by its Eextensioni The most important class is V7 the class of all sets V is a proper class We will soon de ne other important proper classes 22 Wellfounded relations and recursion Let C be a class and R a binary relation on C R is setlike if for all a 6 C7 extRa is a set R is wellfounded if every nonempty subset S of C has an Rminimal element7 iiei7 there is a E S such that 5 extRa 0 The Axiom of Foundation says that E is wellfoundedi The Axiom of Extension ality implies that E is setlikei Exercise 21 Let R be a setlike wellfounded relation on a class C Show that every nonempty subclass of C has an R minimal elementi Hint This might be harder than it seems at rst sight For a set S Q C de ne ExtRS SU UextRa a E S and Emma UExt S n e N Now7 if D is a nonempty subclass of C7 pick a E D and consider the set D O Extf ai Why is this a set You may take recursion on the natural numbers for granted Because of the usefulness of this exercise7 whenever we consider a wellfounded relation7 we will automatically assume that it is setlikei Theorem 22 Trans nite lnduction Let C be a class7 R a well founded relation on C7 z7y17 i i i 7y aformula and 1217 i i i 712 E C Iffor all a E C it holds that b7b17 i i i 71277 for all I E extRa7 then a7 1217 i i 71277 then for all a 6 C7 a7b17ui7bn 6 STEFAN GESCHKE Exercise 23 Give a proof of Theorem 22 Theorem 24 Recursion Theorem Let C be a class R a wellfounded relation on C and F V A V a function Then there is exactly one function G C A V such that for all a E C 96 Ca FaG lextRa Proof We first show uniqueness Let G and G be functions on C that both satisfy 96 and assume that they are not the same By Exercise 21 there is a E C W ich is R minimal with the property that Ca Ga But now by 967 Ca Fa7 G lextRa Ga7 a contradiction e now show the existence of Cl An initial segment of C is a set S Q C such that if aRb and b E S then a 6 5 Note that for any a 6 C7 Extfgo a is an initial segment of C in fact7 Extfgo a is the smallest initial segment containing a Let Q be the collection class of all functions 9 that are de ned on an initial segment of C such that for all a E domg the equation holds for 9 Note that trivially7 the empty function is an element of Q By the proof of uniqueness of C any two functions gg E Q agree on the intersection of their domains7 which happens to be an initial segment of C it follows that G UQ is a function If a E domG7 then there is g E Q such that a E domg Now G l extRa g l extR a and hence G satisfies for all a E domG Now assume that domG G Let a be R minimal with a g domGl Let 9 G lEXti2 eXtRa G l EXti20ia all We extend g to g Ext a A V by letting ga Fagl Now 9 E Q and a E domg l Therefore a E domG7 a contradiction Note that if C is a proper class7 then so is Cl But a class is a collection of sets that is definable by a formula What is the formula that defines G A pair 127 c of sets is in G iff there is a set 9 that happens to be a function that is defined on an initial segment of C and satisfies for all a in its domain such that b E domg and 91 c This is tedious but certainly possible to express in our formal language of set theory D 23 Ordinals7 cardinals and arithmetic A set a is transitive if for all b E a andallcebc a Exercise 25 Let a be transitivel Show that a U a and 73a are transitivel Exercise 26 Let X be a transitive set Show that X7 6 satisfies the Axiom of Extensionalityl Find a set X such that X7 6 does not satisfy the Axiom of Extensionalityl An ordinal is a transitive set that is linearly ordered by E The proper class of all ordinals is denoted by 0rd If a and B are ordinals7 then a lt 6 iff a E Ord is linearly ordered by lt7 ilel7 by E The Axiom of Foundation implies that lt is a wellordering of 0rd If a is an ordinal7 then a U a is the smallest ordinal that is bigger than 1 a U a is frequently denoted by a 1 where the is the of ordinal arithmetic7 not of cardinal arithmetic7 which we will discuss belowl An ordinal of the form a 1 is a successor ordinal An ordinal different from 0 ll that is not a successor ordinal is a limit ordinal Two sets a and b are of the same size if there is a bijection between theml A cardinal is an ordinal a that is not of the same size as any smaller ordinall The proper class of cardinals is denoted by Card The cardinality of a set a is the MODELS OF SET THEORY 7 least ordinal that is of the same size as a It follows from the Axiom of Choice that every set has a cardinality and the cardinality of a set is always a cardinal Every in nite cardinal is a limit ordinal If H and A are cardinals then H A is the size of X H U X A and H A is the size of H X A Ii is the size of the set of all functions from A to Ii Theorem 27 If H and A are cardinals and at least one of them is in nite then H X A HA maxHA The nite ordinals happen to be cardinals and are denoted by 01 2 Recall that 0 ll 1 0 2 01 and so on The set of all nite ordinals is w the rst in nite ordinal For every ordinal a the ath in nite cardinal is denoted by Na In other words the rst in nite cardinals are w N0 N1 N2 and so on No is the size of the set N w 2NO is the size of the set R of real numbers which is the same as the size of73w Theorem 28 For every cardinal H 2N gt H By this theorem the rst candidate for 2NO is N1 The statement 2NO N1 is known as the Continuum Hypothesis The main goal of this course is to show that CH can be neither proved nor refuted from the axioms of ZFC Note that Theorem 28 implies that for every cardinal there is a larger cardinal If H is a cardinal then the smallest cardinal strictly larger than H is denoted by Ii The Generalized Continuum Hypothesis OCH is the statement that for every in nite cardinal H we have 2N H Let a be an ordinal A Q a is co nal in 1 iff for all 6 lt a there is y E A such that B S y The co nality cfa of an ordinal a is the least size of a co nal subset of a A cardinal H is regular if H cfH otherwise it is singular Co nalities of ordinals turn out to be regular cardinals Exercise 29 Show that N1 is regular and N is singular Hint If A is co nal in N1 then N1 U A Why lfA Q N1 is countable what is the size of U A For the singularity of Na use the fact that the union of a set of cardinals ie the supremum of the set of cardinals is again a cardinal The only limitation to the possible values of 2N0 is the following strengthening of Theorem 28 Theorem 210 Let H be an in nite cardinal Then H lt cf2 8 STEFAN GESCHKE 3 THE CONSISTENCY OF THE AXIOM OF FOUNDATION In this section we show that ZF is consistent provided that ZF without the Axiom of Foundation is consistent This relative consistency proof is technically very easy but nevertheless already uses important ideas that can be used for other consistency proofs as well Let ZF denote ZF without the Axiom of Foundation Theorem 31 If ZF is consistent then so is ZF Proof Assume that ZF is consistent Then this theory has a model 6 We use V E in order to construct a model of ZF To do this we pretend to live inside Vi The ordinals are the ordinals of V the cardinals are the cardinals of V and so on Note that we should adjust our de nition of ordinals so that we arrive at the same notion as in the context of Foundation an ordinal is a transitive set that is wellordered rather than just linearly ordered by 6 It can be shown without the Axiom of Foundation that the class Ord of ordinals is wellordered by e For a E Ord let VD be de ned by lt1 v0 2 0 ii Va1 39 73004 iii V I U lta V3 if a is a limit ordinall Using trans nite induction we show that V0aeord is a strictly Qincreasing se quence of transitive setsl Let W Uaeord V0 ilel let WF be the class consisting of all sets a such that for some ordinal a a 6 Val For every a 6 WF let rka denote the least ordinal such that a E Va1l The ordinal rka is the rank of of Note that every ordinal a is an element of WF with rka al We show that WF 6 is a model of ZF Set Existence is obviously satis ed It follows from the transitivity of the V0 that WF is transitive Hence WF satis es the Axiom of Extensionalityl The Axiom of Separation follows directly from the construction of the Val Namely if a is an element of V0 then so is every subset of al The Axioms of In nity Union and Pairing are easily checked For the Axiom of Replacement let F be a function ie a class of pairs in WF such that for all a 6 WF there is at most one I 6 WF such that ab 6 Fl Now consider the function rk oFl For every a 6 WF FM und rk 0F M are sets in V since V 6 satis es Replacement We have to nd a superset of FM in W i It follows from Separation the FM is a set in WFT Let a I suprk 0FM Now FM Q Va1 and Va1 E Va2 Q WFT It follows that WFE satis es replacementl It remains to show that WF 6 satis es the Axiom of Foundation Let a E WFT Let b E a be of minimal rankl en 12 is an Eminimal element of a since for all cd 6 WF with c E d we have rkc lt rkdl While this proof looks convincing at rst sight it does have a couple of problems First of all it is a bit confusing to denote a model of ZF by 6 since we donlt assume 6 to be the real Erelation and also the real V is not a set while structures for the language of set theory are assumed to be setsl On the other hand for someone living inside the structure the elements of the structure do form the class of all sets and the binary relation of the structure is simply the Erelationl Looking at the structure from the outside it should be denoted by M X E or something similar This is what we will do from now on The class WF of M really a formula with a single free variable de ning the class has been tacitly identi ed with the subset of X the consists of all a E X that MODELS OF SET THEORY 9 satisfy this formula in the structure M Then we showed that this subset of X with the restriction of E to it is a model of ZF It is possible to completely ingnore the world outside M in the proof of Theorem 31 In this case the notation E for M is again appropriate We again define the class WF But now the statement WF is a model of ZF77 does not make sense anymore since WF is a class and not a set Still it is possible to formalize that WF 6 is a model of a certain sentence go Let C be a class and go a formula The relativizatz39ou of go to C is the formula goo that is obtained by replacing every quanti er 31 that occurs in go by Hz 6 C Recall that V1 is just an abbreviation and therefore we do not have to consider this quanti er here Of course here Hz 6 C112 is just an abbreviation for a more complicated formula that depends on the formula that de nes C Now WF 6 is a model of ZF77 can be expressed by saying that for every axiom go of ZF goWF holds in V There is one subtle problem if we want to show goWF for every axiom go of ZF Consider for example the axiom Pairing It looks like we have to show for all ab 6 WF that ab is an element of WF This is easy since by Pairing in V a b is a set in V as well and it easy to check that in fact a b 6 WF Something similar is true for Power Set and Union Exercise 32 Let ab 6 WF Show that a b 6 WF Also show that 73a and U a are elements of W It is however not totally obvious that the set that satis es the de nition of a b in V also satis es this definition in WF Similarly we have to show that the sets that satisfy the definition of U a and of73a in V satisfy the same definition in WF Luckily these definitions are simple enough that an element of WF satis es the respective definition in V if and only if it satis es that definition relativized to We introduce absoluteuess in order to deal with this problem explicitly De nition 33 Let C be a class and gozl zn a formula The formula go is absolute over C if the following holds VIlvwwxn 6 Cso11mzn H 900117m71n A function possibly a proper class is absolute over C if the formula that de nes it is absolute over C Obviously every formula that does not have any quanti ers ie Boolean com binations of atomic formulas of is absolute over every class Quanti ers of the form Hz 6 y are bounded A formula go is A0 if all quanti ers of go are bounded Lemma 34 Aoformulas are absolute over transitive classes Let C be a class that satis es a certain fragment ZFquot of ZF ie assume that goo holds for every go 6 ZFquot Let go be a formula and suppose that ZFquot implies that go is equivalent to a Aoformula Then go is absolute over transitive classes that satisfy ZFquot It follows that intersections unions unordered pairs ordered pairs the empty set and so on are absolute over transitive classes that satisfy all the axioms of ZF except possibly Power Set and In nity Now suppose that C is a transitive class that satis es enough of ZF to show the recursion theorem Then the function a gt gt Va is absolute over C in the sense that the formula gozy that says that y is an ordinal a and z is an element of V0 is absolute over C 10 STEFAN GESCHKE From this absoluteness of the Va it follows that WF is a model of V WFI By trans nite induction over 6 it can be shown that assuming ZF V WF is equivalent to the Axiom of Foundation Exercise 35 Show that ZF implies that V WF 4 ELEMENTARY SUBMODELS THE REFLECTION PRINCIPLE AND THE MOSTOWSKI COLLAPSE Let M E be a set with a binary relation EI We will often identify M with M If E is clear from the context this is not going to lead to confusion This is actually quite common throughout mathematics we seldomly distinguish between the eld R 01 of real numbers and the set RI Now N E M is an elementary substructure or an elementary submodel of M if for every formula gozl I I I In in the language of set theory and all al I I I an the following holds NE l goa1I I I an 42gt M E l goa1 I I I an Note that if we write N E we really mean N E N N2I The lncompleteness Theorems imply that there cannot be a set N in V such that NE is an elementary submodel of EI This is Tarskils unde nability of truth I In other words there are no sets over which all formulas are absolute However we will soon see that for a given nite sets of formulas it is possible to construct even transitive sets such that all of the nitely many formulas under consideration are absolute over the transitive setI We will use this in the following way In order to prove the consistency of ZFC CH we pretend that there is a transitive set M such that M E is a model of ZFCI Using M we construct another transitive set N such that N 6 satis es ZFC but not CHI Now if ZFC CH failed to be consistent then by the Compactness Theorem there is already a nite subset of ZFC CH that leads to a contradiction But in order to prove that these nitely many sentences hold in N 6 we only need that M 6 satis es a certain nite subset of ZFCI And for nitely many sentences there are transitive sets M such that these nitely many sentences are absolute over MI We start with a lemma that will save us some work Lemma 41 Let C be a class and sol I I I son a sequence offormulas that is closed under taking subformulas Recall that only 3 is part of our language V is an abbre viation Then the formulas sol I I I son are absolute over C iffor all solm I I I ym of the form Ergoj z y1I II yn we have Vth II ym E CHzgojz yl I I I ym A 31 E Cgojzy1 I I I Exercise 42 Give the proof of Lemma 4I1I Use induction over the length of solI Theorem 43 Re ection Principle Let W Ord A V be a function with the following properties i For all 15 6 Ord with a lt B we have Wa Q ii f7 is a limit ordinal then WW UDKV Wa iii V UaEOrd Wa39 For every sequence sol I I I gon of formulas and all a E Ord there is B E Ord with B gt a such that the goj are absolute over Proof Let sol I I I son be formulas and a E 0rd We may assume that the sequence sol I I I son is closed under taking subformulasI By Lemma 41 it is suf cient to nd 6 gt a such that for all goiy1I II yml of the form Ergojzy1 I I I yml we have Vylwqym 6 W 3Wjryylwqym A 396 6 W sojryyhuqyml MODELS OF SET THEORY 11 For every i E 17 i i i 7 n we de ne a function Gl as follows Suppose goi y17 i i i 7 gm is of the form Hzgojz7y17ui7ymli Let Gib17ui7bml 0 if there is no a such that goj a7 b17 i i i 7 bml holds in Vi If there is a such that goj a7 b17i i i 7 bml holds in V7 then let Gib17i i i 7 bml be the least ordinal a such that there is such an a in Wai Note that the existence of 1 follows from in Now we choose a sequence aked as follows Let Bo 1 Suppose we have de ned Bk for some h 6 mi Let k1 be the least ordinal gt Bk such that for all 80i917 Wynn and all 1 17 ybmz in WW 01021 wme lt kr Let B supIced Now it is easily checked that for each soly17iu7 yml and all b17i i i 7 bml E Gib17 i i i 7bml lt Hence7 by the choice of the Cl and by Lemma 4il7 all the goi are absolute over D Observe that the function a gt gt Va satis es all the assumptions of Theorem 43 In particular7 if V satis es ZFC7 then for every nite list 017Hi7gon o axiom in ZFC there are arbitrarily large a such that V047 6 satis es gob i i i 7 soul A proof very similar to the proof of Theorem 43 yields Theorem 44 LowenheimSkolem Theorem7 downward Let M7 E be a struc ture for the language of set theory For every C M there is an elementary submodel N E M ofM such that X E N and lNlSl N0 Proof As in the proof of Theorem 43 it is enough to nd N E M with X E N and lNlle H20 such that for every existential formula 17 M7 i i i 7y and all b17iu7bn E N with M l ambhwbn there is a E N such that M l avblvuwbnb For every formula 17 M7 i i i 7 yn we de ne a function p M A M such that for all b17iu7bn E M we have M l pb17i i i 7 bn7 b17i i i 7bn provided M l 31 b17i i i 7bni The p are called Skolem functions For every X E M let skX be the Skolem hull of X7 iiei7 the closure of X under all the functions f Since there are only countably many formulas and hence only countably many Skolem functions7 for every X E M7 lskXl le N0i Clearly7 N skX satis es all existential statements with parameters in N that are satis ed in Mr Hence7 N is an elementary submodel of i D Now7 if V satis es all axioms of ZFC7 we can carry out the following construc tion Let E be a nite collection of axioms of ZFCi By the Re ection Principle there is a such that all go 6 E are absolute over Val Since V7 6 satis es E7 V047 E is a model of E as well By the LowenheimSkolem Theorem7 Va has a count able elementary submodel Ni This shows that every nite collection of axioms of ZFC has a countable model assuming that V satis es ZFC We will proceed by constructing countable transitive models of nite parts of ZFCi Theorem 45 Mostowski Collapse Let C be a class and R a wellfounded re lation on C recall that we assume wellfounded relations to be setlike If R is extensional ie7 if two elements a and b of C agree i extRa extRb7 then there are a transitive class D and an isomorphism u C7 R A D7 6 12 STEFAN GESCHKE Proof We de ne M by recursion on R For every a E C let Ma W b 6 mm By the Recursion Theorem M is a wellde ned function from C to V Let D Ma a E C The function M is the Mostowski collapsing function and D is the Mostowski collapse of C R We rst show that M is 11 Suppose it is not and let a E C be Rminimal such that for some I E C we have a f b and Ma Mb By the de nition of M Ma Mc c E extRa Since Ma Mb Mc c E extRa Mc c E extRb But since a is an R minimal counterexample to the injectivity of M we can conclude that extRa extRb Now the extensionality of R implies a b a contradiction Clearly if ab E C are such that aRb then Ma E Mb On the other hand if Ma E Mb then since M is 11 a E extRb ie aRb This shows that M is an isomorphism It remains to show that D is a transitive class Let a E D and b E a Choose c E C such that a Mc By the de nition of M b is of the form Md for some d E extRc But then d E C and thus I Md E D B Our main application of the Mostowski Collapse is Corollary 46 Every nite fragment of ZFC has a countable transitive model Proof Let E be a nite fragment of ZFC We may assume that 2 contains the Axiom of Extensionality We have already argued that E has a countable model of the form N 6 Since N satis es the Axiom of Extensionality E is extensional on N Therefore N E is isomorphic to a structure M E where M is transitive But since N E and M E are isomorphic they satisfy the same sentences Clearly M is countable Exercise 47 Let C be a class on which E is extensional Suppose T is a transitive in V subclass of C Let D be the Mostowski collapse of C E and let M be the collapsing function Show that M is the identity on T In particular T E D MODELS OF SET THEORY 13 5 CONSTRUCTIBILTIY ln ZF we will de ne a class L that satis es ZFCGCHi Recall that GCH is the statement Vii E CardH 2 No A 2K HT L is Godells universe of canstructz39ble sets Since we want to show the consistency of the Axiom of Choice AC with ZF we have to be careful not to use AC in the following arguments We will explicit indicate uses of AC in certain places that are not essential for the theory Sill De nability The construction of L will be very similar to the construction of WF in that we de ne a hierarchy Lgaeord using some restricted power set operationi First of all we recall that formulas can be regarded as certain sets namely nite sequences of elements from our alphabet where the alphabet consists of sets lie we code the characters of the alphabet by certain sets say 77 by 0 77 by l 77 by 2 and so on For a nite sequence so of characters in the real world let ng denote its character bycharacter translation into the nite sequence a set of sets that we used to code the respective charactersi gal is the G delz39zatz39on of gal Using the Recursion Theorem we can now write down a formula fmlz in the real world that expresses the fact that z is a nite sequence of characters from our alphabet that happens to be a formula in the language of set theory We can then prove for every formula go in the real world that gal actually satis es fml Again using the Recursion Theorem we can write down a formula in the real world satzy2 that says i There is n E w such that y is a formula with n free variables ii there are a1 i an E I such that 2 a1 i i an iii the structure I 6 satis es the formula y if the free variables of y are interpreted by a1 i ani By induction over the complexity of formulas we can show that for every formula 11 i i 1 every set M and all a1 i i an E M it holds that g0Ma1 i i an lt gt satM Rail a1 i i an Hence the relation l can now be regarded as a de nable class where we consider l only for structures of the form M E but the general case M E can be handled practically in the same way Note that in the de nition of the formula sat we used the fact that we can code the nitely many sets a1 i i an into a single set namely the n tuple a1 i i an This is necessary since the formula sat has to have a xed number of free variables We can easily write down a formula that de nes the set ZFC of formulas We can then prove that every sentence in the realworld ZFC has its Godelization in Vls version of ZFCi If we are a little bit more general in the de nition of sat so that sat applies to structures of the form M E we can write down the formula Conz that says that z is a set of sentences that has a model Godells Second lncompleteness Theorem now states that ConZFC is not provable from ZFCi Note that the rst ZFC is the set satisfying the de nition of ZFC in V where the second ZFC is the realworld metamathematical ZFCi Now let M be a set A set P E M is de nable in M 6 if there is a formula I y1i yn such that for some parameters 121 i ibn E M we have PaEMME l ab1uibni 14 STEFAN GESCHKE Using the formula sat we can de ne a function D that assigns to each set M the set DM of subsets of M that are de nable in M E For every set M and every realworld formula goz yl yn we can show that for all 121 b7 6 M we have a E M goMab1bn E Lemma 51 Let M be a set Then the following hold 1 73M E 73M 2 IfM is transitive then DM and M Q 3 VX Q Mlelt w A X E 4 AC lMlZ w Hl7311llMl Proof 1 is obvious For 2 let M be transitive and a E M Then a z E M z E a Hence a is a de nable subset of M and thus a E Since a was arbitrary this shows M Q Now let a E DM and let I E a Since a E M b E M But since M Q DM b E This shows that DM is transitive 3 ln V we use induction over the size of X Clearly the empty set is de nable Now let it E w and let f z n 1 A X be a bijection By our inductive hypothesis is a de nable subset of M for instance z E M M l goz b1 bm for some b1bm E M Now fn l z E M M l gozb1bm VI bm1 where we choose bm1 4 easily follows from the facts that the language of set theory has only countably many formulas and that for every n E w there are only ntuples of parameters from M 52 The de nition of L and its elementary properties De nition 52 For each ordinal a we de ne La recursively as follows i L0 2 ll ii La1 1 Dale iii La 2 lta Lg if a is a limit ordinal Let L I Uaeord La be the class of constructible sets Using Lemma 51 by trans nite induction we easily get Lemma 53 For all a E Ord the set La is transitive For all 16 6 Ord with a S B we have La Q Lg In particular the Re ection Principle relativized to L applies to the function a gt gt 0 De nition 54 For every a E L we de ne the LTank pa of a to be the least a E Ord such that a E La1 Lemma 55 For all a E Ord we have the following 1 Laa Lpalta 2 La Ord a 3 a E L and pa a 4 L0 6 La 5 Every nite subset of La is an element of La1 MODELS OF SET THEORY 15 Proof 1 is immediate from the de nition of p We show 2 by induction on a If a 0 then La ll 0 Ord If a is a limit ordinal then a U 5 U L OrdLa Ord lta lta Now let a B 1 Then 6 Lg Ord But the de nition of the class of ordinals is A0 and hence absolute over the transitive class Lg Thus 6 is a de nable subset of L5 namely 6 a 6 Lg L3 6 l a is an ordinal Hence 6 6 L344 On the other hand a is not a subset of L5 simply because 6 g L3 The same holds for every ordinal 2 1 Hence a La Ord 3 follows immediately from 4 is obvious D Lemma 56 a For all a E Ord we have La Q Va 7 For all n E w Ln Vn Moreover Lu V 0 Assuming AC for all a 2 w lLallal Proof a follows from the fact that DM Q 73M for all sets M Since all nite subsets of a set are de nable for every nite set M we have DM This implies Ln Vn for every nite ordinal it Now Lu Una Ln Una Vn Vw This shows b For c observe that since all the Ln are nite lel N0 Now since for every in nite set M we have trans nite induction on a shows lLallal for all a 2 m D 53 ZF in L We assume that V satis es ZF and show that L satis es ZF as well That AC and GCH are satis ed in L requires some more work Theorem 57 L satis es ZF Proof Being an increasing union of transitive sets the class L itself is transitive Hence it satis es the Axiom of Extensionality Clearly ll 6 L and hence Set Exis tence is satis ed Foundation holds in L because it holds in V L satsi es In nity since w E We now show Separation in L Let I y1 yn be a formula and let a 121 In E L We have to show that z E a goLzb1 bn E L Choose a E Ord such that a 121 In 6 La By the Re ection Principle there is B gt a such that go is absolute between L3 and L Now I E a Lzb1bn z E a L zb1bn Clearly I E a goL3 1121 bn E DL L 1 Q L Since the Separation Axiom holds in L in order to prove Pairing Union Power Set and Replacement in L we only have to prove the existence of suf ciently large sets Good candidates are the La We give the proof of the Power Set Axiom The proofs of the other axioms are similar but rather easier Let a E L and let a I suppb b E LAb Q a 1 Now for all I E L with I Q a we have b 6 La 6 L Now the collection of all elements of L that are subsets of a can be obtained from La using Separation D 54 V L It is a natural question whether V can be the same as L ie whether ZFV L is consistent lntuitively one would think that L satis es V L While this is true it is an nontrivial fact It could happen that when we repeat the construction of L inside L itself we end up with some class LL which is a proper subclass of L Fortunately this is not the case Theorem 58 L satis es V L 16 STEFAN GESCHKE Proof We already know that L contains all the ordinalsl Hence in order to show V LL it suf ces to show that for all a E Ord we have La Lil Clearly L0 0 LOL and the limit stages of this inductive proof are easy Now let a E Ord and assume La Lg Now La1 Lid is equivalent to DLa DL L0 The de nition of D is a formula that uses the parameter w respectively wltw n60 w because that is the set that we use to code formulas as sets Moreover the de nition of D uses recursion over m but the individual steps in the recursion only use AOformulasl It is easily checked that recursively de ned functions in which the de nitions of the individual steps of the recursion are absolute are again absolute over models of suf ciently large fragments of ZF This shows that D is absolute over transitive classes that satis es ZF without Power Setl We need some fragment of ZF that allows us to prove the recursion theoreml ZF without Power Set is convenient works for our purposes and is satis ed by many sets This shows that L and V agree on whether a subset of La is de nable or not Hence DLa DL L0 This nishes the proof of the theoreml B These absoluteness considerations show this If M is a transitive class that contains all the ordinals and satis es ZF then L E M and L LMl In other words L is the smallest transitive class that contains all the ordinals and satis es ZFl We will see later that ZF is consistent with V f L MODELS OF SET THEORY 17 55 AC and GCH in L Theorem 59 V L implies the Axiom of Choice The proof of this theorem uses Lemma 510 Let E be a well ordering of a set X 7 a For all a1 anb1lbn E X let a a1 Han En b blpu zn i a f l and for the minimal i with ai hi it holds that ai E bi Then E is a wellordering on X h For all of E Xlt Una X let a Eltw h if either a is a shorter nite sequence than T or for some n E m 113 E X and a E h Then Eltw is a well ordering of Xlt Exercise 511 Prove Lemma 510 Proof of Theorem 59 We show a statement stronger than ACl We show that V L implies that there is a de nable binary relation lt1 that is a wellordering of L This clearly implies that every constructible set X can be wellordered7 namely by the restriction of lt1 to Recursively7 for all a E Ord we de ne wellorderings lt10 of La such that for a lt B Lmlt1a is an initial segment of Lgltg ilel7 lt1alt13l La and for all aELa andbELg withblt1gawehavebELw Obviously7 we have to put lt10 0 If a is a limit ordinal7 let lt04 U lta lt13 Similarly7 let lt1 Uaeord lt10 The only difficult step is the de nition of lt10 if a B l for some ordinal Assume lt13 is a wellordering of L3 Since there are only countably many formulas in the language of set theory7 the set of all formulas can be wellordered Let lt be a wellordering of the set of formulas Now let ab 6 La Lg1l lf ab 6 L5 let a lt10 1 iff a lt13 b If a 6 L3 and b E LD L57 let a lt1 b If ab E LD L57 let goazlulzn and goby1lym be ltminimal formulas defining a7 respectively b in L57 6 with suitable parameters Let alp an 6 LE be lt1gminimal with a c 6 Lg L56 l goalca1l 7anl and let 121 bm 6 L2 be lt1glminimal with b c 6 Lg Lg6 l gobcb1ulbm Now let a lt10 1 iff either goa lt gob or goa gob and alp an lt13 121 bm This nishes the de nition of the lt10 and hence of ltL It is straight forward to verify that the construction works using the proof of Lemma 510 D STEFAN GESCHKE In order to show that GCH holds in L we need Lemma 512 Let H gt No be a regular cardinal Then LN is a model of ZF without the Power Set Axiom Proof Since H is an in nite cardinal H is a limit ordinal The proofs of Set Exis tence Extensionality Pairing and Union in L actually go through for all La with a a limit ordinal In order to show the Separation Scheme we have to use some form of the Re ection Principle for Lg Let if a lt H For each existential formula 31 z y1 b1bn 6 La with yn and all parameters LN l 31 b1 In choose 7 lt H such that L7 already contains a witness to this existential statement To avoid trivialities we choose 7 gt a Let B be the set of all 77s chosen in this way Since there are only countably many formulas and since La is of size lt H B is of size lt H Since H is regular 60 supB lt H We now replace La by L30 and go through the same process obtaining 61 lt H and so on Finally let 6 supned Again by the regularity of H B lt H Clearly L3 is an elementary submodel of LN We are now ready to show that the Separation Scheme holds in LN Let I y1 LN We have to show t at bn 6 LM Let a lt H be such that ab1bn 6 La By the argument above there is B lt H such that a lt B and L3 is an elementary submodel of LN Now d Lg l 40121 bnl is a de nable subset of L3 and hence d 6 L311 Q LN This shows Separation The proof of Replacement is very similar to the proof of Replacement in L and uses again the regularity of H and the fact that all elements of LN are of size lt H D be a formula and ab1 In E dcEaIL lg0cb1H Theorem 513 V L implies GCH Proof Assume V L and let H be an in nite cardinal We show that 73H Q LN and therefore 2 S H et a E H By the LowenheirnSkolern Theorem there is an elementary submodel M of L such that lMl H and H U a E M Let N be the transitive collapse of M Since a E H E H and H is transitive H U a is transitive Since Mostowski collapsing functions are the identity on transitive classes a E Since N is isomorphic to an elementary submodel of LN N l V L Since N is a transitive model of ZF without the Power Set Axiom the absoluteness properties of L give that N UaeN Ord La Lg where B supN Ord Since M and therefore N are of size H l llL5l H In particular 6 lt H It follows that a E LN nishing the proof of the theorem D Corollary 514 If ZF is consistent then so is ZFCGCH Exercise 515 Assume V L Given an in nite a lt N1 give an explicit example of a subset a of w such that a E LN La Hint This actually requires some thought First of all observe that if a lt N1 is large enough then La contains a bijection between w and w X m Using this bijection relations on w ie subsets of w X m can be coded by subsets of m Now if R is a wellordering on w and a lt N1 is suitably chosen say for example La is an elementary submodel of LNI then La will also contain the unique ordinal that is isomorphic to wR because we can perform the Mostowski collaps of wR yn MODELS OF SET THEORY 19 inside Lw What is an example of a set not necessarily a subset of w that is in LN but not in La 20 STEFAN GESCHKE 6 FORCING In this section we will nd a way to enlarge the universe of all sets 61 Partial orderings dense sets and lters De nition 61 Let P be a set and S a binary relation on P Then RS is a partial ordering or a partial order if the following hold i Transitivity Vzy2 E lP z S y y S 2 A I S 2 ii Re exivity VI 6 lP z S 1 iii Antisymmetry Vay E lP z S y y S I A z The elements of P are conditions If p q 6 P and p S q we say that p is stronger than 4 respectively p extends 4 Two conditions p and q are compatible if they have a common extension r 6 ll ie if there is r 6 P such that r S p and r S g If p and q are not compatible they are incompatible and we write p T L For technical reasons we will only consider partial orders P with a largest element denoted by l or 1127 Similarly when dealing with several partial orders at the same time we might denote the relation S on P by Sp In this case we might also write LP instead of just L Let us consider a couple of examples N S is not a partial order in our sense because it does not have a largest element but of course it is a perfectly nice partial order in other contexts N 2 is a partial order in our sense but boring because any two elements are compati e Let U be the collection of all nonempty open subsets of R C Q is a very nice partial order in our sense Two condition U V E U are compatible iff U N V 3e 0 Clearly lg R Let M denote the collection of all measurable subsets of R of positive measure Then M Q is another nice partial order AB E M are compatible iff A N B is not of measure zero Observe that U and M are not standard names for these partial orders Typically one considers closely related Boolean algebras that are for our purposes equivalent to U and M namely the Cohenalgebra C and the measure algebra R We will see later what the connection between partial orders and Boolean algebras is Another important family of partial orders arises as follows Let X be a set Consider FnX2 p p is a function from a nite subset of X to 2 FnX2 is partially ordered by the reverse inclusion 2 The largest element of FnX2 is the empty function Two conditions pq E FnX2 are compatible iff p U L is a function The elements of FnX2 should be considered as nite approximations of a function from X to 2 For our purposes Fnw 2 is equivalent to U and to C We will later see why this is De nition 62 Let P S be a partial order Then D Q P is dense in P if for all p 6 ll there is L E D such that q S p For p 6 P we say that D Q P is dense below p if for all 4 S p there is r E D such that r S q A set A Q P is an antichain if no two distinct elements of A are compatible A set C Q P is a lter if the following hold i VpElP VqE CquHpEG ii Vpq 6 GET 6 Cr SpAr S 4 If D is a family of dense subsets of P and C Q P a lter then G is Dgeneric iff forallDED G Da lll MODELS OF SET THEORY 21 What do dense subsets of I look like If D Q U is any set then X UD is a union of open sets and therefore open If D is dense then for every nonempty open set U Q R there is V E D such that V E U In particular X N U ll It follows that X is dense in R in the topological sense On the other hand if X E R is dense and open consider D U Q R U Q X is open Now for every V E I X N V is nonempty and open and thus U X N V E D It follows that D is dense in U in the ordertheoretic sense Note however that not every dense subset of U is the collection of all nonempty open subsets of a dense open set X E R An example is the set of all open intervals with rational endpoints Another example is for 5 gt 0 the set DE of all open intervals of length lt 5 Now let I be a real number and consider G75 2 U E U z z E U It is easily checked that C75 is a lter in 0 Moreover C75 is DEEgt0generic On the other hand if C Q U is a DEEgt0generic lter then there is exactly one real number I such that z 6 HUGE clU Note however that z 6 H G can fail Exercise 63 Consider the partial order Fnw2 Show 1 If C Q Fnw2 is a lter then U G is a function 2 For all n E w the setDn I p E Fnw 2 z n E domp is dense Fnw 2 3 If C Q Fnw 2 is a Dn n E wgeneric lter then U G is a function from w to 2 4 For every function f z w A 2 the set Cf I p E Fnw2 p Q is a n z n E wgeneric lter The next theorem is a version of the Baire Category Theorem and guarantees the existence of suf ciently generic lters Theorem 64 RasiowaSikorsky Let RS be a partial order and let D be a countable family of dense subsets of R Then there is a D generic lter C Q R Proof Let Dn n E m be an enumeration of D Choose a sequence p7n6w of conditions in R as follows Let pg 6 D0 Suppose for n E w we have chosen pn already Choose pn1 S pn such that pn1 E Dn1 This can be done since Dn1 is dense Now let G p6 R 3n6wpn 10 It is straight forward to check that G is a Dgeneric lter D Exercise 65 Let A A and B B countably in nite dense linear orders without endpoints Recall that a linear order is dense if strictly between any two elements there is another element of the linear order Show that A SA and B SB are isomorphic Hint Use the Rasiowa Sikorski Theorem Consider the partial lP order of iso morphisms between nite subsets of A and B ordered by reverse inclusion Find a countable family D of dense subsets of R such that for every Dgeneric lter C Q R the function U G is an isomorphism from A to B It might help to take another look at Exercise 63 22 STEFAN GESCHKE 62 Generic extensions Our general assumption is that ZFC is consistent In order to show that ZFC CH is consistent it is enough to show that every nite set of sentences from ZFC CH is consistent We assume that V satis es all axioms of ZFC We show that for every nite subset F of ZFC CH there is a nite subset F of ZFC such that is M is a countable transitive model of F then there is a countable transitive model MG of F M and MG will have the same ordinals and M Q The construction of MG is independent of the particular set F ie we will simply assume that M is a countable transitive model of all of ZFC and then construct a model MG of all of ZFC CH from it In order to verify that MG satis es F we will have used the fact that M satis es a certain nite set F of axioms of ZF Now let M be a countable transitive model of ZFC and let ll be a partial order in M For every D E M being a dense subset of lP is absolute over M Since M is countable M contains only countably many dense subsets of lP By the Rasiowa Sikorski Theorem there is a lter C Q lP such that G intersect all the dense subsets of lP that are elements of M Such a lter is P generic over Exercise 66 Let M be a countable transitive model of ZFC and let P S E M be a partial order with the property that every p E lP has at least two incompatible extensions Show that no lter C Q lP that is P generic over M is actually an element of M Hint Given a lter G E M nd a dense subset D E M that is disjoint from G The model will be the smallest transitive model of ZFC such that M U C Q The elements of MG coded by names in M that will be decoded into elements of MG using the generic lter G De nition 67 A set 739 is a Pname if it is a set of pairs and moreover for every pair 017 6 739 p is an element of lP and a is a P name Let M be the class of all P names in M Note that the de nition of names is done by recursion over 6 and is simple enough to be absolute over M Le 739 E M is a P name iff it is a P name in V De nition 68 Let G be a P generic lter over M For every 739 6 MP let TG JG 3p 6 Gap E be the evaluation of 739 with respect to G Let MG Ta 739 6 MP The evaluations 73 are de ned by recursion over 6 This de nition takes place in V However the de nition is absolute over transitive models of a suf ciently large fragment of ZFC Lemma 69 If N is a transitive model of ZFC such that M U C Q N then M C Q N In order to show that M is a subset of MG for every I E M we have to nd a name 739 E M such that z Ta De nition 610 For every I let i 9110 y E I be the canonical name for 1 Lemma 611 For all z E M 3 I In particular M Q Proof Observe that 1p 6 C Now using induction over 6 igygzylpeiyzy zz MODELS OF SET THEORY 23 Next we show that G E We have to come up with a name for G Lemma 612 Let F 1610 p E P Then PG G Proof Fa c1p60P1p GG Let us collect some properties of Lemma 613 a MG is transitive b For all 739 6 MP rk7 g S rk7 c Ord M Ord MG Proof For a let y E MG and z E y Then there is some name y39 6 MP such that y39G y By the de nition of ya there is hp 6 y39 such that z 1393 and p E G But that means that z z39g E b follows by a straight forward Einduction For c rst observe that Ord M Q Ord MG by Lemma 611 On the other hand7 If a E Ord MG then there is a name i 6 MP such that dg a By b7 a rka S rkd E Ord M Since is transitive7 a E M It follows that Ord MG Q Ord M D The easier part of the proof that MG satis es ZFC is Lemma 614 MG satis es Foundation Extensionality In nity Paiiing and Union Proof Foundation is automatic since 6 is wellfounded in V Extensionality is satis ed since MG is transitive In nity holds since w E M Q For Pairing let ab E Choose names 07 6 MP such that a Hg and b Ta Now 77 0 hp 739 11127 is a name and 773 0G7 Ta nb For Union let F E MG and let 739 6 MP be a name such that 73 F Let a 771p 3104 E PEN E MP7rp E 739 mg 6 Obviously7 a 6 MP We show that UF Q ac Let a E UF Then there is b E F such that a E b It follows that there are mi 6 MP and 104 E G such that b 7T3 a 77 774 6 7r and mp E 739 By the de nition of a 771127 6 a and hence a E 03 This shows Union D Exercise 615 Assume we already know that MG satis es ZF Show that MG satis es AC Hint Since M satis es AC7 every name can be wellordered Before we introduce the tools needed to verify the rest of ZFC in MG we collect some additional data on generic lters De nition 616 A subset D ofa partial order P is predense if the set p 6 lP 3L 6 Dp S 4 is dense D is predense below p 6 P if the set L E lP Z 37 E D S T is dense below p A set 0 Q P is open if for all p E O and all 4 S p we have 4 E O A good example of predense sets are maximal antichains maximal with respect to Q Recall that A Q P is an antichain if any two elements of A are incompatible Exercise 617 Use Zorn7s Lemma to show that every antichain of P is contained in a maximal one 24 STEFAN GESCHKE Now let A Q P be a maximal antichain We show that A is predense For this we have to show that the set D p E P 3L 6 Ap S 4 is dense in P So7 let T E P Since A is a maximal antichain7 either T E A and hence T E D or A U T fails to be an antichain In the latter case7 there is p E A such that T and p are compatible Let g be a common extension of T and p Now 4 S T and q E D This shows that indeed7 D is dense in P Hence A is predense in P Exercise 618 Let D Q P be dense and let A E D be an antichain that is maximal among all antichains that are subsets of D Show that A is a maximal antichain in Lemma 619 Let M be a countable tTansitive model of ZFC P E M a partial oneT and C Q P a lteT a If G is geneiic oveT M and p E P then the following holds 1066 H quGUaiq b The following aTe equivalent 1 G is geneTic oveT M 2 FoT eveTy D E M that is pTedense in P G N D 3e ll 3 FoT eveTy D E M that is dense and open in P C N D 3e Z c FoT eveTy p E P the following aTe equivalent 1 G is geneTic oveT M andp E G 2 FoT eveTy D E M that is dense below p G N D 3e ll 3 FoT eveTy D E M that is pTedense below p G N D 3e ll PToof a Obviously7 if p E G then p is compatible with all elements of C Now assume that p is compatible with all elements of G Consider the set D q E P quVqu D is dense ian Let T E P lfT L p then T E D If T 1 p then there is g E P such that q S Tp But now 4 E D and hence T has an extension in D This shows that D is dense Since p P 6 M7 D E M Hence G intersects D But since all elements of G are compatible with p the only way that G can intersect D is that G contains some 4 with q S p But then p E G b 1 3 and 2 1 are trivial Now assume 3 and let D E M be predense in P Let E p E P 3L 6 Dp S Note that E is de nable from D and P and thus E E M Since D is predense7 E is dense in P It is easily checked that E is open By 37 there is p E G N E By the de nition of E7 there is g E D such that p S 4 Since G is a filter7 q E G Hence G intersects D This shows c The equivalence of 2 and 3 follows using the same arguments as for the equivalence of l and 2 in b Now assume either 2 or Consider the set D q E P q S p Clearly7 D is dense below p Hence G intersects D Hence G contains some condition S p Hence G contains p This shows Now assume 1 and let D E M be dense below p Let E q E lP q E DAL S p V q T p It is easily checked that E is dense in P Since 1177 D 6 M7 E E M By genericity of G there is g E G N E Since p E G and since G is a filter7 q 1 p By the de nition of E7 4 E D Hence G intersects D This shows D 63 The forcing relation We need a method to talk about truth in from the perspective of M This is provided by the foTcing Telation ll forces On the left hand side of this relation we have conditions in our xed partial order P On the right hand side we have formulas of the foTcing language The forcing language consists of expressions of the form go7391 Tn where gozl In is a formula in the language of set theory and at every free occurence of Ii 11 has been substituted by the lP name Ti MODELS OF SET THEORY 25 De nition 620 Let p E ll 7 let 411 zn be a formula in the language of set theory and let 71 Tn be P names Then p l 7391Tn iff for all P generic lters C over M with p E G MlGl l 8071G7m739rnc The relation l turns out to be a de nable class in M This is surprising since M does not have any knowledge about generic lters over M The goal of this subsection is to show the de nability of l in M De nition 621 For a formula 7391 Tn of the forcing language of M let Tlrn p6 lP p l 7391Tn be the truth value of 7391 73 Exercise 622 a Show that for every formula 7391 Tn in the forcing language the truthvalue 907391 Tn is an open subset o P b Let 7391 Tn be as above7 p 6 P and assume that 907391 Tn is pre dense below p Show that p E 907391 Hint For b use Lemma 619 Note that our de nition is not the standard de nition of truth values in forcing Typically7 truth values are only de ned if the partial order P is a complete Boolean algebra De nition 623 A Boolean algebra is is a partial order B with the following properties 1 B has a largest element 1 and a smallest element 0 2 Any two elements a7 12 E B have a largest common lower bound a b and a smallest common upper bound a V 3 Every a E B has a complement a such that a V a l and a a 0 4 For all abc ll 7 aA ch aAb VaAc A Boolean algebra B is complete if every set A Q B has a least upper bound A and a greatest lower bound A If B is a Boolean algebra7 then A Q B is a subalgebra of B if it contains 0 and l and is closed under V7 an n The simplest examples of Boolean algebras are the power set algebras 73X7 Q where is intersection7 V union and actual complementation relative to the set X It can be shown that every Boolean algebra is isomorphic to a subalgebra of a power set algebra If a Boolean algebra B is to be used for forcing purposes7 we consider the partial order lP B 0 instead The traditional de nition of the truth value of a formula Th Tn in a complete Boolean algebra B is go7391 Tn Va E B a l 7391 We will however stick to our de nition of truth values in De nition 621 and show later that our truth values actually are the appropriate elements of a certain complete Boolean algebra7 namely the completion of the partial order P that we are forcing with 26 STEFAN GESCHKE In order to show the de nability of lb in M it is certainly enough to show that the map 80717 77 11 H l807391 77nll is de nable in M In M we will de ne an approximation go7391739n of go 7391 Tn and then show that the two sets are actually the same For the following de nitions we pretend to live inside M De nition 624 For A Q P let regA p E P z A is predense below p be the regularization of A A is regular open if A regA For A B Q P let AVB regAUB AB regA regB and A p E P V4 6 ApJ Forpe lP and A Q lP let pA AAp pAA and p p 13 0er 730i let V reg and Af regA A E 7 Observe that for every A regA is open and contains every p such that regA is predense below p In other words regA is regular open In fact regA is the smallest regular open superset of The collection of all regular open subsets of P is denoted by rolP and is a com plete Boolean algebra with respect to the partial order Q The algebraic operations on rolP are just V and n For 7 Q rolP V is indeed the supremum of f in rolP and A is the in mum The smallest element of rolP is just 0 the largest element is P It is tempting to believe that rolP is a subalgebra of 730 which in fact it typically is not because V and l are not the same as N U and complementation in 73 P The Boolean algebra rolP is the completion of P Via the map e P A rolP p gt gt regp every element of P can be considered as an element of rolP This map however sometimes fails to be 11 Exercise 625 a Let 7 Q rolP be a family of regular open sets Show that f is regular open b Let A Q P Show that A is a regular open subset of P Exercise 626 Let e P A rolP be as above a Show that the range of e is dense in rolP Here a subset D of a Boolean algebra B is dense in B if it is dense in B 0 in the partial order sense b P is separative if for p q E P we have pq lt gt VTElP TLplt gtTL4 Show that e is 11 iff P is separative Hint For b rst show that ep eq iff p q De nition 627 Let a and 739 be libnames We de ne 0 6 Tl VH0 nl AP1777P 7 0 Q T d10V 77 6 7 10710E 0 07X O39QTHTAHTQO39HT MODELS OF SET THEORY 27 For formulas 0177 7 7 7 an and 7b73917 7 7 7 7 Tm in the forcing language let g0017 7 7 7 707 7b73917 7 7 7 77m g0017 7 7 7 7077 017 7 7 7 77m7 l lt017770n VWTLAMTmW l800170nl V lWTlpuyTMll and les00170nl llSD03917 7039nll7 For a formula 17 M7 7 7 7 7 yn in the language of set theory and P names 73917 7 7 7 7 Tn let Hzgoz7 7177 7 7 7 73977X Vg0a7 73917 7 7 7 7 737quot 2039 is a P name Note the very subtle recursion in this de nition For P names 007 017 7390 and 7391 let 007 ToR039177391 if rkao lt rkal and rk7 0 S rk7 1 or if rkao S rkal and rk7 0 lt rk7 17 The relation R is wellfounded7 0 T7 0 E T and 0 Q T are de ned by recursion over R7 where we rst de ne a Q T and 7 Q a quot and only then 0 T7 The rest of De nition 6727 is a typical recursion over the complexity of a formula Here we consider a Q 739 as an atomic formu a7 Lemma 628 Let 739177 7 7 7 Tn be a fonula in the foTcz39TLg language of M and let G be PgeneTic oveT M Then l 7391G7 7 7 7 7 TnG 42gt G N 717 7 7 7 7777 f 07 PToof We will rst prove this lemma for atomic formulas including formulas of the form I Q y7 We use induction over a wellfounded relation7 the same relation R that we used in the de nition of the truth values of atomic formulas in the forcing language7 Let 07739 6 MP and suppose that 0G 6 7G7 Then there are 77 6 MP and p E G such that 77717 E 739 and ac 7737 Now 07 77Ra7 739 and therefore7 by the inductive hypothesis7 there is g E 0 77 G7 Since p74 6 G7 there is T E G such that T S p747 We have T E 0 77 Apg 0 E T7 showing that CH 0 E T f 07 Now suppose that G intersects the set 0 6 Tl VH0 nl A101lt777Pgt T By the de nition of V7 Ua 77 Ap 77717 E 739 is predense below every element of 0 E T7 By the genericity of G7 there is 77717 E 739 such that G a 77 p f 07 Now p E G and G N 0 77 f 07 By the inductive hypotesis7 ac 77G7 Since p E G we have 773 E 7G7 It follows that 0G 6 7G7 Now let 0G Q 7G7 Suppose G N 0 Q 739 07 By the genericity of G7 there is L E G a Q T7 We have a Q T pv 776 T 77717 E a Vf ePV 77 E Tl177710 0 VfPAeln E Tl1777P 0 Therefore Up 77 E T 77717 E a is predense below 47 Hence7 there is 777p E a such that G p 77 E T f 37 In particular7 p 6 G7 Hence 773 E 037 Moreover7 G N 77 E 739 07 By the inductive hypothesis7 773 g 7G7 It follows that a T7 Assume 0G Q 7G7 Then there is 777 p E a with p E G and 773 g 7G7 By the inductive hypothesis7 C does not intersect the set 77 E T7 But then7 by the genericity of G7 G intersects 77 E T7 It follows that G intersects M ln 6 Tl hPV 77 6 Tl Hence G is disjoint from a Q Tl d10V 77 6 Tl1n7p 0 28 STEFAN GESCHKE Now suppose that 0G 73 Then 0G Q 73 and 73 Q 03 If G intersects 0 Q T and 7 Q a7 then it intersects la T On the other hand7 if G interects la T7 then it also intersects 0 Q Tl and 7 Q all It follows that 0G 73 This nishes the argument for atomic formulas For nonatomic formulas we use a straight forward induction on the complexity This yields no hidden traps and relies on arguments of the kind we have already used Using this lemma it is not hard to show Theorem 629 For all formulas 73917 7777 in the forcing language of M and for all p 6 ll we have p E 90739177Tn i p E 7177Tn holds in M In particular the relation lb is de nable in M Proof Suppose p lb 73917 7 Tn We show that go73917 7 Tn is predense below p Suppose not Then there is some 4 S p that is not compatible with any ele ment of go73917 7 By the proof of the Rasiowa Sikorski Theorem7 there is a P generic lter C over M that contains 4 Because of the choice of 47 G is dis joint from go73917 7Tn By Lemma 6287 satis es go7391g7 7 TnG7 contradicting the fact that with 4 also p is an element of G This shows llso717m7 rnll l 717 77nl Now let p E go739177739n Suppose there is a P generic lter C over M with p E G such that 7391G77 TnG fails in By Lemma 6287 G N 10717 77quot 3e ll However7 the condition p is incompatible with all elements of 10 73917 7 Tn7 a contradiction lf follows that p lb 73917 7 Tn This shows llsD717m7 rnll Q llso7177nll D Corollary 630 Let G be Pgeneric over M For a formula 73917 7739 in the forcing language of M we have MlGl l 7391G7 7 TnG i there is p E G such that p lb 73917 7 Tn 64 ZFC in Having de ned the forcing relation in M7 we are now ready to verify the rest of ZFC in Theorem 631 MlG sati es ZFC Proof The only axioms that we have not veri ed yet are Separation7 Replacement and Power et For Separation let 17 M7 7 yn be a formula in the language of set theory and let a7 1217 7127 6 We show that z E a MlGl l z7b177bn E Let 0397739177Tn 6 MP be such that 03 a and for all i E 177n7 Tl3 127 Set 77 7np134 6 Pang 6 a A S q Aplb manm Since lb is de nable in M7 we have 77 E M We show that 773 z E a MlGl l 171217 7127 Let I E 773 The there is mp E 77 such that TrG z and p E C By the de nition of 77 we have p lb 907T773917 777 and p S q for some 4 6 ll with 7r7 q E a It follows that z TrG 6 0G and MlGl l 171217 7127 Now let I E a be such that MlGl l 171217 7127 Then there is W74 6 a such that z Na and q E G Moreover7 there is p E G with p lb 907T773917 7777 Since any two elements of C have a common extension in G7 we may actually MODELS OF SET THEORY 29 assume p S q Hence 7r7p E 777 and thus I TrG E 773 This shows Separation in M G i llnlorder to show Replacement let 17 y7 217 i i i 7 277 be a formula and let a7 1217 i i i 7 127 6 MG such that MG l VI 6 a3yg0z7 y7b17 i i i 71277 Choose a7717iu7739n 6 MP such that 0G a and for all i 6 17 i i i 7n7 TiG blquot Choose a set S Q MP in M such that the following holds for all 7r7p E a and all 4 S p with 4 lb Elyg07r7 y7 717 i i 7 777 the set T S q z 377 E ST lb Tr777773917ui7739n is dense below qr Consider the P name S X We show that MG l VI 6 a y E S X lgg0z7 y7 1217 i i i 71277 Let I E a Then there is 7r7p E a such that 7TG z and p 6 Ci Moreover7 there iquGsuchthathpand 4 lb Hlyg07r7y7 73917 i i i 7777 By the choice of 5 there are 77 E S and T E G such that T S q and T lb m 777 73917 i i i 7 Tn Hence MlGl ls0ry77c7b1wbn7 and therefore MlGl l 39 E 5 gtlt 1G8017y7171 77577 For Power Set let a E Choose a 6 MP with ac a Let A 7r 3p 6 lP 7r7p E 0 For every function f z A A 730 let Tf 7r7p p E Put 77 7771 f is a function from A to 73lP i This de nition is a de nition in Mr We show MlG l mm 2 a a z 6 my Let I E with I Q a Choose 739 6 MP with 73 1 De ne f z A A 730 as follows For 7r 6 A let p E P z p ll 7r 6 739 Observe that f is a function in Mr Clearly7 TfG E 779 We show that z TG Tfgi Let y E 1 Since I Q 03 there is mp E a with p E G and y TrGi Choose 4 S p with q E G and 4 lb 7r 6 Ti By the de nition of f7 y TrG E Tfgi Now let y E Tfgi Then there is 7r7p E Tf with y TrG and p 6 Ci By the de nition of f7 p lb 7r 6 7397 and hence y TrG 6 79 It follows that 73 Tfgi This shows that 773 is a superset of 73aMGli D Corollary 632 If ZFC 239s consistent7 then s0 is ZFC Vy L PToof Let M be a countable transitive model of ZFC and let P E M a partial order such that every condition in P has two incompatible extensions7 for instance lP Fnw72i Let G be P generic over Mr By the previous theorem7 MG is a model of ZFCi Moreover7 is transitive and has the same ordinals as Mr By the absoluteness of the de nition of L7 LMlcl LM Q Mi Sice G g M we have LMlcl a MG and thus MG is a model of ZFCV7 Li D 30 STEFAN GESCHKE 7 CH 1s INDEPENDENT OF ZFC In this section we show that ZFC neither implies nor refutes CH We already know that ZFC does not refute CH7 but we will give a forcing argument of this fact 71 Forcing CH Let M be a countable transitive model of ZFC We de ne a partial order P E M such that 1127 lf CH De nition 71 In M let P z A A 730 A is a countable subset of N1 P is ordered by S2 Let G be P generic over M In order to show that CH holds in MG7 we rst observe the following in Lemma 72 Let fa U G Then fa is afuhctz39zm from N1M onto 730 M Proof Since any two elements of C have a common extension in G UG is a function To see that fa is de ned on all of N1M and onto 730 M7 in M we de ne the following dense sets For every 1 lt N1 let Do I p E P z a E domp For every A E w let DA 2 p E P z A E rngp It is easily checked that the DD and the DA are dense in P Since G is generic over M7 G intersects all Du Hence domfg N1M Since C also intersects all DA7 we have rngfc 73wM D n order to show that MG satis es CH7 it is enough to show that N1M N1Mlcl and 73wM 73wMGl The rst equality could fail since N1M might be countable in le7 MG could contain a bijection between w and N1M The second equality could fail since might contain new subsets ofw In both cases MG would have to contain new functions from w into the ordinals We show that this cannot happen Lemma 73 Let f E be a map fTomw into the ordinals Then f E M Proof Let 6 MP be a name such that fa Moreover7 let p E G be such that p lf is a function from w to Ord In M let DquHgwgtOrdqlff By the genericity of C it is enough to show that D is dense below p We rst observe the following Let L S p and let F be lP generic over M with q E F Then p E F By the choice of p is a function from w to the ordinals Let n E w Then a for some ordinal 1 Since M and MF have the same ordinals7 a E M Hence there is T E F such that T lf d From now on we will drop severalvls in order to improve readability Since G is a lter7 we can choose T S L This shows that the set of all T E P for which there is some a E Ord with T lf a in dense below p From now on we argue in M This saves us several Ms A partial order Q is aclosed if for every descending sequence q ne of conditions in Q there is a common extension 4 E Q of the qn P is aclosed Namely7 let p ne be a descending sequence in P Then p I Una pn is a partial function from N1 to 730 with countable domain and hence an element of P Clearly7 p is a common extension of all the pn We are now in the position to show that D is dense below p Let L S p Choose qo S q and a0 6 Ord such that go lf 10 This is possible by the remark at the beginning of this proof Suppose we have chosen qn As above7 there is MODELS OF SET THEORY 31 qn1 S qn and an1 E Ord such that qn1 lb l an1 By the aclosedness of P there is a common extension T of all the qn We show that T E D et 9 z w A rdn gt gt an For all n E w we have T S qn ln particular7 T lb an for all n E w Since w is the same in all transitive models of set theory7 T lb 9 Hence T E D It follows that D is dense below p D Corollary 74 l CH PToof By Lemma 73 we have 73wM 73wMGl and N1M is uncountable in All ordinals below N1M are countable in M and hence in lt follow that N1M N1MGl By Lemma 72 in MG there is map from N1MGl N1M onto 73wMGl 73wM Hence MG l l73wl S N1 This it is provable in ZFC that 730 is uncountable and is a model of ZFC7 we have M G l CH D Exercise 75 Let P be a partial order Consider the following two player game that lasts w many rounds Let p0 qo 1127 In the nth round the rst player choses a condition pn1 S qn and the second player replies by chosing a condition qn1 S pn1 The second player wins the game iff there is a common extension p E P of the pn Suppose the second player has a winning strategy for this game Show that for every G that is P generic over M7 does not contain any new function from w into the ordinals Exercise 76 Let P Fnw7 2 Show that the rst player has a winning strategy in the game described above 8 FORCING CH In order to force the failure of CH7 we start from a countable transitive model M of ZFCCH and generically add at least N2M new subsets of w This is rather easily accomplished What requires work is to show that the N2 of the ground model M actually remains N2 in the extension In M7 let H be a cardinal gt N1 and let lP FnHgtltw2pzAHZIAisa nitesubset ofHXw be ordered by reverse inclusion Let G be lP generic over M Then fa U G is a function from H X w to 2 For every 1 E H let aa n E w fgan 1 Lemma 81 10016 6 H aTe di eTent then so aTe a0 and a3 PToof Consider the set D043 p E P 3n 6 wan E domp pa n f Let p E P Since the domain of p is nite7 there is n E w such that neither an not are in the domain of p Extend p to a condition 4 such that a n E domq and qan q n Then clearly7 q E D043 It follows that D043 is dense in lP Hence there is p E G N D043 Now p Q fa and hence fa an fa This implies aa a3 D This shows that forcing with P adds H new subsets of m In order to show that H remains large in MG7 we need to discuss a crucial property of the forcing notion 32 STEFAN GESCHKE 81 The countable Chain condition and preservation of cardinals De nition 82 A partial order Q satis es the countable anti chain condition ccc if every antichain of Q is countable It turns out that forcing with a ccc partial order does not collapse cardinals The following is the combinatorial foundation of the proof of this fact Lemma 83 In M let Q be ccc Then for every Qgeneric lter F over M and every function f E from some ordinal a E M to the ordinals of M there is a function E M from a to the countable sets of ordinals of M such that for all lt0m g 6 165 Proof Let F be Qgeneric over M and let f E be a function from some ordinal a to Ord Choose a name E MQ such that There is p E F that forces to be a function from a to Ord Let L S p and let H be Q generic over M with q E H For each 6 lt a there is an ordinal 7g such that 7g This has to be forced by some r E H We say that r decides Since 4 and r have a common extension in F7 we may chose r S q to begin with This argument shows that for each 6 lt a the set Dg r E Q r decides is dense below p For each 6 lt a let Ag be a maximal antichain below p consisting of conditions that decide Since Dg is dense below p7 Ag is really maximal among all the antichains below p In particular7 it is predense below p Let 75713T E AMT lb 155 7 Since Q is ccc7 Ag and hence is countable Since Ag is predense below p and p 6 F7 there is r E F such that r forces to be an element of Hence fFlt gt 6 165 D De nition 84 A partial order Q preserves cardinals if for every cardinal H7 1Q lb H is a cardinal Q preserves co nalities if for every ordinal a and H cfoz7 1Q lb H cfa Lemma 85 fQ preserves co nalities then it preserves cardinals Proof Let F be Qgeneric over M and suppose there is a cardinal in M that ceases to be a cardinal in By transitive induction on the cardinals in M we show that all the cardinals of M are still cardinals in Clearly7 N0M N0MFl If H is limit cardinal in M and all cardinals below H are preserved7 then in MF7 H is still the supremum of a set of cardinals and hence a cardina If H is a successor cardinal in M7 then cfH H in M Since Q preserves co nalities7 in MF7 H is still the co nality of an ordinal and hence a cardinal D Lemma 86 fQ is ccc then it preserves co nalities and hence cardinals Proof Let F be Q generic over M Suppose in MF7 a is an ordinal and H cfa Let f H A a be co nal If a is a successor ordinal in MF7 then it is a successor ordinal in M as well Hence we may assume that a is a limit ordinal If a is of countable co nality in M7 then it will have the same co nality in Hence we may assume that in M the co nality of a is uncountable MODELS OF SET THEORY 33 By Lemma 83 in M there is a function from H to the countable subsets of a such that for all 6 lt H E Since a is of uncountable co nality in M for each 6 lt a we have sup lt 1 Now for each 6 lt a S Since f is co nal in a so is 9 Hence in M cfa S H But since H is the least size of a co nal subset of a in MF there is no co nal subset of a of size lt H in M Therefore in M H cfa It follows that Q preserves co nalities D We now have to show that P FnH Xw 2 is actually ccc This fact is also non trivial and can be shown using the ASystem Lemma which is pure combinatorics Lemma 87 ASystem Lemma Let f be an uncountable family of nite sets Then theTe aTe a nite set T and an uncountable family D Q 7 such that foT all distinct st E D s t T D is called a Asystem with root T PToof After throwing away members of the family we may assume that f is of size N1 Now U f is of size N1 Hence we may also assume that 7 consists of subsets of N1 Moreover we may assume that all elements of 7 have the same size say n Let aD DWl be a 11 enumeration of 7 Let N1 A N1 i lt n be functions such that for all a lt N1 aa z i lt n and f0a lt lt fn1a Clearly if is unbounded then for allj lt n with i lt j fj is unbounded as well Let h S n be maximal such that for all i lt h is bounded Let a lt N1 be strictly greater than all the elements of the ranges of the fi i lt h Since a is countable a has only countably many nite subsets This shows that at least one of is unbounded and hence h lt n Since fk is unbounded there is an uncountable set I Q N1 such that fk is 11 on 1 Moreover there is a nite set T Q a such that J E I z i lt h T is uncountable By recursion we now choose a strictly increasing sequence ltk1 in J such that maxT lt fkwo and for 7 lt 7 lt N1 we have fn1 y lt This is possible since fk is unbounded on J It is easily checked that D ag7 7 lt N1 is a Asystem with root T D Lemma 88 F07 eveTy set X FnX2 is ccc PToof Let A Q FnX2 be uncountable By the ASystem Lemma A has an uncountable subset B such that the supports of the elements of B form a Asystem with some root T Q X Since there are only nitely many functions from T to 2 B contains two different conditions p and L that agree on T Since the sets domp T and domqT are disjoint pUq is a function It follows that p and q are compatible Hence A is not an antichain D Corollary 89 CHfails in PToof Recall that G is FnH gtlt w2generic over M where H is a cardinal gt N1 in M Since FnH X m 2 is ccc M and have the same cardinals By Lemma 81 w has at least H subsets in Hence l CH D 82 Nice names and the size of 2N0 Let M H P and G be as before We want to compute the actual value of 2N0 in We do this by nding a small set of P names such that every a 6 730 MG has a name in that set Exercise 810 Let a E Show that in M there is a proper class of names a with ac a 34 STEFAN GESCHKE De nition 811 Let Q be a partial order A Q name a is a nice name for a subset ofw if there is a family Awne of antichains of Q such that a 7120 p 6 An U h gtlt An Lemma 812 Let F be Qgeneric over M Then for every a 6 730 MF there is a nice name a E M for a subset ofw such that a 0F Proof Fix a name 739 E M such that a 77 For each n E w let An be a maximal antichain in the set 17 E Q p ll n E 739 Clearly7 a 7110 p E An is a nice name for a subset of m We have to verify that 0F a Let n 6 Up Then for some p E An7 p E F By the choice of An7 p lt n E 739 and hence it E TF a This shows up Q a On the other hand7 if n 6 a7 then there is mp E 739 such that p E F and 7TF n For some 4 6 F7 4 lb 7r n We can choose 4 S p Now 4 lb n E 739 Since An is a maximal antichain in the set of conditions that force it E 739 An is predense below 4 Since F is generic and q 6 F7 there is 7 E F An Now 7 H n E a and hence it 6 Up This shows a E 0F and hence a 0F D Exercise 813 Recall the de nition of the sets a07 a lt H7 mentioned in Lemma 81 Write down explicitly a nice name for each aw Lemma 814 Let Q be ccc Then there are at most nice Qnames for subsets of w Proof Since Q is ccc7 all antichains of Q are countable Hence Q has at most lQlNO antichains A nice name for a subset of w is essentially just a function from w into the set of antichains of It follows that there are at most Ql gt le nice names for subsets of m D Theorem 815 In M let P FnH gtlt w2 Let G be Pgeneric over M Then MG l 2N0 HN0M Proof Since H is in nite7 HN0M 2 2N0 M Since P is ccc7 it preserves cardinals By Lemma 817 2N MGl is at least Ii Since ZNOWO 2N0 2N MGl is at least HN0MGl Clearly7 HN0M S HNO Mlcl On the other hand7 in M there are at most HNO nice names for subsets of w and hence l73wlMGl S HNO M and the theorem follows Corollary 816 Let M G and H be as above IfM satis es GCH and cfH gt No then in MG 2N0 H IfM satis es GCH but cfH N0 then in MG 2N0 Ii Proof The corollary follows from the previous theorem and the fact that under GCH we have HNO H if cfH gt No and HNO li if H is an in nite cardinal of countable co nality D Exercise 817 Prove the statement about the size of HNO under GCH used in the proof of the previous corollary MODELS OF SET THEORY 35 9 MARTIN S AXIOM Having produced models of ZFC in which CH fails7 there are several natural questions 1 Let H lt 2N0 be a cardinal ls 2N S 2N0 2 How many measure zero sets are needed to cover the real line 3 Let X be a topological space A Q X is nowhere dense if the closure of A has an empty interior The Baire Category Theorem says in particular that R is not the union of countably many nowhere dense setsi But how many nowhere dense sets are needed to cover all of R i A family A Q 73w is almost disjoint if all AB E A with A f B have a nite intersectioni An easy application of Zorn s Lemma shows that every almost disjoint family of subsets ofw is contained in a maximal one What is the minimal size of an in nite maximal almost disjoint family An easy argument shows that no countably in nite almost disjoint family is maximali g All of these questions have an obvious answer under CHi Martin s Axiom also answers all these questions7 but is consistent with CHi ln fact7 MA is only inter esting if CH fails since under CH it does not say anything new as it follows from CHi De nition 91 Let H be a cardinal MAN says that for every cicici partial order R and every family D of size H of dense subsets of R there is a Dgeneric lter C Q R Martin s Axiom MA is the statement vii lt 2N MANi 9i Martin s Axiom and Souslin s Hypothesis The original motivation to introduce Martin s Axiom lies in Souslih s Hypothesis A linear order LS is 000 if there is no uncountable family of pairwise disjoint open intervals of Li L is separable if it has a countable dense subseti L is connected if it is not the union of two disjoint open subsetsi It is relatively easy to show that every connected separable linear order without endpoints is isomorphic to R Suslihs Hypothesis SH is the statement that every connected cicici linear order without endpoints is isomorphic to R H neither implies nor refutes SHi Both directions of this independence result are due to Jensen SH fails in L The consistency proof of MA CH is a relatively straight forward generalization generalization of Solovay s and Tennenbaumls proof of the consistency of SHi Martinls name is attached to the axiom because he observed that the consistency proof of SH could be adapted to show the consistency of something much stronger7 namely of MA with an arbitrarily large size of 2 0 36 STEFAN GESCHKE We now show how MAN1 implies SH A Souslih line is a connected linear order without endpoints that is ccc but not separable Since every separable connected linear order without endpoints is isomorphic to the real line7 SH holds and only if there is no Souslin line De nition 92 A partial order T7 S is a tree if for allt E T the set 3 E T s S t is well ordered If T is a tree and t 6 T7 then the height htTt of t in T is the order type of the set 3 E T s lt t7 ie7 the unique ordinal a such that oz7 E is isomorphic to s E T s lt t7 lt For an ordinal a the ath level LevaT of T is the set of all nodest E T of height a A branch ofa tree T is a maximal chain in T An antichain in a tree T is a family of pairwise incomparable elements of the tree A tree is Souslih if it is uncountable and has neither uncountable chains nor antichains Lemma 93 If there is a Souslih line then there is a Souslih tree Actually the existence of a ccc linear order that is not separable implies the existence of a Souslin line by roughly the same proof as below Connectedness simpli es the proof a tiny little bit The main information that connectedness gives us is that L has to be a dense linear order7 ie7 if ab 6 L are such that a lt b then ab is nonempty and in fact in nite Proof Let L7 S be a Souslin line The Souslin tree T that we are going to con struct will consist of nonempty open intervals in L ordered by reverse inclusion By recursion on a E Ord we de ne the ath level of the tree T Let Levo T We consider L as a nonempty open interval of L Suppose we have constructed the th level of T and a 61 For each interval I E Levg T let A be a an in nite maximal disjoint family of open intervals contained in I This is possible since by connectedness every nonempty open interval of L has at least two disjoint nonempty open subintervals Let LemT Um I e Lewd Now assume that a is a limit ordinal and for all 6 lt a we have already de ned LevgT Let LevaT be a maximal of pairwise disjoint7 nonempty open intervals I with the property that for every 6 lt a there is J E Lev5T with I Q J This nishes the de nition of T Obviously7 the levels of T are eventually empty Every antichain of T is a family of pairwise disjoint7 nonempty open intervals of L Since L is ccc7 every antichain of T is countable ln particular7 every level of T is countable Now suppose that T has an uncountable chain Since T is a tree7 every chain of T is wellordered Hence7 if T has an uncountable chain7 it has a chain of the form IQDLEN where I3 Q Ia if a lt Now the sequence of left endpoints of the Ia has an uncountable increasing subsequence or the sequence of right endpoints of the Ia has an uncountable decreasing subsequence Without loss of generality assume the former and let authem be a strictly increasing sequence in L Then ama0 1mg1 is an uncountable family of pairwise disjoint7 nonempty open in tervas in L7 a contradiction It follows that T has no uncountable chains Note that this implies that LevN1 T is empty It remains to show that T is uncountable Let D be the collection of all the endpoints of the intervals I E T that are not 00 or 700 We claim that D is dense in L Let ab 6 L be such that a lt b It is enough to nd some interval I E T that intersects ab but is not a superset of a7 12 since in this case a7 12 has to contain an endpoint o Let a be minimal with the property that a7 12 is disjoint from every element of Leva MODELS OF SET THEORY 37 We rst observe that a is a limit ordinal Otherwise a B 1 for some ordinal and there is I E Lev5T such that I has a nonempty intersection with ab But now A was chosen to be a maximal family of paiwise disjoint nonempty open subintervals of I Since I N a b is a nonempty open subinterval of I there is J E A Q LevaT such that J intersects ab a contradiction By the choice of a for every 6 lt a there is I E LevgT with ab N I 3e 0 If some of these I s intersects a b but is not a superset of a b we are done Hence we may assume that for each 6 lt a there is I E LevT such that a 12 Q I But by the de nition of LevaT this means that some J E LevaT intersect ab contradicting the choice of a We have thus found a dense subset of L of size at most Since L is not separable T is uncountable It follows that T is a Souslin tree D The converse of this lemma is also true if there is a Souslin tree then there is a Souslin line Theorem 94 MAN1 implies SH Proof We show that under MAN1 there are no Souslin trees Assume there is a Souslin tree T S We have to prune the tree a bit Namely we remove all those nodes t E T such that for some a lt N1 there is no 8 E LevaT with t S 8 Let T denote the pruned tree Now for every t in T and every 1 lt N1 with a gt htT t there is a node 8 E T of height a such that t S 8 If not then for some t E T and a lt N1 with a gt htTt t has no successors at the 0178 level of T But this implies that all successors oft in LevaT have only countably many successors in T It follows that t has only countably many successors in T a contradiction since t E T Now let P be the tree T but ordered by the relation 2 Now antichains in the tree T correspond to antichains in the partial order R Since with T also T has only countable antichains R is ccc Since every t E T has successors of every countable height for every 1 lt N1 the set DD t E T htT t gt a is dense in R By MAN1 there is a DaaltN1generic lter C Q R It is easily checked that G is an uncountable chain in T and hence in T A contradiction D 92 The Baire Category Theorem and Martin s Axiom In its strongest form the Baire Category Theorem states that no complete metric space and no compact space is the union of countably many nowhere dense sets We concentrate on compact spaces A topological space X is ccc if every family of pairwise disjoint open subsets of X is countable Theorem 95 MA is equivalent to the statement no ccc compact space is the union of fewer than 2N0 nowhere dense setsquot The proof of this theorem needs a couple of lemmas Before we start proving it we point out an important consequence Corollary 96 Under MA R is not the union of fewer than 2N0 nowhere dense sets Proof R is not compact but 01 is and R is homeomorphic to 01 A subset of 01 is nowhere dense in 01 iff it is nowhere dense in 01 The singletons 0 and 1 are nowhere dense in 01 It follows that the number of nowhere dense subsets of 01 needed to cover 01 is the same as the number of nowhere dense subsets of 01 needed to cover 01 In particular 01 and therefore R cannot be covered by fewer than 2N0 nowhere dense sets D 38 STEFAN GESCHKE Our rst step in the proof of Theorem 95 is to associate every Boolean algebra with a compact space This connection between Boolean algebras and certain compact spaces is known as Stone Duality De nition 97 Let A be a Boolean algebra and F E A We say that F is an ultra lter of A iff F is a maximal lter in the partial order A 0 or equivalently7 ifF is a lter inA0 and for each a6 A either a E F or nae F Let UltA denote the set of ultra lters of A topologized by declaring the sets of the form a F E UltA a E F7 a 6 A7 as open Le7 a subset of UltA is open iff it is a union of sets of the form a We call the sets a basic open Exercise 98 A set S Q A has the nite intersection property if for all n and all a17 an 6 A7 a1 an 0 By Zorn7s Lemma7 every set with the nite intersection property is contained in a maximal set with the nite intersection property Show that a maximal set S Q A with the nite intersection property is an ultra lter of A Lemma 99 For every Boolean algebra A UltA is a compact space the Stone space of A Proof We rst show that Stone spaces are Hausdorff7 ie7 for two distinct points Ly E UltA there are disjoint open sets UV Q UltA such that z E U and e V Let Ly E UltA be such that I f y Then there is a E A such that a E z and a g y or vice versa Without loss of generality we assume the rst Since y is an ultra lter7 a E y Now a and a are disjoint open sets7 the rst containing 1 the second containing y This shows Hausdorffness Now let 0 be an open cover of Ult For every I E Ult A choose agc E A such that for some U75 6 O we have I E agc Q U75 Clearly7 UltA UmeUltltAa If there are nitely many points 11 In E UltA such that UltA am U U awn7 then Ugc17 UM is a nite subcover of O and we are done Suppose there are not nitely many I such that the corresponding agc union up to UltA In this case the family UltA ail z E UltA has the nite intersection property7 ie7 no nite intersection of sets from the family is empty This easily translates to the nite intersection property of ags z E UltA By the previous exercise there is an ultra lter y of A that extends ags z E UltA It is easily checked that y g UerMA agc a contradiction D Exercise 910 Let A be a Boolean algebra For each a E A let Du b E A z b S a V b L a Then each Du is a dense subset of A If F E G is a DaaeAgeneric lter7 then F is an ultra lter Lemma 911 Let A be a Boolean algebra and S Q UltA If S is nowhere dense in UltA then the set Dsa6A0z al 50 is dense in A On the other hand if D is a dense subset of A then the set I e U1tA I g Um a e D is nowhere dense in UltA Proof Let S be nowhere dense Taking the closure of S we can assume that S is closed Let a E A Since 5 is closed and nowhere dense7 a Q 5 Hence a S is a nonempty open subset of UltA Since the topology on UltA is generated by the basic open sets7 there is b E A 0 such that b E a S and thus b 6 D5 and b S a This shows the density of D5 MODELS OF SET THEORY 39 Now let D be a dense subset of A and let UD U a a E D As a union of open sets Up is open In order to show that UltA Up is nowhere dense it is enough to show that Up is dense in UltA Let V E UltA be nonempty and open Then there is a E A 0 such that a E V By the density of D there is b E D such that b S a Now clearly 12 E V N Up This shows that Up is dense in UltA D Proof of Theorem 95 Assume MA and let X be a ccc compact space Let P denote the collection of all nonempty open subsets of X ordered by inclusion Since X is ccc so is P Let f be a collection of fewer than 2N0 nowhere dense subsets of X We may assume that each member of f is a closed set For each 5 E 7 let DSU lP clU S0 Let S E f and let U Q X be nonempty and open Since 5 is closed and nowhere dense U S is nonempty and open Let V E X be nonempty open and such that clV Q U 5 By the de nition of D5 V 6 D5 It follows that D5 is dense in P By MA there is a D556generic lter C Q P Let T clU U E G Since G has the nite intersection property and X is compact T f 0 By the genericity of G T is disjoint from every 5 E 7 showing that 7 does not cover X On the other hand let P be any ccc partial order and assume that no ccc compact space is the union of fewer than 2N0 nowhere dense sets Let A rolP and X UltA Claim 912 X is ccc Let A be a family of pairwise disjoint nonempty open subsets of X We may assume that every element of A is of the form a for some a E A We may further assume that every element of A is of the form a where a regp for some p E 73 Since the elements of A are pairwise disjoint the corresponding elements of P are pairwise incompatible Since P is ccc A is countable This shows the claim Now let D be a collection of fewer than 2N0 dense subsets of P Let 6 lP ro rolP be the natural embedding Since 6UP is dense in rolP the images of the D E D in rolP are also dense It follows that for each D E D the set SD X Uep p E D is nowhere dense in X By our assumption X is not the union of the SD D E D It follows that there is an ultra lter F of A that is not in any of the sets SD D E D Let G p 6 lP p E F Hence if D E D F E Uep 2p 6 D But this implies that there is some p E D such that 6p E F By the de nition of G p E G This shows that G has a nonempty intersection with D It follows that G is Dgeneric This shows MA D 40 STEFAN GESCHKE 93 Iterated forcing We are going to show the consistency of MA with CH by means of iterated forcing The strategy is as follows we start with a countable transitive model M of GCH and construct an increasing sequence Mahgmgw of models of set theory and a sequence GaaltN2M such that M0 M and for all a lt N2M Cu is Qageneric over Ma where Qa 6 Ma is a partial order and M0244 MDJGDL For each a lt N2M Ma l Qa is a ccc partial order of size N1 Most of the Qa add new reals all the Ma 1 lt N2M satisfy CH the nal model MN2M satis es 2N0 N2 and no cardinals are collapsed in the process We choose Qa in such a way that in the nal model the following holds whenever P is a ccc forcing of size N1 and D is a family of fewer than N2 dense subsets of P then there is a lt N2M N2 such that P Qa and D Q Ma In particular Ga which is an element of MN2M intersects every D E D showing that there is a Dgeneric lter of P By the following lemma this is enough to show MA in MN2M Lemma 913 Martin s Axiom is equivalent to Martin s Axiom restricted to partial orders of size lt 2N0 Proof We assume MA restricted to partial orders of size lt 2N0 Let P be a ccc partial order and let D be a family of dense subsets of P of some size H lt 2N0 Let A be a sufficiently large cardinal and Let M be an elementary submodel of VA of size H such that PE M andD E M Now consider the partial order Q P N M Let 4041 6 lf go and q1 are compatible in P then M knows about this and hence they are compatible in Thus if A Q Q is an antichain in Q it is an antichain in P It follows that Q is ccc Now let 4 E Q and D E D Since D is dense in P there is p 6 P such that p E D and p S q M knows about this and hence there is p E Q such that p E D and p S L It follows that D N Q is dense if By MA restricted to partial orders of size lt 2N0 there is a D N Q D E Dgeneric lter F E It is easily checked that the lter G generated by F in P is Dgeneric This shows Martinls Axiom B Our strategy has one major problem If a S N2M is a limit ordinal how do we de ne Mu It is tempting to choose Ma simply as the union of the previous Mg 6 lt 1 However there is no reason why this union should be a model of ZFC A strategy that works however is to de ne a single forcing notion Q in the ground model M such that every Qgeneric lter C over M codes a sequence Gagade of lters and a sequence MaaSN2M of models of set theory as above Let us rst consider the case where we want to iterate just two forcings Let P be a partial order in M and let G be P generic over M Let Q be a forcing notion in MG and let F be Qgeneric over Then MGF MG is a model of set theory We want to represent MGF as a single generic extension of M with respect to a certain forcing notion in M The problem is that Q might not be an element of M Hence from the point of view of M we can access Q only in terms of a lP name For simplicity we would like to assume that 11127 forces that is a partial order Moreover typically the partial order Q has a simple de nition in MG such as Q is the partial order of all closed subsets of R of positive measure We would like to have a name that is forced by 1127 to satisfy this de nition All this is made possible by the Existential Completeness Lemma Lemma 914 Existential C A Lemma r 39 M 39 quot Princi ple Let xy1 yn be a formula in the language of set theory Let P be a partial order 71 Tn Pnames and p 6 ll Suppose that p lk ngox7391 Tn MODELS OF SET THEORY 41 Then theTe is a Phame a such that p lb a7 17n The proof of this lemma uses the following sublemma Lemma 915 Let lP be a paTtial UTdeT A Q lP an antichaih and 0171793 a family of Phames Then theTe is a Phame a such that foT all p E A p lb 0 03917 PToof Let a 777 3106 A q E lP T S pAT S qA 7797 6 017 Now if p E A we claim that p lb 0 03917 Let G be generic over the ground model with p E G Let 777 6 a be such that T E G and 773 I Since A is an antichain p is the unique element of A that is in G Hence T S p By the de nition of a there is L E lP such that T S q and 77 q 6 Up Now 4 E G and hence I 773 E alga This shows 0G Q Upg On the other hand let I 6 0pm Fix 774 6 0391 such that q E G and 773 1 since p and q are both in G there is a common extension T E G of both p and 4 By the de nition of 0 777 6 a and hence I 773 E 03 This shows apg Q 09 D PToof 0f the Existential Completeness Lemma By the de nition of the truthvalue 31g0z 7391 Tn the set D q S p137 E VPQ lb n7391739n is predense below p Since D is open it is actually dense below p Choose a maximal antichain A in D For each 4 E A choose a name nq such that 4 lb nq 71 Tn By the previous lemma there is a name a such that for all 4 E A 4 lb 0 77 Since A is predense below p 0 lb 9007717m 7 D De nition 916 Let lP be a partial order and let be a P name for a partial order ie a P name such that 1127 forces Q39to be a partial order The twostep iteTatizm of lP and Q is the partial order lP Q consisting of all pairs 17 where p is a condition in lP and 4 is a P name such that p lb L E 39 Let Sp denote the order on lP and let SQ be a P name for the order on We de ne the order S on lP Q as follows 10141 S 102412 iff p1 Sp p2 and P1 lb 41 Q 42 We will drop the subscripts lP and Q if they are clear from the context Observe that with this de nition of the iteration of lP and Q lP turns out to be a proper class Hence we rede ne lP Q as p E lP rkLj lt rklP w rkQ w even though this de nition obviously lacks the elegance of the rst de nition Now whenever p E lP and is a P name such that p lb L E Q then there is a P name T such that p T E lP Q and p lb T Lj Whenever we choose a name for an element of Q we implicitly assume that we only consider names of rank lt rklP Ha rkQ 0 42 STEFAN GESCHKE Now let 1Q be a name for the largest element of Then obviously7 ilP gtlP szgt gtplp is an embedding of partial orders If H is ll Q generic over the ground model M7 We de ne G i llH and F ng 3p 6 Gp j E Lemma 917 G is Pgeneric over M and F is Qggeneric over MlGl Proof It is easily checked that G is a lter Let D E M be a dense subset of lP Then the set D p 6 ll 96 z p E D is dense in ll 96 and hence there is p E H N D Since 104 S p1Q7 p1Q E H and thus p E G N D We now show that F is a lter in Q3 Suppose that 43 E F and 39fg E QG is such 43 S b3 Then there is p E G such that p lb L S 39f Since p E G 11712 E H Since 43 6 F7 there is p 6 ll such that p tj E H Since H is a filter7 p and p tj have a common extension 10 in H Now p lb L S 39b and p lb s S L It follows that p lb s S 39f Since p S p we have 17 s S 10 739quot and thus 39b3 6 F A similar argument shows that any two elements of F have a common extension in Now let D E MlGl be a dense subset of Q3 There is a lP name E M for D By the Maximality Principle we may assume that 11127 forces to be a dense subset of Consider the set D pq39 ElP xszlbLjeD This set is dense in ll 96 Let 104 be an element of like Since is forced to be dense in and by the Maximality Principle7 there is a name 39 such that p forces 39f to be an element of D that is an extension of L Now pi S 104 and p E D It follows that D is dense in ll 96 Since H is ll Q generic over M7 there is p E D N H Now p E H and thus p E C By the de nition of D 7 p lb L E By the de nition of F7 4G 6 F It follows that D N F 3e 0 Therefore F is generic over D Lemma 918 If M lP and are as above G is Pgenen39c over M and F is Qggenen39c over MlG then HGFptjszGALjGeF 239s ll Qgenen39c over M Proof Exercise D Lemma 919 If is 000 and 11127 lb Q is 000quot then PW is 000 Proof Assume there is a subset pmtja a lt ml of lP such that pm Lia is incompatible with 10345 if a f Consider the name a 641004 a lt M1 Since lP is ccc7 the ml of the ground model remains ml in the generic extension by lP Now let G be P generic over M and let 15 6 ac be distinct Suppose 403G and Lj a are compatible Then there is a lP name 39f for a condition in that is a common extension of dag and Lj g Some p E G forces that 39b is a common extension of Lia and 45 We may assume that p is a common extension of pa and pg Now p 739 is a common extension of 100440 and 10343 a contradiction It follows that the daa are pairwise incompatible Since Q3 is ccc7 it follows that 0G is countable Hence the supremum of ac is a countable ordinal MODELS OF SET THEORY 43 We now forget about the particular lter G again and choose a P name E M for the supremum of 0 Since P is ccc7 there is a countable set C Q wl such that 1127 forces to be an element Let 7 be the supremum of C By the choice of B 11127 lb S Ry But by the de nition of this means that no pa with a gt 7 can be an element of a P generic lter over M7 a contradiction 94 Long iterations We will now de ne iterations of in nite length De nition 920 Let 6 be an ordinal PD D S57 Q lt5 is a nite support iter ation length 6 if the following conditions are satis ed 1 For every 1 S 6 Pa is a partial order consisting of sequences of length a In particular7 P0 is the trivial partial order 2 lfalt S6andp6Pgthenp laePa 3 For every 1 lt 6 Qa is a POLname for a partial order and Pa1 Pa Qa Since Pa consists of sequences of length a it is natural to consider Pa Qa as consisting of sequences of length a l 4 If B S 6 is a limit ordinal7 then P5 consists of all sequences p of length 6 such that the support sump a lt 511001 log ofp is nite and for all a lt B p l a 6 Pa If S denotes the order on P5 and pq 6 Pg then p S q if for all a lt B p a lb paSaqa where SD is a name for the order on Q04 De nition 921 Let P and Q be partial orders and let e P A Q be an embedding Le7 let e be 11 and such that for all pmpl 6 P7 p0 S p1 iff ep0 S ep1 Then e is a complete embedding if it preserves L and for all g E Q there is p E P such that whenever r E P is an extension of p7 then r is compatible with q A 01 V Lemma 922 Let e P A Q be an embedding of partial orders in the ground model M Then e is a complete embedding i for every Qgeneric lter F over M G e 1F is Pgeneric over If e P A Q is a complete embedding7 then there is a P name Q P for a forcing notion such that forcing with Q is equivalent to forcing with P 96 P Lemma 923 Let PD D S57 Qgglt5 be a nite support iteration and let 6 lt 6 For every p 6 P5 let egp 6 P5 be such that egp l B p and for all a lt 6 with a 2 egp a lQa Then e is a complete embedding Now let G be P5 generic over the ground model M Then for every 6 lt 6 G B eEWG is Pggeneric over M Let a lt 6 Then Pa1 Pa Qa and hence there is a Qageneric lter Ga over MG a such that G l a 1 G 196 Ga Lemma 924 Let Paa55Qgglt5 be a nite support iteration If for each a lt 6 39 Pa lb Qa is cccquot7 then P5 is ccc In short nite support iterations of ccc forcings are ccc Theorem 925 Martin s Axiom is consistent with the negation of CH Proof Let M be a countable transitive model of GCH In M we construct an iteration 39 Pahsam Q llkkzl of ccc forcing notions such that for all a lt N2 Qa is forced to be of size N1 and for every PNZgeneric lter C over M and every ccc partial order Q of size N1 in 44 STEFAN GESCHKE MG there are co nally many a lt N2 such that 1204ng It can be shown that MG MA 2N0 Ng D MODELS OF SET THEORY 45 REFERENCES 1 T Jech Set Theory Academic Press 1978 2 K Kunen Set Theory An Intmdnction to Independence Pmofs North Holland 1980 DEPARTMENT OF MATHEMATICS BOISE STATE UNIVERSITY 1910 UNIVERSITY DRIVE BOISE ID 8372571555 Eimail addTess geschkeemathjoisestateedu

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.