Set theory - Chapter 3: Cardinal Numbers

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

1. ((i))

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

2. ((ii))

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

3. ((iii))

   Let $S$ be finite and $f:S\rightarrow n$ 1-1 onto. Let $g:\operatorname{\mathcal{P}}(S)\rightarrow 2^{n}$ given by $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 $f$ is one-to-one, we see that $g$ is also one-to-one. Hence $S$ is finite.

4. ((iv))

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

1. ((i))

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

2. ((ii))

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

3. ((iii))

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

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

1. ((i))

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

2. ((ii))

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

For $n<\omega$, $\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 $(\alpha+1)\times(\alpha+1)$ given by the canonical ordering is:

1. (1)

   First, the initial segment $\alpha\times\alpha$ given by $(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, $\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 $\alpha mapsto\omega^{\alpha}$ are continuous then $\Gamma(\lambda\times\lambda)\leq\omega^{\lambda}$.

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

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

Now, define the function $\Gamma^{{<\omega}}:\mathrm{Ord}^{{<\omega}}\rightarrow\mathrm{Ord}$ by assigning to $\Gamma^{{<\omega}}(t)$ the order-type of the initial segment given by $t$. Clearly, if $s<t$ then $s$ is in the initial segment given by $t$ and so $\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=\operatorname{ran}\Gamma^{{<\omega}}$ is a proper class, so for any $\lambda\in\mathrm{Ord}$, $C\nsubseteq\lambda$ and so there is $t\in\mathrm{Ord}^{{<\omega}}$ such that $\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 $t$) we have $\lambda\in\operatorname{ran}\Gamma^{{<\omega}}$. Finally, we get an isomorphism $\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 $\alpha\in\mathrm{Ord}$.

Let’s prove by induction that for any ordinal $\alpha$, we have $\gamma(\omega_{\alpha})=\omega_{\alpha}$. For $\alpha=0$, we have $|\omega^{{<\omega}}|=\aleph_{0}$ according to exercise 3.4 and in particular $\gamma(\omega_{\alpha})\geq\omega$. But if $(a_{1},a_{2},...,a_{n})\in\omega^{{<\omega}}$ then the initial segment given by $(a_{1},a_{2},...,a_{n})$ is finite and so $\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\in\omega_{\alpha}^{{<\omega}}$ such that $\Gamma^{{<\omega}}(t)=\omega_{\alpha}$. In particular $t\neq 0$ and we can pick $\delta<\omega_{\alpha}$ such that $\delta>\max(\operatorname{ran}t)$. $\delta^{{<\omega}}$ is an initial segment containing $t$ 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 $\alpha\in\mathrm{Ord}$, $\left|\omega_{\alpha}^{{<\omega}}\right|=\omega_{\alpha}$.

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

Let $X={[\omega_{\alpha}]}^{{<\omega}}$ and $Y=\bigcup_{{n<\omega}}\omega_{\alpha}^{n}$. The onto mapping $f:Y\rightarrow X$ such that $(x_{1},x_{2},...,x_{n})\mapsto\{x_{1},x_{2},...,x_{n}\}$ shows that $X$ is a projection of $Y$. But

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

Let $B$ be a projection of $A$ and $f:A\rightarrow B$ onto. Let $g:\operatorname{\mathcal{P}}(B)\rightarrow\operatorname{\mathcal{P}}(A)$, $X\mapsto f^{{-1}}(X)$. Suppose that $g(X_{1})=g(X_{2})$ then for all $x\in X_{1}$ there is $y\in f^{{-1}}(X_{1})=f^{{-1}}(X_{2})$ such that $f(y)=x$. Hence $x\in X_{1}$ and $X_{1}\subseteq X_{2}$. By symmetry, $X_{1}=X_{2}$ and so $g$ is 1-1. Thus $|\operatorname{\mathcal{P}}(B)|\leq|\operatorname{\mathcal{P}}(A)|$.

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

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

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

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

Let $\aleph_{\alpha}$ an uncountable limit cardinal. Then $\alpha\geq 1$ is limit. Let $\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 $\xi<\operatorname{cf}(\alpha)$ such that $\alpha_{\xi}>\beta$. Then $\aleph_{{\alpha_{\xi}}}>\aleph_{\beta}=\kappa$. So we have $\sup_{{\xi<\alpha_{\xi}}}\aleph_{{\alpha_{\xi}}}=\aleph_{{\alpha}}$ By Lemma 3.7(ii) the sequence $\left\langle\alpha_{{\alpha_{\xi}}}:\xi<\operatorname{cf}(\alpha)\right\rangle$ shows that $\operatorname{cf}(\operatorname{cf}(\alpha))=\operatorname{cf}(\aleph_{\alpha})$. Finally $\operatorname{cf}(\operatorname{cf}(\alpha))=\operatorname{cf}(\omega_{\alpha})$.

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

Let $S$ be $D$-infinite and $f:S\rightarrow X\subsetneq S$ a 1-1 onto map. Let $x_{0}\in S\setminus X$ and define for all $n<\omega,x_{{n+1}}=f(x_{n})$. $x_{0}\notin X$ while for every $n>0,x_{n}\in X$. Hence $x_{0}$ is distinct from all $x_{n},n>0$. We show by induction on $n$ that for all $0<m<n$, $x_{m}\neq x_{n}$. This is true for $n=1$ by the previous remark. Suppose it is true for some $n\geq 1$. Then for all $0<m<n+1$, $x_{m}\neq x_{{n+1}}$ or otherwise $x_{{m-1}}=x_{n}$ (since $f$ is 1-1) which contradicts either the induction hypothesis or the inital remark on $x_{0}$. Hence $n\mapsto x_{n}$ is 1-1 and $S$ contains the countable subset $X=\{x_{n}:n<\omega\}$.

Conversely, if $X=\{x_{n}:n<\omega\}$ is a countable subset of $S$. Let $f:S\rightarrow S\setminus\{x_{0}\}$ where $f(x)=x$ if $x\not inX$ and $\forall n,f(x_{n})=x_{{n+1}}$. $f$ shows that S is $D$-infinite.

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

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

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

   2. (b)

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

2. ((ii))

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

3. ((iii))

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

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