Set theory - Chapter 5: The Axiom of Choice and Cardinal Arithmetic

5.1

We saw in exercise 4.6 that the set of all open sets has cardinality 202^{{\aleph_{0}}}. The operation ”taking the complement of a set” puts this set in bijection with the set of all closed sets. Since every perfect set is closed, there are at most 202^{{\aleph_{0}}} many such sets. Moreover, every nonempty closed interval of reals [a,b][a,b] is perfect and so there are exactly 202^{{\aleph_{0}}} perfect sets of reals. We consider an enumeration Pα,α<20\langle P_{\alpha},\alpha<2^{{\aleph_{0}}}\rangle of all perfect sets.

Now, we construct sequences aα,α<20\langle a_{\alpha},\alpha<2^{{\aleph_{0}}}\rangle and bα,α<20\langle b_{\alpha},\alpha<2^{{\aleph_{0}}}\rangle by induction by picking for each α<20\alpha<2^{{\aleph_{0}}} two elements aα\({aξ:ξ<α}{bξ:ξ<α})a_{\alpha}\in\mathbb{R}\backslash\left(\{a_{{\xi}}:\xi<\alpha\}\cup\{b_{{\xi}}% :\xi<\alpha\}\right) and bαPα\{aξ:ξα}b_{{\alpha}}\in P_{\alpha}\backslash\{a_{{\xi}}:\xi\leq\alpha\}. This choice is possible because ||=|Pα|=20>|α||\mathbb{R}|=|P_{\alpha}|=2^{{\aleph_{0}}}>|\alpha| (recall that any perfect set has cardinality 202^{{\aleph_{0}}}).

Now let S={aα:α<20}S=\{a_{\alpha}:\alpha<2^{{\aleph_{0}}}\}. The aαa_{\alpha} are distinct by definition and so |S|=20|S|=2^{{\aleph_{0}}}. Let a<20a<2^{{\aleph_{0}}}. For all α<ξ<20\alpha<\xi<2^{{\aleph_{0}}}, aξbαa_{\xi}\neq b_{{\alpha}} by definition of aξa_{{\xi}}. For all ξα\xi\leq\alpha, bαaξb_{{\alpha}}\neq a_{{\xi}} by definition of bαb_{{\alpha}}. Hence bαSb_{{\alpha}}\notin S and because bαPαb_{{\alpha}}\in P_{\alpha} we have PαSP_{\alpha}\nsubseteq S.

Finally, SS is a set of reals of cardinality 202^{{\aleph_{0}}} without a perfect subset.

5.2

Let XX be an infinite set and α=|X|\aleph_{\alpha}=|X| its aleph and SS the set of all finite subsets of XX. Then we have

|S|\displaystyle|S| =|[X]<ω|\displaystyle=|{[X]}^{{<\omega}}|
=n<ωαn\displaystyle=\sum_{{n<\omega}}\aleph_{\alpha}^{n}
=n<ωα\displaystyle=\sum_{{n<\omega}}\aleph_{\alpha}
=0α\displaystyle=\aleph_{0}\aleph_{\alpha}
=α\displaystyle=\aleph_{\alpha}
=|X|\displaystyle=|X|

5.3

Let PP a linearly ordered set and κ\kappa a cardinal such that for all xPx\in P, the initial segment Px={yP:y<x}P_{x}=\{y\in P:y<x\} is of size less than κ\kappa.

If MM is a greatest element of PP, then clearly |P|=|PM{M}|=1+|PM|κ|P|=|P_{M}\cup\{M\}|=1+|P_{M}|\leq\kappa since |PM|<κ|P_{M}|<\kappa.

Otherwise, let x0<x1<xα<x_{0}<x_{1}<...x_{\alpha}<... an enumeration of PP of size λ=|P|\lambda=|P|. Then for all α<λ\alpha<\lambda, |α|=|Pxα|<κ|\alpha|=|P_{{x_{\alpha}}}|<\kappa thus α<κ\alpha<\kappa. Since PP does not have a greatest element, λ\lambda is limit i.e. λ=supα<λακ\lambda=\sup_{{\alpha<\lambda}}\alpha\leq\kappa. Again |P|κ|P|\leq\kappa.

5.4

I actually discovered and proved the statement of this exercise when I was in high school, but here is a more straightforward proof:

Let AA be a well-ordered set. For all subsets XYX\neq Y, XΔYX\Delta Y is non empty. Define X<YX<Y if the least element of XΔYX\Delta Y belongs to XX. Note that by definition << is irreflexive and assymetric. If the order is well defined, then it is clearly total (if XYX\neq Y, the least element of XΔYX\Delta Y is either in XX or in YY).

It remains to prove that << is transitive. Let X,Y,ZX,Y,Z such that X<YX<Y and Y<ZY<Z. We define and have:

  1. (1)

    m1=min(XΔY)X\Ym_{1}=\min(X\Delta Y)\in X\backslash Y

  2. (2)

    m2=min(YΔZ)Y\Zm_{2}=\min(Y\Delta Z)\in Y\backslash Z

  3. (3)

    m3=min(XΔZ)m_{3}=\min(X\Delta Z)

We want to prove that m3Xm_{3}\in X. Suppose the contrary i.e. m3Z\Xm_{3}\in Z\backslash X.

First, suppose m3Ym_{3}\in Y. Then m3Y\Xm_{3}\in Y\backslash X and by (1), we have m1Xm_{1}\in X and m1<m3m_{1}<m_{3}. By (3) we get m1Zm_{1}\in Z. By (1), we get m1Z\Ym_{1}\in Z\backslash Y. By (2) we get m2<m1m_{2}<m_{1} and m2Ym_{2}\in Y. By (1) we get m2Xm_{2}\in X. By (2) we get m2X\Zm_{2}\in X\backslash Z. By (3) we get m3<m2m_{3}<m_{2}. Finally, we have obtained m3<m2<m1<m3m_{3}<m_{2}<m_{1}<m_{3}. A contradiction.

Now, suppose instead that m3Ym_{3}\notin Y. Then m3Z\Ym_{3}\in Z\backslash Y so by (2) we have m2<m3m_{2}<m_{3} and m2Zm_{2}\notin Z. By (3) we get m2Xm_{2}\notin X and still m2<m3m_{2}<m_{3} and moreover by (2) we have m2Ym_{2}\in Y. By (1), we get m1<m2<m3m_{1}<m_{2}<m_{3} and m1Xm_{1}\in X. From m1<m3m_{1}<m_{3} and m1Xm_{1}\in X we get by (3) that m1Zm_{1}\in Z and we still have m1<m2m_{1}<m_{2}. By (2), we get m1Ym_{1}\in Y. But this contradicts (1).

5.5

Let SS be a family of nonempty sets. Let P={f:f is a choice function on some ZS}P=\{f:f\text{ is a choice function on some }Z\subset S\}, ordered by inclusion. It is clearly non empty since there is a choice function on any finite ZSZ\subset S. If we have a chain of choice functions fα,α<λf_{\alpha},\alpha<\lambda then f=α<λfαf=\cup_{{\alpha<\lambda}}f_{\alpha} is a choice function on α<λdom(fα)\cup_{{\alpha<\lambda}}{\operatorname{dom}(f_{\alpha})} and so is an upper bound of the chain. By Zorn’s Lemma, PP has a maximal element ff. Moreover dom(f)=S\operatorname{dom}(f)=S for otherwise, we could extended ff and it would not be maximal. So ff is a choice function on SS.

5.6

Let AA be an infinite set and define for all nn\in\mathbb{N}, the set AnA_{n} of one-to-one sequences in AA of length nn. Each AnA_{n} is nonempty so assuming the countable AC, there exists a choice function ff on S={An:n}S=\{A_{n}:n\in\mathbb{N}\}. Define for all nn\in\mathbb{N}, sn=f(An)s_{n}=f(A_{n}) and B=nran(sn)AB=\cup_{{n\in\mathbb{N}}}\operatorname{ran}(s_{n})\subseteq A. Clearly BB is infinite. For all bBb\in B, we define nbn_{b} to be the least natural integer nn such bran(sn)b\in\operatorname{ran}(s_{{n}}). Then the function g:B×g:B\rightarrow\mathbb{N}\times\mathbb{N} given by g(b)=(nb,snb-1(b))g(b)=(n_{b},s_{{n_{b}}}^{{-1}}(b)) is one-to-one and so BB is countable.

5.7

Let S={An:nN}S=\{A_{n}:n\in N\} a countable family of non-empty set. Let AA be the set of all choices functions on some Sn={Ai|in}S_{n}=\{A_{i}|i\leq n\}. Let fAf\in A is a choice function on SnS_{n}. An+1A_{{n+1}} is non-empty so we can pick xAn+1x\in A_{{n+1}} and define the function f~\tilde{f} on Sn+1S_{{n+1}} by f~|Sn=f\tilde{f}_{{|S_{n}}}=f and f~(An+1)=x\tilde{f}(A_{{n+1}})=x. Then f~A\tilde{f}\in A and f~f\tilde{f}\supset f. Assuming DC, there is a sequence (gn)n{(g_{n})}_{{n\in\mathbb{N}}} of elements of AA such that for all nn\in\mathbb{N}, gn+1gng_{{n+1}}\supset g_{{n}}. Hence we can define g=ngng=\cup_{{n\in\mathbb{N}}}g_{n}. This is a choice function on SS.

5.8

Let κ\kappa be a cardinal. Let’s show that for all α<κ+\alpha<\kappa^{+} there are sets XnααX_{n}^{\alpha}\subset\alpha (nn\in\mathbb{N}) such that α=nXnα\alpha=\bigcup_{n}X_{n}^{\alpha} and for each nn, the order-type of XnαX_{n}^{\alpha} is κn\leq\kappa^{n}.

First for any limit ordinal α<κ+\alpha<\kappa^{+}, we define AαA_{\alpha} the set of increasing sequences of elements α\alpha of length |α||\alpha|. Using AC, we consider a choice function ff on S={Aα:α<κ+}S=\{A_{\alpha}:\alpha<\kappa^{+}\}. We set (αξ)ξ<|α|=f(Aα){(\alpha_{\xi})}_{{\xi<|\alpha|}}=f(A_{\alpha}).

We shall prove the result by induction on α<κ+\alpha<\kappa^{+}. More precisely, we will construct by induction on α<κ+\alpha<\kappa^{+}, countable families of sets XnαX_{n}^{{\alpha}} and associated increasing function fnα:Xnακnf_{n}^{{\alpha}}:X_{n}^{{\alpha}}\rightarrow\kappa^{n}.

  1. (1)

    If α=0\alpha=0, we can just take Xnα=X_{n}^{{\alpha}}=\emptyset and fnα=f_{n}^{{\alpha}}=\emptyset for all nn\in\mathbb{N}.

  2. (2)

    Suppose α=β+1\alpha=\beta+1 is a successor ordinal. In particular, 0κ0\in\kappa. If the induction hypothesis is true for β\beta then we have

    α=β{β}=(ξ<βXnβ){β}\alpha=\beta\cup\{\beta\}=\left(\bigcup_{{\xi<\beta}}X_{n}^{\beta}\right)\cup% \{\beta\}

    and we can take:

    • X0α={β}X_{0}^{\alpha}=\{\beta\} and f0α={(β,0)}f_{0}^{\alpha}=\{(\beta,0)\}

    • For all nn\in\mathbb{N}, Xn+1α=XnβX_{{n+1}}^{\alpha}=X_{n}^{\beta} and fn+1α(x)=fnβ(x)×{0}f_{{n+1}}^{\alpha}(x)=f_{{n}}^{{\beta(x)}}\times\{0\}.

  3. (3)

    If α\alpha is a limit cardinal and the induction hypothesis is true below α\alpha then

    α=ξ<|α|αξ=ξ<|α|(αξ\ξ<ξαξ)=ξ<|α|((nXnαξ)\ξ<ξαξ)=n(ξ<|α|(Xnαξ\ξ<ξαξ))\alpha=\bigcup_{{\xi<|\alpha|}}\alpha_{\xi}=\bigcup_{{\xi<|\alpha|}}\left(% \alpha_{\xi}\backslash{\bigcup_{{\xi^{{\prime}}<\xi}}\alpha_{{\xi^{{\prime}}}}% }\right)=\bigcup_{{\xi<|\alpha|}}\left({\left(\bigcup_{{n\in\mathbb{N}}}X_{n}^% {{\alpha_{\xi}}}\right)}\backslash{\bigcup_{{\xi^{{\prime}}<\xi}}\alpha_{{\xi^% {{\prime}}}}}\right)=\bigcup_{{n\in\mathbb{N}}}\left(\bigcup_{{\xi<|\alpha|}}% \left(X_{n}^{{\alpha_{\xi}}}\backslash\bigcup_{{\xi^{{\prime}}<\xi}}\alpha_{{% \xi^{{\prime}}}}\right)\right)

    and we can take

    • X0α=X_{0}^{{\alpha}}=\emptyset, f0α=f_{0}^{{\alpha}}=\emptyset.

    • For all nn\in\mathbb{N}, Xn+1α=ξ<αYnαξX_{{n+1}}^{{\alpha}}=\bigcup_{{\xi<\alpha}}Y_{n}^{{\alpha_{\xi}}} where Ynαξ=Xnαξ\ξ<ξαξXnαξαξY_{n}^{{\alpha_{\xi}}}=X_{n}^{{\alpha_{\xi}}}\backslash\bigcup_{{\xi^{{\prime}% }<\xi}}\alpha_{{\xi^{{\prime}}}}\subseteq X_{n}^{{\alpha_{\xi}}}\subseteq% \alpha_{{\xi}}. We define for all xXn+1αx\in X_{{n+1}}^{\alpha}, fn+1α(x)=(ξx,fnαξx(x))κn+1f_{{n+1}}^{{\alpha}}(x)=(\xi_{x},f_{n}^{{\alpha_{{\xi_{x}}}}}(x))\in\kappa^{{n% +1}} where ξx\xi_{x} is the least ordinal such that xYnαξxx\in Y_{n}^{{\alpha_{{\xi_{x}}}}}. By construction ff is an increasing function.

5.9

Let {Xi:iI}\{X_{i}:i\in I\} and {Yi:iI}\{Y_{i}:i\in I\} be two disjoint families such that |Xi|=|Yi||X_{i}|=|Y_{i}|. For all iIi\in I, let AiA_{i} be the set of all bijection between XiX_{i} and YiY_{i}. AiA_{i} is nonempty by assumption. Suppose AC and let’s consider a choice function AifiA_{i}\mapsto f_{i} on S={Ai:iI}S=\{A_{i}:i\in I\}. Let X=iIXiX=\cup_{{i\in I}}X_{i} and Y=iIYiY=\cup_{{i\in I}}Y_{i}. For all xXx\in X denote by ixi_{x} the unique index such that xXix\in X_{i} (no need for AC here). Then xfix(x)x\mapsto f_{{i_{x}}}(x) is a bijection between XX and YY.

5.10

Same hypothesis as exercise 5.9, without assuming that the two families contain disjoint sets. We define fif_{i} the same way, using AC. Then we have a bijection between iIXi\prod_{{i\in I}}X_{i} and iIYi\prod_{{i\in I}}Y_{i} given by (xi)iI(fi(xi))iI{(x_{i})}_{{i\in I}}\mapsto{(f_{i}(x_{i}))}_{{i\in I}}.

5.11

0<n<ωn=sup0<n<ωn0=00=20\prod_{{0<n<\omega}}n={\sup_{{0<n<\omega}}n}^{{\aleph_{0}}}={\aleph_{0}}^{{% \aleph_{0}}}=2^{{\aleph_{0}}}

5.12

n<ωn=supn<ωn0=ω0\prod_{{n<\omega}}\aleph_{n}={\sup_{{n<\omega}}\aleph_{n}}^{{\aleph_{0}}}={% \aleph_{\omega}}^{{\aleph_{0}}}

5.13

α<ω+ωα=supα<ω+ωα|ω+ω|=ω+ω0\prod_{{\alpha<\omega+\omega}}\aleph_{\alpha}={\sup_{{\alpha<\omega+\omega}}% \aleph_{\alpha}}^{{|\omega+\omega|}}={\aleph_{{\omega+\omega}}}^{{\aleph_{0}}}

5.14

Suppose GCH holds, then:

  1. (1)

    2<κ=supμ<κ2μ=supμ<κμ+=κ2^{{<\kappa}}=\sup_{{\mu<\kappa}}2^{\mu}=\sup_{{\mu<\kappa}}\mu^{+}=\kappa

  2. (2)

    If κ\kappa is regular, κμ=κ\kappa^{\mu}=\kappa for all μ<κ\mu<\kappa, so κ<κ=supμ<κκμ=supμ<κκ=κ\kappa^{{<\kappa}}=\sup_{{\mu<\kappa}}\kappa^{\mu}=\sup_{{\mu<\kappa}}\kappa=\kappa.

5.15

Let β\beta be such that for every α,2α=α+β\alpha,2^{{\aleph_{\alpha}}}=\aleph_{{\alpha+\beta}} and suppose that βω\beta\geq\omega.

We have 0+β=β0+\beta=\beta and β+β>β\beta+\beta>\beta so we can define α\alpha to be the least α\alpha such that α+β>β\alpha+\beta>\beta and moreover 0<αβ0<\alpha\leq\beta.

If α=α+1\alpha=\alpha^{{\prime}}+1, let δ\delta be such that β=ω+δ\beta=\omega+\delta. We have α+β=α+1+ω+δ=α+ω+δ=α+β<β\alpha+\beta=\alpha^{{\prime}}+1+\omega+\delta=\alpha^{{\prime}}+\omega+\delta% =\alpha^{{\prime}}+\beta<\beta. A contradiction.

Hence α\alpha is limit and κ=α+α\kappa=\aleph_{{\alpha+\alpha}} is a limit cardinal. We have cf(κ)=cf(α)αα<α+α=κ\operatorname{cf}(\kappa)=\operatorname{cf}(\alpha)\leq\alpha\leq\aleph_{{% \alpha}}<\aleph_{{\alpha+\alpha}}=\kappa. Thus κ\kappa is singular.

Now, for all ξ<α\xi<\alpha, we have ξ+β=β\xi+\beta=\beta and

2α+ξ=α+ξ+β=α+β2^{{\aleph_{{\alpha+\xi}}}}=\aleph_{{\alpha+\xi+\beta}}=\aleph_{{\alpha+\beta}}

an by corollary 5.17,

2κ=2α+α=α+β<α+(α+β)=2α+α=2κ2^{\kappa}=2^{{\aleph_{{\alpha+\alpha}}}}=\aleph_{{\alpha+\beta}}<\aleph_{{% \alpha+(\alpha+\beta)}}=2^{{\aleph_{{\alpha+\alpha}}}}=2^{\kappa}

As a consequence, β<ω\beta<\omega.

5.16

ω1+ω1\displaystyle\aleph_{{\omega_{1}+\omega}}^{{\aleph_{1}}} (n=0+ω1+n)1\displaystyle\leq{\left(\prod_{{n=0}}^{{+\infty}}\aleph_{{\omega_{1}+n}}\right% )}^{{\aleph_{1}}}
=n=0+ω1+n1\displaystyle=\prod_{{n=0}}^{{+\infty}}\aleph_{{\omega_{1}+n}}^{{\aleph_{1}}}

But by repeated application of the Hausdorff formula, we have ω1+n1=ω11i=1nω1+i=ω11ω1+n\aleph_{{\omega_{1}+n}}^{{\aleph_{1}}}=\aleph_{{\omega_{1}}}^{{\aleph_{1}}}{% \prod_{{i=1}}^{{n}}\aleph_{{\omega_{1}+i}}}=\aleph_{{\omega_{1}}}^{{\aleph_{1}% }}\aleph_{{\omega_{1}+n}}, so

n=0+ω1+n1\displaystyle\prod_{{n=0}}^{{+\infty}}\aleph_{{\omega_{1}+n}}^{{\aleph_{1}}} =ω110n=0+ω1+n\displaystyle=\aleph_{{\omega_{1}}}^{{\aleph_{1}\aleph_{0}}}{\prod_{{n=0}}^{{+% \infty}}\aleph_{{\omega_{1}+n}}}
=ω11n=0+ω1+n\displaystyle=\aleph_{{\omega_{1}}}^{{\aleph_{1}}}{\prod_{{n=0}}^{{+\infty}}% \aleph_{{\omega_{1}+n}}}
=(supα<ω1α)1n=0+ω1+n\displaystyle={\left({\sup_{{\alpha<\omega_{1}}}\aleph_{\alpha}}\right)}^{{% \aleph_{1}}}{\prod_{{n=0}}^{{+\infty}}\aleph_{{\omega_{1}+n}}}
=α<ω1αn=0+ω1+n\displaystyle={\prod_{{\alpha<\omega_{1}}}\aleph_{{\alpha}}}{\prod_{{n=0}}^{{+% \infty}}\aleph_{{\omega_{1}+n}}}
=α<ω1+ωα\displaystyle={\prod_{{\alpha<\omega_{1}+\omega}}\aleph_{{\alpha}}}

Moreover, we have

α<ω1+ωα\displaystyle\prod_{{\alpha<\omega_{1}+\omega}}\aleph_{{\alpha}} α<ω1+ωω1+ω\displaystyle\leq\prod_{{\alpha<\omega_{1}+\omega}}\aleph_{{\omega_{1}+\omega}}
ω1+ω1\displaystyle\leq\aleph_{{\omega_{1}+\omega}}^{{\aleph_{1}}}

and finally

α<ω1+ωα=ω1+ω1\prod_{{\alpha<\omega_{1}+\omega}}\aleph_{{\alpha}}=\aleph_{{\omega_{1}+\omega% }}^{{\aleph_{1}}}

5.17

Let κ\kappa be a limit cardinal and 1λ<cfκ1\leq\lambda<\operatorname{cf}\kappa. Then every function κλ\kappa^{\lambda} is bounded and so κλ=α<καλ\kappa^{\lambda}=\bigcup_{{\alpha<\kappa}}\alpha^{\lambda}. Hence we have

κλ\displaystyle\kappa^{\lambda} =|α<καλ|\displaystyle=\left|\bigcup_{{\alpha<\kappa}}\alpha^{\lambda}\right|
κsupα<κ|α|λ\displaystyle\leq\kappa\sup_{{\alpha<\kappa}}{|\alpha|}^{\lambda}
=α<κ|α|λ\displaystyle=\sum_{{\alpha<\kappa}}{|\alpha|}^{\lambda}
α<κκλ\displaystyle\leq\sum_{{\alpha<\kappa}}\kappa^{\lambda}
=κκλ\displaystyle=\kappa\kappa^{\lambda}
=κλ\displaystyle=\kappa^{\lambda}

5.18

Obviously, ω1\aleph_{\omega}^{{\aleph_{1}}} is at least ω021\aleph_{\omega}^{{\aleph_{0}}}2^{{\aleph_{1}}}. Let’s prove the equality.

By theorem 5.20, it is either n0{\aleph_{n}}^{{\aleph_{0}}} for some n<ωn<\omega or (since cf(ω)=01\operatorname{cf}(\aleph_{\omega})=\aleph_{0}\leq\aleph_{1}) it is ω0\aleph_{\omega}^{{\aleph_{0}}}. In the latter case, using Hausdorff formula we get n0=112n21ω0{\aleph_{n}}^{{\aleph_{0}}}=\aleph_{1}^{{\aleph_{1}}}{\aleph_{2}...\aleph_{n}}% \leq 2^{{\aleph_{1}}}\aleph_{\omega}^{{\aleph_{0}}}.

5.19

As in 5.18, one inequality is clear. We show the other direction by induction on α<ω1\alpha<\omega_{1}. For α=0,1\alpha=0,1, we have α1=21\aleph_{\alpha}^{{\aleph_{1}}}=2^{{\aleph_{1}}}. If the equality is true below some 1<α<ω11<\alpha<\omega_{1} then α1\aleph_{\alpha}^{{\aleph_{1}}} can only take the values β1\aleph_{\beta}^{{\aleph_{1}}} (β<α\beta<\alpha), α\aleph_{\alpha} or αcfα\aleph_{\alpha}^{{\operatorname{cf}{\aleph_{\alpha}}}} (theorem 5.20). The first is not more than the expect result, by induction hypothesis. The second is less than the third, which is itself at most α0\aleph_{\alpha}^{{\aleph_{0}}} because cfα=cfαα<ω1\operatorname{cf}{\aleph_{\alpha}}=\operatorname{cf}{\alpha}\leq\alpha<\omega_% {1}. Finally α1=21α0\aleph_{\alpha}^{{\aleph_{1}}}=2^{{\aleph_{1}}}\aleph_{\alpha}^{{\aleph_{0}}}

5.20

We proceed as in 5.19: one equality is clear and we show the result by induction on α<ω2\alpha<\omega_{2}. For α=0,1,2\alpha=0,1,2, we have α2=22\aleph_{\alpha}^{{\aleph_{2}}}=2^{{\aleph_{2}}}. If the equality is true below some 2<α<ω12<\alpha<\omega_{1} then α1\aleph_{\alpha}^{{\aleph_{1}}} can only take the values β2\aleph_{\beta}^{{\aleph_{2}}} (β<α\beta<\alpha), α\aleph_{\alpha} or αcfα\aleph_{\alpha}^{{\operatorname{cf}{\aleph_{\alpha}}}} (theorem 5.20). The first is not more than the expect result, by induction hypothesis. The second is less than the third, which is itself at most α1\aleph_{\alpha}^{{\aleph_{1}}} because cfα=cfαα<ω2\operatorname{cf}{\aleph_{\alpha}}=\operatorname{cf}{\alpha}\leq\alpha<\omega_% {2}. Finally α2=22α1\aleph_{\alpha}^{{\aleph_{2}}}=2^{{\aleph_{2}}}\aleph_{\alpha}^{{\aleph_{1}}}

5.21

Let κ\kappa a regular limit cardinal. Clearly, 2<κκ<κ2^{{<\kappa}}\leq\kappa^{{<\kappa}}. For the other direction, we not that by theorem 5.20 and because κ\kappa is regular, for all μ\mu infinite κμ\kappa^{\mu} is either λμ\lambda^{\mu} (for some λ<κ\lambda<\kappa) or κ\kappa. But μ<κ,2<κ2μ=μμ\forall\mu<\kappa,2^{{<\kappa}}\geq 2^{\mu}=\mu^{\mu} and a fortiori μ,λ<κ,2<κλμ\forall\mu,\lambda<\kappa,2^{{<\kappa}}\geq\lambda^{\mu} (consider the maxium of λ\lambda and μ\mu and use the previous inequality). Moreover, 2<κsupμ<κ2μsupμ<κμ+κ2^{{<\kappa}}\geq\sup_{{\mu<\kappa}}2^{\mu}\geq\sup_{{\mu<\kappa}}\mu^{{+}}\geq\kappa. Thus 2<κκ<κ2^{{<\kappa}}\geq\kappa^{{<\kappa}} and finally Thus 2<κ=κ<κ2^{{<\kappa}}=\kappa^{{<\kappa}}.

If moreover κ\kappa is strong limit, then again theorem 5.20 shows that κ<μ=κ\kappa^{{<\mu}}=\kappa for μ<κ\mu<\kappa and so 2<κ=κ<κ=κ2^{{<\kappa}}=\kappa^{{<\kappa}}=\kappa

5.22

Let κ\kappa singular but not strong limit. Now, for all μ<κ\mu<\kappa, κμ\kappa^{\mu} can take the values λμ\lambda^{\mu} (for some λ<κ\lambda<\kappa), κ\kappa or κcf(κ)\kappa^{{\operatorname{cf}(\kappa)}}. We have already seen that 2<κλμ2^{{<\kappa}}\geq\lambda^{\mu} and we have κ<κcf(κ)\kappa<\kappa^{{\operatorname{cf}(\kappa)}}. Since κ\kappa is not strong limit, we can find μ,λ<κ\mu,\lambda<\kappa such that λμ>κ\lambda^{\mu}>\kappa and thus 2<κλμcf(κ)>κcf(κ)2^{{<\kappa}}\geq\lambda^{{\mu\operatorname{cf}(\kappa)}}>\kappa^{{% \operatorname{cf}(\kappa)}}. So finally 2<κ=κ<κκcf(κ)>κ2^{{<\kappa}}=\kappa^{{<\kappa}}\geq\kappa^{{\operatorname{cf}(\kappa)}}>\kappa

5.23

Let κ\kappa is strong limit and singular. Now, for all μ<κ\mu<\kappa, κμ\kappa^{\mu} can take the values κ\kappa or κcf(κ)\kappa^{{\operatorname{cf}(\kappa)}}. In particular κ<κ=κcf(κ)\kappa^{{<\kappa}}=\kappa^{{\operatorname{cf}(\kappa)}}.

Moreover 2<κ=supμ<κ2μsupμ<κκ=κ2^{{<\kappa}}=\sup_{{\mu<\kappa}}2^{\mu}\leq\sup_{{\mu<\kappa}}\kappa=\kappa and 2<κsupμ<κ2μsupμ<κμ+κ2^{{<\kappa}}\geq\sup_{{\mu<\kappa}}2^{\mu}\geq\sup_{{\mu<\kappa}}\mu^{{+}}\geq\kappa. Hence 2<κ=κ2^{{<\kappa}}=\kappa.

5.24

Suppose that 20ω2^{{\aleph_{0}}}\geq\aleph_{\omega} then ω020(20)0ω0\aleph_{\omega}^{{\aleph_{0}}}\geq 2^{{\aleph_{0}}}\geq{(2^{{\aleph_{0}}})}^{{% \aleph_{0}}}\geq\aleph_{\omega}^{{\aleph_{0}}}

5.25

Suppose 21=22^{{\aleph_{1}}}=\aleph_{2} and ω0>ω1\aleph_{\omega}^{{\aleph_{0}}}>\aleph_{{\omega_{1}}}. Then ω0ω1221\aleph_{\omega}^{{\aleph_{0}}}\geq\aleph_{{\omega_{1}}}\geq\aleph_{2}\geq 2^{{% \aleph_{1}}} so by exercise 5.18 we have ω0=ω1\aleph_{\omega}^{{\aleph_{0}}}=\aleph_{\omega}^{{\aleph_{1}}}. Finally, ω0=ω1=ω10ω11\aleph_{\omega}^{{\aleph_{0}}}=\aleph_{\omega}^{{\aleph_{1}}}=\aleph_{\omega}^% {{\aleph_{1}\aleph_{0}}}\geq\aleph_{{\omega_{1}}}^{{\aleph_{1}}}. The other sense is obvious so ω0=ω11\aleph_{\omega}^{{\aleph_{0}}}=\aleph_{{\omega_{1}}}^{{\aleph_{1}}}.

5.26

If 20ω12^{{\aleph_{0}}}\geq\aleph_{{\omega_{1}}} then (ω)=ω020200ω10ω0\operatorname{\gimel}(\aleph_{\omega})=\aleph_{\omega}^{{\aleph_{0}}}\geq 2^{{% \aleph_{0}}}\geq 2^{{\aleph_{0}\aleph_{0}}}\geq\aleph_{{\omega_{1}}}^{{\aleph_% {0}}}\geq\aleph_{{\omega}}^{{\aleph_{0}}} and (ω1)=ω1120121ω11\operatorname{\gimel}(\aleph_{{\omega_{1}}})=\aleph_{{\omega_{1}}}^{{\aleph_{1% }}}\leq{2^{{\aleph_{0}}}}^{{\aleph_{1}}}\leq 2^{{\aleph_{1}}}\leq\aleph_{{% \omega_{1}}}^{{\aleph_{1}}}.

5.27

Suppose 21=22^{{\aleph_{1}}}=\aleph_{2}. If we have ω0=ω1{\aleph_{\omega}}^{{\aleph_{0}}}=\aleph_{{\omega_{1}}} then by exercise 5.18 ω1=ω021=ω12=ω1{\aleph_{\omega}}^{{\aleph_{1}}}=\aleph_{\omega}^{{\aleph_{0}}}2^{{\aleph_{1}}% }=\aleph_{{\omega_{1}}}\aleph_{2}=\aleph_{{\omega_{1}}}. This is not possible since cf(ω1)=1<cf(ω1)\operatorname{cf}(\aleph_{{\omega_{1}}})=\aleph_{1}<\operatorname{cf}({\aleph_% {\omega}}^{{\aleph_{1}}}).

5.28

With the hypothesis of the exercise, (κ)=κcf(κ)(λ)cf(κ)λcf(λ)cf(κ)λcf(λ)(λ)\operatorname{\gimel}(\kappa)=\kappa^{{\operatorname{cf}(\kappa)}}\leq{% \operatorname{\gimel}(\lambda)}^{{\operatorname{cf}(\kappa)}}\leq\lambda^{{% \operatorname{cf}(\lambda)\operatorname{cf}(\kappa)}}\leq\lambda^{{% \operatorname{cf}(\lambda)}}\leq\operatorname{\gimel}(\lambda).

5.29

Let κ\kappa be a singular cardinal such that 2cf(κ)<κ2^{{\operatorname{cf}(\kappa)}}<\kappa. Suppose there exists some λ<κ\lambda<\kappa such that κλcf(κ)\kappa\leq\lambda^{{\operatorname{cf}(\kappa)}}. Let’s consider the smallest such λ\lambda. Clearly, we have (λ)(κ)\operatorname{\gimel}(\lambda)\leq\operatorname{\gimel}(\kappa). Moreover κcf(κ)λcf(κ)cf(κ)=λcf(κ)κcf(κ)\kappa^{{\operatorname{cf}(\kappa)}}\leq\lambda^{{\operatorname{cf}(\kappa)% \operatorname{cf}(\kappa)}}=\lambda^{{\operatorname{cf}(\kappa)}}\leq\kappa^{{% \operatorname{cf}(\kappa)}} so (κ)=λcf(κ)\operatorname{\gimel}(\kappa)=\lambda^{{\operatorname{cf}(\kappa)}}.

If cf(κ)cf(λ)\operatorname{cf}(\kappa)\leq\operatorname{cf}(\lambda), then κ<(κ)=λcf(κ)λcf(λ)\kappa<\operatorname{\gimel}(\kappa)=\lambda^{{\operatorname{cf}(\kappa)}}\leq% \lambda^{{\operatorname{cf}(\lambda)}} and we can apply exercise 5.28: (κ)(λ)\operatorname{\gimel}(\kappa)\leq\operatorname{\gimel}(\lambda) and so (κ)=(λ)\operatorname{\gimel}(\kappa)=\operatorname{\gimel}(\lambda). Suppose instead that cf(κ)>cf(λ)\operatorname{cf}(\kappa)>\operatorname{cf}(\lambda) and let’s use Theorem 5.20 to compute (κ)=λcf(κ)\operatorname{\gimel}(\kappa)=\lambda^{{\operatorname{cf}(\kappa)}}. First, λcf(κ)\lambda\leq\operatorname{cf}(\kappa) is impossible for otherwise 2λ2cf(κ)<κλcf(κ)2^{\lambda}\leq 2^{{\operatorname{cf}(\kappa)}}<\kappa\leq\lambda^{{% \operatorname{cf}(\kappa)}} by assumption while Theorem 5.20 implies that λcf(κ)=2λ\lambda^{{\operatorname{cf}(\kappa)}}=2^{\lambda}. Next, the existence of some μ<κ\mu<\kappa such that μcf(κ)=λcf(κ)\mu^{{\operatorname{cf}(\kappa)}}=\lambda^{{\operatorname{cf}(\kappa)}} would contradict the minimality of λ\lambda. Finally, because cf(λ)cf(κ)\operatorname{cf}(\lambda)\leq\operatorname{cf}(\kappa) Theorem 5.20 implies that (κ)=λcf(κ)=λcf(λ)=(λ)\operatorname{\gimel}(\kappa)=\lambda^{{\operatorname{cf}(\kappa)}}=\lambda^{{% \operatorname{cf}(\lambda)}}=\operatorname{\gimel}(\lambda).

This page is W3C-compliant - Author: Frédéric WANG
Valid XHTML 1.1 Valid MathML 2.0 Valid SVG Valid CSS