MathML Crowdfunding
MathML
Crowdfunding

Blog de Frédéric

To content | To menu | To search

Tag - website updates

Entries feed - Comments feed

Wednesday, July 24 2013

Exercises in Set Theory: Large Cardinals

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

Saturday, June 1 2013

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. Peter Krautzberger pointed out that the proof could probably work assuming only Martin’s Axiom. This was indeed proved by Booth in 1970 and 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.

Friday, May 3 2013

Exercises in Set Theory: Applications of Forcing

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

The exercises from this chapter was a good opportunity to play a bit more with the forcing method. Exercise 15.15 seemed a straightforward generalization of Easton’s forcing but turned out to be a bit technical. I realized that the forcing notion used in that exercise provides a result in ZFC (a bit like Exercises 15.31 and 15.32 allow to prove some theorems on Boolean Algebras by Forcing).

Remember that 0=0,1=20,2=21,ω=supn,,α+1=2α,\beth_{0}=\aleph_{0},\beth_{1}=2^{{\beth_{0}}},\beth_{2}=2^{{\beth_{1}}}...,% \beth_{\omega}=\sup\beth_{n},...,\beth_{{\alpha+1}}=2^{{\beth_{{\alpha}}}},... is the normal sequence built by application of the continuum function at successor step. One may wonder: is α\beth_{\alpha} regular?

First consider the case where α\alpha is limit. The case α=0\alpha=0 is clear (0=0\beth_{0}=\aleph_{0} is regular) so assume α>0\alpha>0. If α\alpha is an inacessible cardinal, it is easy to prove by induction that for all β<α\beta<\alpha we have β<α\beth_{\beta}<\alpha: at step β=0\beta=0 we use that α\alpha is uncountable, at successor step that it is strong limit and at limit step that it is regular. Hence α=α\beth_{\alpha}=\alpha and so is regular. If α\alpha is not a cardinal then cf(α)=cf(α)|α|<αα\operatorname{cf}(\beth_{\alpha})=\operatorname{cf}(\alpha)\leq|\alpha|<\alpha% \leq\beth_{\alpha} so α\beth_{\alpha} is singular. If α\alpha is a cardinal but not strong limit then there is β<α\beta<\alpha such that 2βα2^{\beta}\geq\alpha. Since β<αα\beta<\alpha\leq\beth_{\alpha} there is γ<α\gamma<\alpha such that γ>β\beth_{\gamma}>\beta. Then αγ+1=2γ>2βα\beth_{\alpha}\geq\beth_{{\gamma+1}}=2^{{\beth_{\gamma}}}>2^{\beta}\geq\alpha. So cf(α)=cf(α)α<α\operatorname{cf}(\beth_{\alpha})=\operatorname{cf}(\alpha)\leq\alpha<\beth_{\alpha} and α\beth_{\alpha} is singular. Finally, if α\alpha is a singular cardinal, then again cf(α)=cf(α)<αα\operatorname{cf}(\beth_{\alpha})=\operatorname{cf}(\alpha)<\alpha\leq\beth_{\alpha} and α\beth_{\alpha} is singular.

What about the successor case i.e. α+1\beth_{{\alpha+1}}? By Corollary 5.3 from Thomas Jech’s book any α\alpha, we can show that α+1\aleph_{{\alpha+1}} is a regular cardinal. The Generalized Continuum Hypothesis says that α,α=α\forall\alpha,\aleph_{\alpha}=\beth_{\alpha}. Since it holds in LL we can not prove in ZFC that for some α\alpha, α+1\beth_{{\alpha+1}} is singular.

The generic extension V[G]VV[G]\supseteq V constructed in exercise 15.15 satisfies GCH and so it’s another way to show that α+1\beth_{{\alpha+1}} can not be proved to be singular for some α\alpha. However, it provides a better result: by construction, V[G]α+1V=(αV)+V[G]\models\beth_{{\alpha+1}}^{V}={(\beth_{{\alpha}}^{V})}^{+} and so V[G][α+1V is a regular cardinal]V[G]\models[\beth_{{\alpha+1}}^{V}\text{ is a regular cardinal}]. Since ‘‘regular cardinal’’ is a Π1\Pi_{1} notion we deduce that α+1\beth_{{\alpha+1}} is a regular cardinal in VV.

Now the question is: is there any ‘‘elementary’’ proof of the fact that α+1\beth_{{\alpha+1}} is regular i.e. without using the forcing method?

--update: of course, I forgot to mention that by König’s theorem, 2α=α+1cf(α+1)=cf(2α)(α)+2^{{\beth_{{\alpha}}}}=\beth_{{\alpha+1}}\geq\operatorname{cf}(\beth_{{\alpha+% 1}})=\operatorname{cf}(2^{{\beth_{{\alpha}}}})\geq{(\beth_{{\alpha}})}^{+} so the singularity of α+1\beth_{{\alpha+1}} would imply the failure of the continuum hypothesis for the cardinal α\beth_{\alpha} and this is not provable in ZFC.

Wednesday, March 20 2013

Exercises in Set Theory: Classical Independence Results

Here are new solutions to exercises from Thomas Jech’s book ‘‘Set Theory’’:

Doing the exercises from these chapters gave me the opportunity to come back to the ‘‘classical’’ results about the independence of the Axiom of Choice and (Generalized) Continuum Hypothesis by Kurt Gödel and Paul Cohen. It’s funny to note that it’s easier to prove that AC holds in LL (essentially, the definition by ordinal induction provides the well-ordering of the class of contructible sets) than to prove that GCH holds in LL (you rely on AC in LL and on the technical condensation lemma). Actually, I believe Gödel found his proof for AC one or two years after the one for GCH. On the other hand, it is easy to make GCH fails (just add 2\aleph_{2} Cohen reals by Forcing) but more difficult to make AC fails (e.g. AC is preserved by Forcing). This can be interpreted as AC being more ‘‘natural’’ than GCH.

After reading the chapters again and now I analyzed in details the claims, I’m now convinced about the correctness of the proof. There are only two points I didn’t verify precisely about the Forcing method (namely that all axioms of predicate calculus and rules of inference are compatible with the Forcing method ; that the Forcing/Generic Model theorems can be transported from the Boolean Algebra case to the general case) but these do not seem too difficult. Here are some notes about claims that were not obvious to me at the first reading. As usual, I hope they might be useful to the readers of that blog:

  1. In the first page of chapter 13, it is claimed that for any set MM, Mdef(M)M\in\mathrm{def}(M) and Mdef(M)𝒫(M)M\subseteq\mathrm{def}(M)\subseteq\operatorname{\mathcal{P}}(M). The first statement is always true because M={xM:(M)x=x}def(M)M=\{x\in M:(M,\in)\models x=x\}\in\mathrm{def}(M) and (x=x)(M){(x=x)}^{{(M,\in)}} is x=xx=x by definition. However, the second statement can only be true if MM is transitive (since that implies M𝒫(M)M\subseteq\operatorname{\mathcal{P}}(M)). Indeed, if MM is transitive then for all aMa\in M we have aMa\subseteq M and since xax\in a is Δ0\Delta_{0} we get a={xM:(M)xa}def(M)a=\{x\in M:(M,\in)\models x\in a\}\in\mathrm{def}(M). If moreover we consider xXdef(M)x\in X\in\mathrm{def}(M) then xXMx\in X\subseteq M so xMdef(M)x\in M\subseteq\mathrm{def}(M) and def(M)\mathrm{def}(M) is also transitive. Hence the transitivity of the LαL_{\alpha} can still be shown by ordinal induction.

  2. The proof of lemma 13.7 can not be done exactly by induction on the complexity of GG, as suggested. For example to prove (ii) for G=G2=×G=G_{2}=\cdot\times\cdot, we would consider uF()×H()φ(u)aF(),bH(),φ((a,b))\exists u\in F(...)\times H(...)\varphi(u)\Leftrightarrow\exists a\in F(...),% \exists b\in H(...),\varphi((a,b)) and would like to say that φ((a,b))\varphi((a,b)) is Δ0\Delta_{0}. Nevertheless, we can not deduce that from the induction hypothesis. Hence the right thing to do is to prove the lemma for G1={,}G_{1}=\{\cdot,\cdot\} first and deduce the lemma for G=(,)G=(\cdot,\cdot) (and G=(,,)G^{{\prime}}=(\cdot,\cdot,\cdot)). Then we can proceed by induction.

  3. In the proof of theorem 13.18, it is mentioned that the assumption

    1. x<αyx<_{\alpha}y implies x<βyx<_{\beta}y

    2. xLαx\in L_{\alpha} and yLβLαy\in L_{\beta}\setminus L_{\alpha} implies x<βyx<_{\beta}y

    implies that if xyLαx\in y\in L_{\alpha} then x<αyx<_{\alpha}y. To show that, we consider βα\beta\leq\alpha the least ordinal such that yLβy\in L_{\beta}. In particular, β\beta is not limit (L0=L_{0}=\emptyset and if yLβy\in L_{\beta} for some limit β>0\beta>0 then there is γ<β\gamma<\beta such that yLγy\in L_{\gamma}) and we can write it β=γ+1\beta=\gamma+1. We have yLβ=Lγ+1y\in L_{\beta}=L_{{\gamma+1}} so there is a formula φ\varphi and elements a1,,anLγa_{1},...,a_{n}\in L_{\gamma} such that xy={zLγ:(Lγ)φ(z,a1,,an)}x\in y=\{z\in L_{\gamma}:(L_{\gamma},\in)\models\varphi(z,a_{1},...,a_{n})\}. Hence xLγx\in L_{\gamma}. Moreover by minimality of β\beta, yLβLγy\in L_{\beta}\setminus L_{\gamma} so by (ii) we have x<βyx<_{\beta}y and by (i) x<αyx<_{\alpha}y.

  4. In lemma 14.18, we have expressions that seem ill-defined for example au(t)a_{u}(t) where tdom(au)t\notin\operatorname{dom}(a_{u}). This happens in other places, like lemma 14.17 or definition 14.27. The trick is to understand that the functions are extended by 0. Indeed, for any x,yVBx,y\in V^{B} if xyx\subseteq y and tdom(y)dom(x),y(t)=0\forall t\in\operatorname{dom}(y)\setminus\operatorname{dom}(x),y(t)=0 then

    yx\displaystyle\|y\subseteq x\| =tdom(y)(-y(t)+tx)\displaystyle=\prod_{{t\in\operatorname{dom}(y)}}\left(-y(t)+{\|t\in x\|}\right)
    =tdom(x)(-x(t)+tx)\displaystyle=\prod_{{t\in\operatorname{dom}(x)}}\left(-x(t)+{\|t\in x\|}\right)
    =xx=1\displaystyle=\|x\subseteq x\|=1

    and similarly we get x=y=1\|x=y\|=1. Then we can use the inequality page 207 (φ(x)=x=yφ(x)φ(y)=x=yφ(y)φ(x)\|\varphi(x)\|=\|x=y\|\cdot\|\varphi(x)\|\leq\|\varphi(y)\|=\|x=y\|\cdot\|% \varphi(y)\|\leq\|\varphi(x)\|) to replace xx by its extension yy.

  5. In lemma 14.23, the inequality

    x is an ordinalxαˇ+x=αˇ+αˇx\|x\text{ is an ordinal}\|\leq\|x\in\check{\alpha}\|+\|x=\check{\alpha}\|+\|% \check{\alpha}\in x\|

    seems obvious but I don’t believe that it can be proved so easily at that point. For example the proof from chapter 2 requires at least the Separation axiom and the Δ0\Delta_{0} formulation from chapter 10 is based on the Axiom of Regularity. To solve that issue, it seems to me that the lemma should be moved after the proof that axioms of ZFC are valid in VBV^{B}. This is not an issue since lemma 14.23 is only used much later in lemma 14.31.

  6. Many details could be added to the proof of theorem 14.24, but let’s just mention Powerset. For any uVBu\in V^{B}, some udom(Y)u^{{\prime}}\in\operatorname{dom}(Y) is defined and satisfies uXu=u\|u\subseteq X\|\leq\|u=u^{{\prime}}\| (this follows from the definitions, using the Boolean inequality -a+b-a+ba-a+b\leq-a+b\cdot a to conclude). Since moreover tdom(Y),Y(t)=1\forall t\in\operatorname{dom}(Y),Y(t)=1 we get

    uXuY\displaystyle\|u\subseteq X\|\implies\|u\in Y\| -u=u+tdom(Y)(u=tY(t))\displaystyle\geq-\|u=u^{{\prime}}\|+\sum_{{t\in\operatorname{dom}(Y)}}\left(% \|u=t\|\cdot Y(t)\right)
    =tdom(Y)-(utu=u)\displaystyle=\sum_{{t\in\operatorname{dom}(Y)}}-\left(\|u\neq t\|\cdot\|u=u^{% {\prime}}\|\right)
    tdom(Y)u=t=1\displaystyle\geq\sum_{{t\in\operatorname{dom}(Y)}}\|u^{{\prime}}=t\|=1
  7. In theorem 14.34, we prove that any κ\kappa regular in VV remains regular in V[G]V[G] (the hard case is really κ\kappa uncountable and this assumption is implicitely used later to say that α<λAα\bigcup_{{\alpha<\lambda}}A_{\alpha} is bounded). It may not be obvious why this is enough. First recall that for any ordinal α\alpha, cfV[G](α)cfV(α)\operatorname{cf}^{{V[G]}}(\alpha)\leq\operatorname{cf}^{V}(\alpha), |α|V[G]|α|V{|\alpha|}^{{V[G]}}\leq{|\alpha|}^{{V}}, and any (regular) cardinal in V[G]V[G] is a (regular) cardinal in VV. Next we have,

    αOrd,cfV[G](α)cfV(α)\displaystyle\exists\alpha\in\mathrm{Ord},\operatorname{cf}^{{V[G]}}(\alpha)% \leq\operatorname{cf}^{{V}}(\alpha) αOrd,cfV[G](cfV(α))cfV[G](α)<cfV(α)\displaystyle\implies\exists\alpha\in\mathrm{Ord},\operatorname{cf}^{{V[G]}}(% \operatorname{cf}^{V}(\alpha))\leq\operatorname{cf}^{{V[G]}}(\alpha)<% \operatorname{cf}^{{V}}(\alpha)
    β regular cardinal in V, not regular cardinal in V[G]\displaystyle\implies\exists\beta\textrm{ regular cardinal in }V,\textrm{ not % regular cardinal in }V[G]
    βOrd,cfV[G](β)<β=cfV(β)\displaystyle\implies\exists\beta\in\mathrm{Ord},\operatorname{cf}^{{V[G]}}(% \beta)<\beta=\operatorname{cf}^{V}(\beta)

    that is αOrd,cfV[G](α)=cfV(α)\forall\alpha\in\mathrm{Ord},\operatorname{cf}^{{V[G]}}(\alpha)=\operatorname{% cf}^{{V}}(\alpha) is equivalent to ‘‘VV and V[G]V[G] have the same regular cardinals’’. Similarly, we can prove that αOrd,|α|V[G]=|α|V\forall\alpha\in\mathrm{Ord},{|\alpha|}^{{V[G]}}={|\alpha|}^{{V}} is equivalent to ‘‘VV and V[G]V[G] have the same cardinals’’.

    The proof of theorem 14.34 shows that ‘‘VV and V[G]V[G] have the same regular cardinals’’ and so to complete the proof, it is enough to show that α,cfV[G](α)=cfV(α)\forall\alpha,\operatorname{cf}^{{V[G]}}(\alpha)=\operatorname{cf}^{{V}}(\alpha) implies α,|α|V[G]=|α|V\forall\alpha,{|\alpha|}^{{V[G]}}={|\alpha|}^{{V}}. So suppose α,cfV[G](α)=cfV(α)\forall\alpha,\operatorname{cf}^{{V[G]}}(\alpha)=\operatorname{cf}^{{V}}(\alpha) and assume that there is α\alpha such that |α|V[G]<|α|V{|\alpha|}^{{V[G]}}<{|\alpha|}^{{V}}. Consider the least such α\alpha. If β=|α|V\beta={|\alpha|}^{{V}} then βα\beta\leq\alpha so |β|V[G]|α|V[G]<|α|V=β{|\beta|}^{{V[G]}}\leq{|\alpha|}^{{V[G]}}<{|\alpha|}^{{V}}=\beta. By minimality of α\alpha, β=α\beta=\alpha and so α\alpha is a cardinal in VV. α\alpha is actually regular in VV. Otherwise, suppose cfV(α)<α\operatorname{cf}^{V}(\alpha)<\alpha and let α=β<cfV(α)Xβ\alpha=\bigcup_{{\beta<\operatorname{cf}^{V}(\alpha)}}X_{\beta} such that |Xβ|V<|α|V{|X_{\beta}|}^{V}<{|\alpha|}^{V}. By minimality of α\alpha, we have |cfV(α)|V[G]=|cfV(α)|V{|\operatorname{cf}^{V}(\alpha)|}^{{V[G]}}={|\operatorname{cf}^{V}(\alpha)|}^{% {V}} and |Xβ|V[G]=|Xβ|V{|X_{\beta}|}^{{V[G]}}={|X_{\beta}|}^{{V}}. Then |α|V[G]=|cfV(α)|V[G]supβ<cfV(α)|Xβ|V[G]=|cfV(α)|Vsupβ<cfV(α)|Xβ|V=|α|V{|\alpha|}^{{V[G]}}={|\operatorname{cf}^{V}(\alpha)|}^{{V[G]}}\sup_{{\beta<% \operatorname{cf}^{V}(\alpha)}}{|X_{\beta}|}^{{V[G]}}={|\operatorname{cf}^{V}(% \alpha)|}^{{V}}\sup_{{\beta<\operatorname{cf}^{V}(\alpha)}}{|X_{\beta}|}^{{V}}% ={|\alpha|}^{{V}}, a contradiction. Finally, we get cfV(α)=α=|α|V>|α|V[G]cfV[G](α)\operatorname{cf}^{V}(\alpha)=\alpha={|\alpha|}^{V}>{|\alpha|}^{{V[G]}}\geq% \operatorname{cf}^{{V[G]}}(\alpha). This is again a contradiction and so α,|α|V[G]=|α|V\forall\alpha,{|\alpha|}^{{V[G]}}={|\alpha|}^{{V}}.

Friday, January 25 2013

Exercises in Set Theory

I'm finally done with the first part "Basic Set Theory" :-) The two last chapters:

- page 1 of 4