Frédéric Wang    About    Mathematics    Computer Science    Miscellaneous    Archive

Exercises in Set Theory: Iterated Forcing and Martin’s Axiom

New solutions to exercises from Thomas Jech’s book “Set Theory”:

Last November, I tried to provide some details of the proof given in chapter 7, regarding the fact that the continuum hypothesis implies the existence of a Ramsey ultrafilter. Booth actually proved in 1970 that this works assuming only Martin’s Axiom. The missing argument is actually given in exercise 16.16. For completeness, I copy the details on this blog post.

Remember that the proof involves contructing a sequence (Xα)α<20{(X_{\alpha})}_{\alpha<2^{\aleph_{0}}} of infinite subsets of ω\omega. The induction hypothesis is that at step α<20\alpha<2^{\aleph_{0}}, for all β1,β2<α\beta_{1},\beta_{2}<\alpha we have β1<β2Xβ2Xβ1\beta_{1}<\beta_{2}\implies X_{\beta_{2}}\setminus X_{\beta_{1}} is finite. It is then easy to show the result for the successor step, since the construction satisfies Xα+1XαX_{\alpha+1}\subseteq X_{\alpha}. However at limit step, to ensure that XαXβX_{\alpha}\setminus X_{\beta} is finite for all β<α\beta<\alpha, the proof relies on the continunum hypothesis. This is the only place where it is used.

Assume instead Martin’s Axiom and consider a limit step α<20\alpha<2^{\aleph_{0}}. Define the forcing notion Pα={(s,F):s[ω]<ω,F[α]<ω}P_{\alpha}=\{(s,F):s\in{[\omega]}^{<\omega},F\in{[\alpha]}^{<\omega}\} and (s,F)(s,F)(s^{\prime},F^{\prime})\leq(s,F) iff sss\subseteq s^{\prime}, FFF\subseteq F^{\prime} and ssXβs^{\prime}\setminus s\subseteq X_{\beta} for all βF\beta\in F. It is clear that the relation is reflexive and antisymmetric. The transitivity is almost obvious, just note that if (s3,F3)(s2,F2)(s_{3},F_{3})\leq(s_{2},F_{2}) and (s2,F2)(s1,F1)(s_{2},F_{2})\leq(s_{1},F_{1}) then for all βF1F2\beta\in F_{1}\subseteq F_{2} we have s3s1s3s2s2s1Xβs_{3}\setminus s_{1}\subseteq s_{3}\setminus s_{2}\cup s_{2}\setminus s_{1}% \subseteq X_{\beta}.

The forcing notion satisfies ccc or even property (K): since [ω]<ω{[\omega]}^{<\omega} is countable, for any uncountable subset WW there is t[ω]<ωt\in{[\omega]}^{<\omega} such that Z={(s,F)W:s=t}Z=\{(s,F)\in W:s=t\} is uncountable. Then any (t,F1),(t,F2)Z(t,F_{1}),(t,F_{2})\in Z have a common refinement (t,F1F2)(t,F_{1}\cup F_{2}).

For all n<ωn<\omega, define Dn={(s,F):|s|n}D_{n}=\{(s,F):|s|\geq n\}. Let β1>β2>>βk\beta_{1}>\beta_{2}>...>\beta_{k} the elements of FF. We show by induction on 1mk1\leq m\leq k that i=1mXβi\bigcap_{i=1}^{m}X_{\beta_{i}} is infinite. This is true for m=1m=1 by assumption. If it is true for m-1m-1 then

i=1m-1Xβi=i=1mXβii=1mXβiXβm\bigcap_{i=1}^{m-1}X_{\beta_{i}}=\bigcap_{i=1}^{m}X_{\beta_{i}}\cup\bigcap_{i=% 1}^{m}X_{\beta_{i}}\setminus X_{\beta_{m}}

The left hand side is infinite by induction hypothesis. The second term of the right hand side is included in Xβ1XβmX_{\beta_{1}}\setminus X_{\beta_{m}} and thus is finite. Hence the first term is infinite and the result is true for mm. Finally, for m=km=k, we get that βFXβ\bigcap_{\beta\in F}X_{\beta} is infinite. Pick x1,x2,,xnx_{1},x_{2},...,x_{n} distinct elements from that set and define (s,F)=(s{x1,xn},F)(s^{\prime},F^{\prime})=(s\cup\{x_{1},...x_{n}\},F). We have (s,F)Dn(s^{\prime},F^{\prime})\in D_{n}, sss\subseteq s^{\prime}, FFF\subseteq F^{\prime} and for all βF\beta\in F, ss={x1,xn}Xβs^{\prime}\setminus s=\{x_{1},...x_{n}\}\subseteq X_{\beta}. This shows that DnD_{n} is dense. For each β<α\beta<\alpha, the set Eβ={(s,F):βF}E_{\beta}=\{(s,F):\beta\in F\} is also dense: for any (s,F)(s,F) consider (s,F)=(s,F{β})(s^{\prime},F^{\prime})=(s,F\cup\{\beta\}).

By Martin’s Axiom there is a generic filter GG for the family {Dn:n<ω}{Eβ:β<α}\{D_{n}:n<\omega\}\cup\{E_{\beta}:\beta<\alpha\} of size |α|<20|\alpha|<2^{\aleph_{0}}. Let Xα={n<ω:(s,F)G,ns}X_{\alpha}=\{n<\omega:\exists(s,F)\in G,n\in s\}. For all n<ωn<\omega, there is (s,F)GDn(s,F)\in G\cap D_{n} and so |Xα||s|n|X_{\alpha}|\geq|s|\geq n. Hence XαX_{\alpha} is infinite. Let β<α\beta<\alpha and (s1,F1)GEβ(s_{1},F_{1})\in G\cap E_{\beta}. For any xXαx\in X_{\alpha}, there is (s2,F2)G(s_{2},F_{2})\in G such that xs2x\in s_{2}. Hence there is (s3,F3)G(s_{3},F_{3})\in G a refinement of (s1,F2),(s2,F2)(s_{1},F_{2}),(s_{2},F_{2}). We have xs2s3x\in s_{2}\subseteq s_{3} and s3s1Xβs_{3}\subseteq s_{1}\subseteq X_{\beta}. Hence XαXβs1X_{\alpha}\setminus X_{\beta}\subseteq s_{1} is finite and the induction hypothesis is true at step α\alpha.