Set theory - Chapter 3: Cardinal Numbers


First, we note that the ordering Ord\leq_{{\mathrm{Ord}}} is the same as Card\leq_{{\mathrm{Card}}} for natural numbers. Let n,mn,m be two natural numbers. We can suppose nOrdmn\leq_{{\mathrm{Ord}}}m. Then nmn\subseteq m and the identity is 1-1 from nn to mm, i.e. nCardmn\leq_{{\mathrm{Card}}}m.

  1. ((i))

    Let XX be a finite set of cardinality nn and f:Xnf:X\rightarrow n 1-1 onto. Let YXY\subseteq X. The identity of YY is 1-1 so we have |Y||X|=n|Y|\leq|X|=n. Let pp be the least natural number such that |Y|p|Y|\leq p. We shall show that |Y|=p|Y|=p. If p=0p=0, then Y=Y=\emptyset and we are done. Otherwise, we can write p=q+1p=q+1 and suppose there exists a 1-1 gg from YY to pp that is not surjective. We can suppose qran(g)q\notin\operatorname{ran}(g). Then g|Y:Yqg_{{|Y}}:Y\rightarrow q is 1-1 and |Y|q<p|Y|\leq q<p. A contradiction. Finally YY is finite.

  2. ((ii))

    Let S=i<pSiS=\bigcup_{{i<p}}S_{i} and fi:Sinif_{i}:S_{i}\rightarrow n_{i} 1-1 onto. Let f:Si<pnif:S\rightarrow\sum_{{i<p}}n_{i} given by x(j<kinj+fi(x))x\mapsto\left(\sum_{{j<k_{i}}}n_{j}+f_{i}(x)\right) where for each kik_{i} is the least natural number such that xSkix\in S_{{k_{i}}}. Clearly, ff is well-defined and 1-1 so |S|i<pni|S|\leq\sum_{{i<p}}n_{i}. As in (i), we conclude that SS is finite.

  3. ((iii))

    Let SS be finite and f:Snf:S\rightarrow n 1-1 onto. Let g:𝒫(S)2ng:\operatorname{\mathcal{P}}(S)\rightarrow 2^{n} given by XxX2f(x)X\mapsto\sum_{{x\in X}}2^{{f(x)}}. By unicity of the binary decomposition of a natural (easy to show by induction) and because ff is one-to-one, we see that gg is also one-to-one. Hence SS is finite.

  4. ((iv))

    Let SS be finite and f:Snf:S\rightarrow n 1-1 onto and consider a mapping F:STF:S\rightarrow T. Then g:F(S)ng:F(S)\rightarrow n given by xmin{i<ω:F(f-1(i))=x}x\mapsto\min\left\{i<\omega:F(f^{{-1}}(i))=x\right\} is 1-1 so F(S)F(S) is finite.


  1. ((i))

    Let an:n<0\left\langle a_{n}:n<\aleph_{0}\right\rangle be an enumeration of SS (i.e. f:nanf:n\mapsto a_{n} is 1-1 onto from \mathbb{N} to SS) and XSX\subseteq S . If XX is finite, then we are done. Define by induction for each n<ω,xn=apn<\omega,x_{n}=a_{p} where pp is the least natural such that ap{xi:i<ni}a_{p}\notin\{x_{i}:i<n_{i}\} and apXa_{p}\in X. Such an apa_{p} always exists for otherwise X{xi:i<ni}X\subseteq\{x_{i}:i<n_{i}\} would be finite by 3.1 (i). Then nxnn\mapsto x_{n} is 1-1 from 0\aleph_{0} to XX and xf-1(x)x\mapsto f^{{-1}}(x) is 1-1 from XX to 0\aleph_{0}. By Cantor-Berstein, XX is countable.

  2. ((ii))

    Let S=i<nSiS=\bigcup_{{i<n}}S_{i} with fi:Si0f_{i}:S_{i}\rightarrow\aleph_{0} 1-1 onto. We suppose n1n\geq 1 for otherwise S=S=\emptyset. Then f0-1f_{0}^{{-1}} is 1-1 from 0\aleph_{0} to SS. Define g:S0g:S\rightarrow\aleph_{0} by x2i3fi(x)x\mapsto 2^{i}3^{{f_{i}(x)}} where i<ni<n is the least element such that xSix\notin S_{i}. By Cantor-Bernstein, |S|=0|S|=\aleph_{0}.

  3. ((iii))

    Let f:S0f:S\rightarrow\aleph_{0} 1-1 and F:SF(S)F:S\rightarrow F(S). Define g:F(S)0g:F(S)\rightarrow\aleph_{0} where xg(x)x\mapsto g(x) is the least ii such that F(f-1(i))=xF(f^{{-1}}(i))=x. Then gg is 1-1. By (i), g(F(S))0g(F(S))\subseteq\aleph_{0} is at most countable. So F(S)F(S) too.


Let f:×f:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N} defined by (n,m)2m(2n+1)-1(n,m)\mapsto 2^{m}(2n+1)-1. Let xx\in\mathbb{N} and pp be the greatest natural such that 2p2^{p} divides x+1x+1. Then x+12p\frac{x+1}{2^{p}} is odd and can be written 2q+12q+1 for some natural qq. Thus x=f(q,p)x=f(q,p) and ff is onto. If f(n1,m1)=f(n2,m2)f(n_{1},m_{1})=f(n_{2},m_{2}) then 2n1(2m1+1)=2n2(2m2+1)2^{{n_{1}}}(2m_{1}+1)=2^{{n_{2}}}(2m_{2}+1). Hence the 22-adic order of this number is n1=n2n_{1}=n_{2} and consequently m1=m2m_{1}=m_{2}. Therefore ff is also onto. Finally ×\mathbb{N}\times\mathbb{N} is countable.


  1. ((i))

    Let g:ai:i<n2ni<npiai-1g:\left\langle a_{i}:i<n\right\rangle\mapsto 2^{n}\prod_{{i<n}}p_{i}^{{a_{i}}}-1 where pip_{i} is the ii-th prime number. Then gg is 1-1 onto.

  2. ((ii))

    Let S={ai:i<n}S=\{a_{i}:i<n\} a countable set. Let g:X2ni<npiχX(ai)-1g:X\mapsto 2^{n}\prod_{{i<n}}p_{i}^{{\chi_{X}(a_{i})}}-1 where χX\chi_{X} is the characteristic function of XX. Then gg is 1-1 onto.


For n<ωn<\omega, Γ(n×n)<ωωn\Gamma(n\times n)<\omega\leq\omega^{n}. Γ(ω×ω)=ωωω\Gamma(\omega\times\omega)=\omega\leq\omega^{\omega}. Let αω\alpha\geq\omega such that Γ(α×α)ωα\Gamma(\alpha\times\alpha)\leq\omega^{\alpha}. Then the order type of (α+1)×(α+1)(\alpha+1)\times(\alpha+1) given by the canonical ordering is:

  1. (1)

    First, the initial segment α×α\alpha\times\alpha given by (0,α)(0,\alpha)

  2. (2)

    The elements (ξ,α)(\xi,\alpha) for ξ<α\xi<\alpha

  3. (3)

    The elements (α,ξ)(\alpha,\xi) for ξ<α\xi<\alpha

  4. (4)

    and finally (α,α)(\alpha,\alpha).

Consequently, Γ((α+1)×(α+1))=Γ(α×α)+α2+1=ωα+ωα3ωα4ωα+1\Gamma((\alpha+1)\times(\alpha+1))=\Gamma(\alpha\times\alpha)+\alpha 2+1=% \omega^{\alpha}+\omega^{\alpha}3\leq\omega^{\alpha}4\leq\omega^{{\alpha+1}}

If λ>ω\lambda>\omega is a limit ordinal such that Γ(α×α)ωα\Gamma(\alpha\times\alpha)\leq\omega^{\alpha} for all α<λ\alpha<\lambda then since αΓ(α×α)\alpha\mapsto\Gamma(\alpha\times\alpha) and αmapstoωα\alpha mapsto\omega^{\alpha} are continuous then Γ(λ×λ)ωλ\Gamma(\lambda\times\lambda)\leq\omega^{\lambda}.


For any n1n\leq 1, if we note Γn-1=ΓΓΓntimes\Gamma^{{n-1}}=\underset{n\,\text{times}}{\underbrace{\Gamma\circ\Gamma\circ..% .\Gamma}} then we have a well-ordering of Ordn\mathrm{Ord}^{n} given by the isomorphism Γn-1:OrdnOrd\Gamma^{{n-1}}:\mathrm{Ord}^{n}\cong\mathrm{Ord}. Now we define an ordering << on the set Ord<ω\mathrm{Ord}^{{<\omega}} of finite ordinal sequences as follows:

s<t\displaystyle s<t\iff (s=) or\displaystyle(s=\emptyset)\text{ or }
(s,tmax(ran(s))<max(ran(t))) or\displaystyle(s,t\neq\emptyset\wedge\max{(\operatorname{ran}(s))}<\max{(% \operatorname{ran}(t))})\text{ or }
(s,tmax(ran(s))=max(ran(t))lengths<lengtht) or\displaystyle(s,t\neq\emptyset\wedge\max{(\operatorname{ran}(s))}=\max{(% \operatorname{ran}(t))}\wedge\mathrm{length}{s}<\mathrm{length}{t})\text{ or }
(s,tmax(ran(s))=max(ran(t))lengths=lengthtΓlengths-1(s)<Γlengtht-1(t))\displaystyle(s,t\neq\emptyset\wedge\max{(\operatorname{ran}(s))}=\max{(% \operatorname{ran}(t))}\wedge\mathrm{length}{s}=\mathrm{length}{t}\wedge\Gamma% ^{{\mathrm{length}{s}-1}}(s)<\Gamma^{{\mathrm{length}{t}-1}}(t))

Clearly, << is a well-ordering. Moreover, for all αOrd\alpha\in\mathrm{Ord}, the only possibilities for s<(α)s<(\alpha) is that s=s=\emptyset and or ss\neq\emptyset and max(ran(s))<α\max{(ran(s))}<\alpha. So α<ω\alpha^{{<\omega}} is the initial segment given by (α)(\alpha).

Now, define the function Γ<ω:Ord<ωOrd\Gamma^{{<\omega}}:\mathrm{Ord}^{{<\omega}}\rightarrow\mathrm{Ord} by assigning to Γ<ω(t)\Gamma^{{<\omega}}(t) the order-type of the initial segment given by tt. Clearly, if s<ts<t then ss is in the initial segment given by tt and so Γ<ω(s)<Γ<ω(t)\Gamma^{{<\omega}}(s)<\Gamma^{{<\omega}}(t). Because << is total, this means that Γ<ω\Gamma^{{<\omega}} is one-to-one and moreover the converse implication is true. Because Γ<ω\Gamma^{{<\omega}} is one-to-one, C=ranΓ<ωC=\operatorname{ran}\Gamma^{{<\omega}} is a proper class, so for any λOrd\lambda\in\mathrm{Ord}, CλC\nsubseteq\lambda and so there is tOrd<ωt\in\mathrm{Ord}^{{<\omega}} such that Γ<ω(t)λ\Gamma^{{<\omega}}(t)\notin\lambda. This implies λΓ<ω\lambda\in\Gamma^{{<\omega}} and by Theorem 2.8 (applied to the restriction of Γ<ω\Gamma^{{<\omega}} to the initial segment of tt) we have λranΓ<ω\lambda\in\operatorname{ran}\Gamma^{{<\omega}}. Finally, we get an isomorphism Γ<ω:Ord<ωOrd\Gamma^{{<\omega}}:\mathrm{Ord}^{{<\omega}}\cong\mathrm{Ord}. Note that because γ(α)=Γ<ω((α))\gamma(\alpha)=\Gamma^{{<\omega}}((\alpha)) is an increasing function, we have γ(α)α\gamma(\alpha)\geq\alpha for all αOrd\alpha\in\mathrm{Ord}.

Let’s prove by induction that for any ordinal α\alpha, we have γ(ωα)=ωα\gamma(\omega_{\alpha})=\omega_{\alpha}. For α=0\alpha=0, we have |ω<ω|=0|\omega^{{<\omega}}|=\aleph_{0} according to exercise 3.4 and in particular γ(ωα)ω\gamma(\omega_{\alpha})\geq\omega. But if (a1,a2,,an)ω<ω(a_{1},a_{2},...,a_{n})\in\omega^{{<\omega}} then the initial segment given by (a1,a2,,an)(a_{1},a_{2},...,a_{n}) is finite and so Γ<ω((a1,a2,,an))<ω\Gamma^{{<\omega}}((a_{1},a_{2},...,a_{n}))<\omega. Necessarily, we have γ(ω)=ω\gamma(\omega)=\omega. Now suppose that the result is true below an ordinal α\alpha but that we have γ(ωα)>ωα\gamma(\omega_{\alpha})>\omega_{\alpha}. Let tωα<ωt\in\omega_{\alpha}^{{<\omega}} such that Γ<ω(t)=ωα\Gamma^{{<\omega}}(t)=\omega_{\alpha}. In particular t0t\neq 0 and we can pick δ<ωα\delta<\omega_{\alpha} such that δ>max(rant)\delta>\max(\operatorname{ran}t). δ<ω\delta^{{<\omega}} is an initial segment containing tt and so Γ<ω(δ<ω)ωα\Gamma^{{<\omega}}(\delta^{{<\omega}})\supseteq\omega_{\alpha} and |δ<ω|ωα\left|\delta^{{<\omega}}\right|\geq\omega_{\alpha}. But by induction hypothesis, |δ<ω|=||δ|<ω|=|γ(|δ|)|=|δ|<ωα\left|\delta^{{<\omega}}\right|=\left|{|\delta|}^{{<\omega}}\right|=\left|{% \gamma({|\delta|})}\right|={|\delta|}<\omega_{\alpha}. A contradiction.

Note: in particular we proved that for all αOrd\alpha\in\mathrm{Ord}, |ωα<ω|=ωα\left|\omega_{\alpha}^{{<\omega}}\right|=\omega_{\alpha}.


Let f:ωαBf:\omega_{\alpha}\mapsto B an onto mapping. Then g:Bωαg:B\rightarrow\omega_{\alpha} given by xmin(f-1(x))x\mapsto\min(f^{{-1}}(x)) is 1-1 and |B||ωα|=α|B|\leq|\omega_{\alpha}|=\aleph_{\alpha}.


Let X=[ωα]<ωX={[\omega_{\alpha}]}^{{<\omega}} and Y=n<ωωαnY=\bigcup_{{n<\omega}}\omega_{\alpha}^{n}. The onto mapping f:YXf:Y\rightarrow X such that (x1,x2,,xn){x1,x2,,xn}(x_{1},x_{2},...,x_{n})\mapsto\{x_{1},x_{2},...,x_{n}\} shows that XX is a projection of YY. But

|Y||n<ωωαn|=n<ω|ωαn|=n<ωα=α0=α|Y|\leq\left|\bigcup_{{n<\omega}}\omega_{\alpha}^{n}\right|=\sum_{{n<\omega}}|% \omega_{\alpha}^{n}|=\sum_{{n<\omega}}\aleph_{\alpha}=\aleph_{\alpha}\aleph_{0% }=\aleph_{\alpha}

Hence by 3.7, |X|α|X|\leq\aleph_{\alpha}. Now h:ωαXh:\omega_{\alpha}\rightarrow X given by h(x)={x}h(x)=\{x\} is 1-1 so |X|=α|X|=\aleph_{\alpha}.


Let BB be a projection of AA and f:ABf:A\rightarrow B onto. Let g:𝒫(B)𝒫(A)g:\operatorname{\mathcal{P}}(B)\rightarrow\operatorname{\mathcal{P}}(A), Xf-1(X)X\mapsto f^{{-1}}(X). Suppose that g(X1)=g(X2)g(X_{1})=g(X_{2}) then for all xX1x\in X_{1} there is yf-1(X1)=f-1(X2)y\in f^{{-1}}(X_{1})=f^{{-1}}(X_{2}) such that f(y)=xf(y)=x. Hence xX1x\in X_{1} and X1X2X_{1}\subseteq X_{2}. By symmetry, X1=X2X_{1}=X_{2} and so gg is 1-1. Thus |𝒫(B)||𝒫(A)||\operatorname{\mathcal{P}}(B)|\leq|\operatorname{\mathcal{P}}(A)|.


Let f:𝒫(ωα×ωα)ωα+1f:\operatorname{\mathcal{P}}(\omega_{\alpha}\times\omega_{\alpha})\rightarrow% \omega_{{\alpha+1}} such that for all Rωα×ωαR\in\omega_{\alpha}\times\omega_{\alpha}, f(R)f(R) is the order-type of RR if this one is a well-ordering of ωα\omega_{\alpha} and any xωα+1x\in\omega_{{\alpha+1}} otherwise. In the former case, f(R)=βf(R)=\beta for an ordinal β\beta such that |β||ωα|\beta|\leq|\omega_{\alpha}. Hence f(R)=β<ωα+1f(R)=\beta<\omega_{{\alpha+1}} and ff is well-defined.

Each βωα\beta\in\omega_{\alpha} is an ordinal and its well-ordering RR satisfies f(R)=βf(R)=\beta. If βωα+1\beta\in\omega_{{\alpha+1}} and βωα\beta\geq\omega_{\alpha} , then |β|=|ωα|\beta|=|\omega_{\alpha}. Let gg be a one-to-one mapping from ω\omega onto β\beta and define the relation \preceq on ωα\omega_{\alpha} by xyx\preceq y iff g(x)g(y)g(x)\in g(y). Then by construction we have f()=βf(\preceq)=\beta. Finally ff is onto.

Since |ωα×ωα|=α=ωα|\omega_{\alpha}\times\omega_{\alpha}|=\aleph_{\alpha}=\omega_{\alpha} we conclude that ωα+1\omega_{{\alpha+1}} is a projection of 𝒫(ωα)\operatorname{\mathcal{P}}(\omega_{\alpha}).


By Cantor’s theorem, |ωα+1|<|𝒫(ωα+1)||\omega_{{\alpha+1}}|<|\operatorname{\mathcal{P}}(\omega_{{\alpha+1}})|. Using exercises 3.10 and 3.9 we get |𝒫(ωα+1)||𝒫(𝒫(ωα+1))||\operatorname{\mathcal{P}}(\omega_{{\alpha+1}})|\leq|\operatorname{\mathcal{P% }}(\operatorname{\mathcal{P}}(\omega_{{\alpha+1}}))|. Finally, α+1<22α\aleph_{{\alpha+1}}<2^{{2^{{\aleph_{\alpha}}}}}.


Let α\aleph_{\alpha} an uncountable limit cardinal. Then α1\alpha\geq 1 is limit. Let αξ:ξ<cf(α)\left\langle\alpha_{\xi}:\xi<\operatorname{cf}(\alpha)\right\rangle a cofinal sequence in α\alpha. If κ<α\kappa<\aleph_{\alpha}, there is β<α\beta<\alpha such that κ=β\kappa=\aleph_{\beta}. Let ξ<cf(α)\xi<\operatorname{cf}(\alpha) such that αξ>β\alpha_{\xi}>\beta. Then αξ>β=κ\aleph_{{\alpha_{\xi}}}>\aleph_{\beta}=\kappa. So we have supξ<αξαξ=α\sup_{{\xi<\alpha_{\xi}}}\aleph_{{\alpha_{\xi}}}=\aleph_{{\alpha}} By Lemma 3.7(ii) the sequence ααξ:ξ<cf(α)\left\langle\alpha_{{\alpha_{\xi}}}:\xi<\operatorname{cf}(\alpha)\right\rangle shows that cf(cf(α))=cf(α)\operatorname{cf}(\operatorname{cf}(\alpha))=\operatorname{cf}(\aleph_{\alpha}). Finally cf(cf(α))=cf(ωα)\operatorname{cf}(\operatorname{cf}(\alpha))=\operatorname{cf}(\omega_{\alpha}).


Suppose that ω2=n<ωSn\omega_{2}=\bigcup_{{n<\omega}}S_{n} with |Sn|=0|S_{n}|=\aleph_{0} and let αn\alpha_{n} be the order-type of SnS_{n}. We may assume that the sets SnS_{n} are disjoint. Then n<ω,αn<ω1\forall n<\omega,\alpha_{n}<\omega_{1} and α=supαnω1\alpha=\sup\alpha_{n}\leq\omega_{1}. Define f:ω×αω2f:\omega\times\alpha\rightarrow\omega_{2} where f(n,ξ)f(n,\xi) is the ξ\xi-th element of SnS_{n} if ξ<αn\xi<\alpha_{n} and ω2\emptyset\in\omega_{2} otherwise. Then ff is onto and we can build a 1-1 map from ω2\omega_{2} to ω×α\omega\times\alpha (without AC since ω×α\omega\times\alpha is well-ordered). Consequently 2=|ω2||ω×α|01=1\aleph_{2}=|\omega_{2}|\leq|\omega\times\alpha|\leq\aleph_{0}\aleph_{1}=\aleph% _{1}. A contradiction.


Let SS be DD-infinite and f:SXSf:S\rightarrow X\subsetneq S a 1-1 onto map. Let x0SXx_{0}\in S\setminus X and define for all n<ω,xn+1=f(xn)n<\omega,x_{{n+1}}=f(x_{n}). x0Xx_{0}\notin X while for every n>0,xnXn>0,x_{n}\in X. Hence x0x_{0} is distinct from all xn,n>0x_{n},n>0. We show by induction on nn that for all 0<m<n0<m<n, xmxnx_{m}\neq x_{n}. This is true for n=1n=1 by the previous remark. Suppose it is true for some n1n\geq 1. Then for all 0<m<n+10<m<n+1, xmxn+1x_{m}\neq x_{{n+1}} or otherwise xm-1=xnx_{{m-1}}=x_{n} (since ff is 1-1) which contradicts either the induction hypothesis or the inital remark on x0x_{0}. Hence nxnn\mapsto x_{n} is 1-1 and SS contains the countable subset X={xn:n<ω}X=\{x_{n}:n<\omega\}.

Conversely, if X={xn:n<ω}X=\{x_{n}:n<\omega\} is a countable subset of SS. Let f:SS{x0}f:S\rightarrow S\setminus\{x_{0}\} where f(x)=xf(x)=x if xnXx\not inX and n,f(xn)=xn+1\forall n,f(x_{n})=x_{{n+1}}. ff shows that S is DD-infinite.


We use the equivalent definition of DD-finiteness obtained in exercise 3.14. For each proof we suppose that final set is DD-infinite and shows that one of the initial set is not DD-finite.

  1. ((i))
    1. (a)

      Suppose XABX\subseteq A\cup B is a countable set. We have X=(XA)(XB)X=(X\cap A)\cup(X\cap B) and so by exercise 3.1 (ii), one of (XA)(X\cap A) or (XB)(X\cap B) is not finite. Say XAX\cap A is infinite. By exercise 3.2 (i), XAX\cap A is at most countable and so XAX\cap A is a countable subset of AA.

    2. (b)

      Let {(an,bn):n<ω}=X\{(a_{n},b_{n}):n<\omega\}=X a countable subset of A×BA\times B. For all n0,αn=akn\geq 0,\alpha_{n}=a_{k} where kk is the least index such that ak{αi:i<n}a_{k}\notin\{\alpha_{i}:i<n\} (if such an index exists). The sequence βn\beta_{n} is defined similarly. At least one of these sequences is completly defined, otherwise let n,mn,m the least indices such that αn\alpha_{n} and βm\beta_{m} are not defined, then XX is a subset of the finite set {αi:i<n}×{βi:i<m}\{\alpha_{i}:i<n\}\times\{\beta_{i}:i<m\}. Suppose for instance that {αn:n<ω}\{\alpha_{n}:n<\omega\} is well defined, then it is a countable subset of AA.

  2. ((ii))

    Let AA be a set and {(uki)k<ni:i<ω}\{{(u_{k}^{i})}_{{k<n_{i}}}:i<\omega\} a countable set of 1-1 finite sequence of elements of AA. Let x0=u00x_{0}=u_{0}^{0} and for all n>0,xn=ukin>0,x_{n}=u_{k}^{i} where ii is the least index such that ranui\operatorname{ran}u^{i} is not included in {xj:j<n}\{x_{j}:j<n\} and kk the least index such that uki{xj:j<n}u_{k}^{i}\notin\{x_{j}:j<n\}. This sequence is well defined, otherwise if nn is the least index such that xnx_{n} can not be defined, then {uki:i<ω,k<ni}X={xj:j<n}\{u_{k}^{i}:i<\omega,k<n_{i}\}\subseteq X=\{x_{j}:j<n\} and (uki)k<ni:i<ω\left\langle{(u_{k}^{i})}_{{k<n_{i}}}:i<\omega\right\rangle is included in the finite (by exercise 3.4 i) set [X]<ω{[X]}^{{<\omega}}. Finally, {xn:n<ω}\{x_{n}:n<\omega\} is a countable subset of AA.

  3. ((iii))

    Let (Xi)iI{(X_{i})}_{{i\in I}} a disjoint family of DD-finite sets and suppose that their union is DD-infinite. Let X={xn:n<ω}X=\{x_{n}:n<\omega\} a countable subset of iIXi\bigcup_{{i\in I}}X_{i}. For each n<ωn<\omega let mm be the least natural such that xmk<nXikx_{m}\notin\bigcup_{{k<n}}X_{{i_{k}}}. Such an mm always exists for otherwise an Xk<nXikX\subseteq\bigcup_{{k<n}}X_{{i_{k}}} while this union is DD-finite by (i). Then, define ini_{n} the unique index such that xmXix_{m}\in X_{i}. Finally, we get a countable set {in:n<ω}I\{i_{n}:n<\omega\}\subseteq I.


Let AA be an infinite set and for all n<ω,Xn={XA:|X|=n}n<\omega,X_{n}=\{X\subseteq A:|X|=n\}. Each XnX_{n} is nonempty: AA is infinite so we can choose nn elements of AA to build an element of XnX_{n}. Moreover the XnX_{n} are clearly pairwise distinct. Hence {Xn:n<ω}\{X_{n}:n<\omega\} is a countable subset of 𝒫(𝒫(A))\operatorname{\mathcal{P}}(\operatorname{\mathcal{P}}(A)). Finally, 𝒫(𝒫(A))\operatorname{\mathcal{P}}(\operatorname{\mathcal{P}}(A)) is DD-infinite.

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