Exercise 7.2.3

Proof. For any ordinal $\alpha$, we show this by induction on $n$, noting that we only need to show this for positive $n$ so that $n\ge 1$ (in fact it is untrue for $n=0$). First, for $n=1$ we clearly have ${\aleph }_{\alpha }^n={\aleph }_{\alpha }^1={\aleph }_{\alpha }$ by what was shown in Exercise 5.1.2. Now assume that ${\aleph }_{\alpha }^n={\aleph }_{\alpha }$. We then have

This completes the induction step. □

Proof. For ordinal $\alpha$ and natural number $n$, first we show that $\left|n\right|\le {\aleph }_{\alpha }$ by constructing an injective $f:n\to {\omega }_{\alpha }^n$. For a set $X\in n$ we have that $\left|X\right|=n$. Thus there is a bijective $g$ from $n$ to $X$, and since clearly $X\subseteq {\aleph }_{\alpha }={\omega }_{\alpha }$ it follows that $g$ is a function from $n$ to ${\omega }_{\alpha }$. Hence we simply set $f(X)=g$. Now consider any $X_1$ and $X_2$ in $n$ where $X_1\ne X_2$. Then let $g_1$ and $g_2$ be the corresponding bijections from $n$ to $X_1$ and $X_2$, respectively. Thus $f(X_1)=g_1$ and $f(X_2)=g_2$. Then, since clearly the range of $g_1$ is $X_1$, the range of $g_2$ is $X_2$, and $X_1\ne X_2$ it follows that $f(X_1)=g_1\ne g_2=f(X_2)$, which shows that $f$ is injective. Hence it follows that $\left|n\right|\le \left|{\omega }_{\alpha }^n\right|={\left|{\omega }_{\alpha }\right|}^{\left|n\right|}={\aleph }_{\alpha }^n={\aleph }_{\alpha }$ by what was shown in part (a).

Now we show that also ${\aleph }_{\alpha }\le \left|n\right|$ by constructing an injective $f:{\omega }_{\alpha }\to n$. So for any $\beta \in {\omega }_{\alpha }$ let $X=\left\{\beta +k\mid k\in n\right\}$, noting that clearly $X\subseteq {\omega }_{\alpha }={\aleph }_{\alpha }$ since ${\omega }_{\alpha }$ is a limit ordinal (since then $\beta +k\in {\omega }_{\alpha }$ for any natural number $k$). Also clearly $\left|X\right|=n$ so that $X\in n$. We then set $f(\beta )=X$. Now consider any ${\beta }_1$ and ${\beta }_2$ in ${\omega }_{\alpha }$ where ${\beta }_1\ne {\beta }_2$ and let $X_1=\left\{{\beta }_1+k\mid k\in n\right\}$ and $X_2=\left\{{\beta }_2+k\mid k\in n\right\}$ so that $f({\beta }_1)=X_1$ and $f({\beta }_2)=X_2$. Since ${\beta }_1\ne {\beta }_2$ we can assume that ${\beta }_1<{\beta }_2$ without loss of generality. Now, clearly ${\beta }_1={\beta }_1+0$ is the least element of $X_1$ and ${\beta }_2={\beta }_2+0$ the least element of $X_2$. Since ${\beta }_1<{\beta }_2$ it then follows that ${\beta }_1\notin X_2$, but since ${\beta }_1\in X_1$ this clearly implies that $f({\beta }_1)=X_1\ne X_2=f({\beta }_2)$. This shows that $f$ is injective so that ${\aleph }_{\alpha }=\left|{\omega }_{\alpha }\right|\le \left|n\right|$.

Since we have shown that both $\left|n\right|\le {\aleph }_{\alpha }$ and ${\aleph }_{\alpha }\le \left|n\right|$, it follows from the Cantor-Bernstein Theorem that $\left|n\right|={\aleph }_{\alpha }$, which is what we intended to show. □

Proof. For any ordinal $\alpha$ we show first note that clearly $={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n<\omega }n$. We show that $\left|\right|={\aleph }_{\alpha }$ by constructing a bijective $f:\omega \times {\omega }_{\alpha }\to {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n<\omega }n$. So consider any $n\in \omega$ and $\beta \in {\omega }_{\alpha }$. Now, by what was shown in part (b), we have $\left|n\right|={\aleph }_{\alpha }=\left|{\omega }_{\alpha }\right|$ so that there is a bijective $g_n:{\omega }_{\alpha }\to n$, i.e. $g_n$ is a transfinite enumeration of $n$. We then set $f(n,\beta )=g_n(\beta )$, from which it should be clear that $f(n,\beta )\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{k<\omega }k$ since $f(n,\beta )=g_n(\beta )\in n$.

First we show that $f$ is injective. To this end consider any $(n_1,{\beta }_1)$ and $(n_2,{\beta }_2)$ in $\omega \times {\omega }_{\alpha }$ where $(n_1,{\beta }_1)\ne (n_2,{\beta }_2)$. Then either $n_1\ne n_2$ or ${\beta }_1\ne {\beta }_2$ (or both). Let $g_{n_1}$ and $g_{n_2}$ be the corresponding bijections from ${\omega }_{\alpha }$ to $n_1$ and $n_2$, respectively, as described above. Clearly if $n_1\ne n_2$ then $f(n_1,{\beta }_1)=g_{n_1}({\beta }_1)\in n_1$ whereas $f(n_2,{\beta }_2)=g_{n_2}({\beta }_2)\in n_2$ so that $f(n_1,{\beta }_1)\ne f(n_2,{\beta }_2)$ since $n_1$ and $n_2$ are clearly disjoint (since $n_1$ contains only sets with $n_1$ elements and $n_2$ contains only sets with $n_2$ elements and $n_1\ne n_2$). On the other hand, if $n_1=n_2$ then it must be the case that ${\beta }_1\ne {\beta }_2$. It also follows that $g_{n_1}=g_{n_2}$ since $n_1=n_2$. Hence we have $f(n_1,{\beta }_1)=g_{n_1}({\beta }_1)\ne g_{n_1}({\beta }_2)=g_{n_2}({\beta }_2)=f(n_2,{\beta }_2)$ since $g_{n_1}=g_{n_2}$ is injective and ${\beta }_1\ne {\beta }_2$. Thus in any case $f(n_1,{\beta }_1)\ne f(n_2,{\beta }_2)$ so that $f$ is injective.

Next we show that $f$ is surjective. So consider any $X\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n<\omega }n$ so that there is an $n<\omega$ such that $X\in n$. Then let $\beta =g_n^{-1}(X)$ (where $g_n$ is the bijection from ${\omega }_{\alpha }$ to $n$ as described above). Then clearly $(n,\beta )\in \omega \times {\omega }_{\alpha }$ and we have $f(n,\beta )=g_n(\beta )=g_n(g_n^{-1}(X))=X$. Since $X$ was arbitrary this shows that $f$ is surjective.

Hence $f$ is a bijection so that $\left|\right|=\left|{\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n<\omega }n\right|=\left|\omega \times {\omega }_{\alpha }\right|=\left|\omega \right|\cdot \left|{\omega }_{\alpha }\right|={\aleph }_0\cdot {\aleph }_{\alpha }={\aleph }_{\alpha }$ by Corollary 7.2.2 since clearly $0\le \alpha$. This shows the desired result. □