Exercise 7.2.4

Proof. Suppose that $A$ and $B$ are disjoint sets where $\left|A\right|=\left|\alpha \right|$ and $\left|B\right|=\left|\beta \right|$ so that, by the definition of cardinal addition, $\left|\alpha \right|+\left|\beta \right|=\left|A\cup B\right|$. We then show the result by constructing a bijection $f$ from $A\cup B$ to the ordinal $\alpha +\beta$. First, since $\left|A\right|=\left|\alpha \right|$, there is a bijective $f_A:A\to \alpha$. Similarly there is a bijective $f_B:B\to \beta$ since $\left|B\right|=\left|\beta \right|$. Now consider any $x\in A\cup B$. We then set

noting that this is unambiguous since $A$ and $B$ are disjoint. If $x\in A$ then we clearly have $f(x)=f_A(x)<\alpha =\alpha +0\le \alpha +\beta$ by Lemma 6.5.4 so that $f(x)\in \alpha +\beta$. On the other hand if $x\in B$ then $f(x)=\alpha +f_B(x)<\alpha +\beta$ again by Lemma 6.5.4 since $f_B(x)<\beta$, and hence again $f(x)\in \alpha +\beta$. This shows that $f$ really is a function into $\alpha +\beta$.

Next we show that $f$ is injective. So consider any $x$ and $y$ in $A\cup B$ where $x\ne y$.

Case: $x$ and $y$ are both in $A$. Then $f(x)=f_A(x)\ne f_A(y)=f(y)$ since $f_A$ is injective and $x\ne y$.

Case: $x\in A$ and $y\in B$. Then $f(x)=f_A(x)<\alpha =\alpha +0\le \alpha +f_B(y)=f(y)$ by Lemma 6.5.4 so that clearly $f(x)\ne f(y)$.

Case: $x\in B$ and $y\in A$. This is analogous to the previous case.

Case: $x$ and $y$ are both in $A$. Then $f(x)=\alpha +f_B(x)\ne \alpha +f_B(y)=f(y)$ by Lemma 6.5.4b since $f_B$ is injective and $x\ne y$ so that $f_B(x)\ne f_B(y)$.

Hence in all cases we have $f(x)\ne f(y)$, which shows that $f$ is injective.

Lastly, we show that $f$ is surjective. So consider any $y$ in $\alpha +\beta$. If $y<\alpha$ then $y\in \alpha$. Since $f_A$ is surjective there is an $x\in A$ such that $f_A(x)=y$. Then, since $x\in A$, clearly $f(x)=f_A(x)=y$. If $y\ge a$ then by Lemma 6.5.5 there is an ordinal $\xi$ such that $\alpha +\xi =y$. It then follows that $\alpha +\xi =y<\alpha +\beta$ so that $\xi <\beta$ by Lemma 6.5.4a. Hence $\xi \in \beta$ so that there is an $x\in B$ such that $f_B(x)=\xi$ since $f_B$ is surjective. Then, since $x\in B$, clearly we have $f(x)=\alpha +f_B(x)=\alpha +\xi =y$. Hence in both cases there is an $x\in A\cup B$ where $f(x)=y$. Since $y$ was arbitrary, this shows that $f$ is surjective.

Thus we have shown that $f$ is bijective so that $\left|\alpha \right|+\left|\beta \right|=\left|A\cup B\right|=\left|\alpha +\beta \right|$. □

Proof. First, if $\alpha =0$ then

The result also holds when $\beta =0$. Hence going forward we can assume that $\alpha$ and $\beta$ are nonzero and therefore nonempty.

We then show the result by constructing a bijective $f:\alpha \times \beta \to \alpha \cdot \beta$. So consider any $(\gamma ,\delta )\in \alpha \times \beta$. It then follows that $\gamma <\alpha$ and $\delta <\beta$ so that $\delta +1\le \beta$. We then set $f(\gamma ,\delta )=\alpha \cdot \delta +\gamma$. We note that

by Lemma 6.5.4, Exercise 6.5.2, and Exercise 6.5.7. Hence $f(\gamma ,\delta )\in \alpha \cdot \beta$ so that $f$ is into $\alpha \cdot \beta$.

Now we show that $f$ is injective. So consider any $({\gamma }_1,{\delta }_1)$ and $({\gamma }_2,{\delta }_2)$ in $\alpha \times \beta$ where $({\gamma }_1,{\delta }_1)\ne ({\gamma }_2,{\delta }_2)$. Then clearly we have ${\gamma }_1<\alpha$, ${\gamma }_2<\alpha$, ${\delta }_1<\beta$, and ${\delta }_2<\beta$. We then have

Case: ${\delta }_1={\delta }_2$. Then it must be that ${\gamma }_1\ne {\gamma }_2$. We then have

where we have used Lemma 6.5.4b and Exercise 6.5.7b since $\alpha \ne 0$.

Case: ${\delta }_1\ne {\delta }_2$. Without loss of generality we can assume that ${\delta }_1<{\delta }_2$ so that clearly ${\delta }_1+1\le {\delta }_2$. Then we have

where we have again used Lemma 6.5.4a, Exercise 6.5.2, and Exercise 6.5.7.

Hence in all cases we have $f({\gamma }_1,{\delta }_1)\ne f({\gamma }_2,{\delta }_2)$, which shows that $f$ is injective.

Lastly, we show that $f$ is surjective. So consider any ordinal $\xi \in \alpha \cdot \beta$ so that $\xi <\alpha \cdot \beta$. Since $\alpha \ne 0$, it follows from Theorem 6.6.3 that there is a unique $\delta$ and unique $\gamma <\alpha$ such that $\xi =\alpha \cdot \delta +\gamma$. Note that we have $\delta <\beta$ since otherwise $\delta \ge \beta$ would imply that

by Lemma 6.5.4 and Exercise 6.5.7, which is impossible since $\xi <\alpha \cdot \beta$. Hence we have that $(\gamma ,\delta )\in \alpha \times \beta$, and clearly $f(\gamma ,\delta )=\xi$. Since $\xi$ was arbitrary this shows that $f$ is surjective.

Thus we have shown that $f$ is bijective so that by the definition of cardinal multiplication we have $\left|\alpha \cdot \beta \right|=\left|\alpha \times \beta \right|=\left|\alpha \right|\cdot \left|\beta \right|$ as desired. □

Proof. We define a function $f:\alpha \times \beta \to {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\gamma <\alpha }{A}_{\gamma }$ by simply setting $f(\gamma ,\delta )=a_{\gamma }(\delta )$ for any $\gamma \in \alpha$ and $\delta \in \beta$. We show that $f$ is onto by considering any $x\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\gamma <\alpha }{A}_{\gamma }$ so that there is an $\gamma <\alpha$ such that $x\in A_{\gamma }$. Then, since $A_{\gamma }$ is the range of $a_{\gamma }$, there is a $\delta <\beta$ such that $a_{\gamma }(\delta )=x$. Hence $f(\gamma ,\delta )=a_{\gamma }(\delta )=x$ so that $f$ is onto since $x$ was arbitrary.

We also have that $\alpha \times \beta$ is well-orderable by Theorem 6.5.8 (for example the lexicographic ordering has order type $\beta \cdot \alpha$). It then follows from Lemma ?? that $\left|{\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\gamma <\alpha }{A}_{\gamma }\right|\le \left|\alpha \times b\right|=\left|\alpha \right|\cdot \left|\beta \right|$ since $f$ is onto. Hence ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{\gamma <\alpha }{A}_{\gamma }$ is at most $\left|\alpha \right|\cdot \left|\beta \right|$ as desired. □

Proof. Let $f$ be a bijection from ${\omega }_{\gamma }$ to $A$. We also know from Theorem 7.2.1 that $\left|{\omega }_{\gamma }\times {\omega }_{\gamma }\right|={\aleph }_{\gamma }\cdot {\aleph }_{\gamma }={\aleph }_{\gamma }$, so let $g$ be a bijection from ${\omega }_{\gamma }$ to ${\omega }_{\gamma }\times {\omega }_{\gamma }$. For each $n<{\omega }_0=\omega$ (i.e. $n\in 𝑵$) we define a transfinite enumeration $⟨a_n(\alpha )\mid \alpha <{\omega }_{\gamma }⟩$ of $A^n$, where $A^n$ of course denotes the set of all sequences of elements of $A$ of length $n$. We define these enumerations recursively. Clearly for $n=0$ we have $A^n=A^0=\left\{\text{∅}\right\}$ so that we can set

Then, having defined $a_n$, for any $\alpha <{\omega }_{\gamma }$, we let $g(\alpha )=({\alpha }_1,{\alpha }_2)$ and define the sequence $a_{n+1}(\alpha )$ of length $n$ as follows:

for any $k<n+1$.

Clearly each $a_n(\alpha )$ is a sequence of length $n$ for any $n<{\omega }_0$ and $\alpha <{\omega }_{\gamma }$, but we must show that $a_n$ is in fact an enumeration by showing that it is onto $A^n$ for all $n<{\omega }_0$. We show this by induction on $n$. Obviously this is true for the trivial $n=0$ case and for the $n=1$ case as well since, for any sequence $⟨a⟩$ of length 1 where $a\in A$, we have that there is a an $\alpha <{\omega }_{\gamma }$ such that $f(\alpha )=a$ since $f$ is onto. Hence by definition $a_1(\alpha )=⟨f(\alpha )⟩=⟨a⟩$ so that $a_1$ is onto.

Now suppose that $a_n$ is onto $A^n$ and consider any sequence $h\in A^{n+1}$. Now, since $h\upharpoonright n$ is a sequence of length $n$ there is an ${\alpha }_1<{\omega }_{\gamma }$ such that $a_n({\alpha }_1)=h\upharpoonright n$ by the induction hypothesis. We also have $h(n)\in A$ so that there is an ${\alpha }_2<{\omega }_{\gamma }$ such that $f({\alpha }_2)=h(n)$ since again $f$ is onto. Now, clearly $({\alpha }_1,{\alpha }_2)\in {\omega }_{\gamma }\times {\omega }_{\gamma }$ so that there is an $\alpha <{\omega }_{\gamma }$ such that $g(\alpha )=({\alpha }_1,{\alpha }_2)$ since $g$ is onto. Now consider any $k<n+1$. If $k<n$ then clearly we have $a_{n+1}(\alpha )(k)=a_n({\alpha }_1)(k)=h(k)$ since $a_n({\alpha }_1)=h\upharpoonright n$. On the other hand, if $k=n$, then by definition $a_{n+1}(\alpha )(k)=f({\alpha }_2)=h(n)=h(k)$. Thus $a_{n+1}(\alpha )=h$ since $k$ was arbitrary and the cases are exhaustive. This shows that $a_{n+1}$ is onto since $h$ was arbitrary, hence it is an enumeration.

Clearly we have that $\mathrm{Seq}(A)={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n<{\omega }_0}{A}^n$ and, since we also have an transfinite enumeration (indexed by ${\omega }_{\gamma }$) of each $A^n$ it follows from Lemma 3 that

where we have utilized Corollary 7.2.2 since $0\le \gamma$. Also clearly ${\aleph }_{\gamma }\le \left|\mathrm{Seq}(A)\right|$ since, for example, the function $f:{\omega }_{\gamma }\to \mathrm{Seq}(A)$ defined by $f(\alpha )=⟨\alpha ⟩$ (for any $\alpha <{\omega }_{\gamma }$) is injective. Thus by the Cantor-Bernstein Theorem we have $\left|\mathrm{Seq}(A)\right|={\aleph }_{\gamma }$ as desired. □

Proof. First we note that clearly the set $B\cup \omega$ is countable (since $B$ is finite and $\omega$ is countable) so that $\mathrm{Seq}(A\cup \omega )$ is also countable by Lemma 4. Now let $f$ be a function from $\mathrm{Seq}(A)$ to $\mathrm{Seq}(A\cup \omega )$ defined by the identity $f(g)=g$ for any sequence $g\in \mathrm{Seq}(A)$. Note that $A\subseteq A\cup \omega$ so that any sequence of elements of $A$ is a also a sequence with elements in $A\cup \omega$. Clearly $f$ is injective so that $\left|\mathrm{Seq}(A)\right|\le \left|\mathrm{Seq}(A\cup \omega )\right|={\aleph }_0$.

Since $A$ is nonempty there is an $a\in A$. For any $n<\omega$ consider the finite sequence $g_n(k)=a$ for any $k<n$, which is clearly a sequence of length $n$ with elements in $A$. Consider then the function $f$ from $\omega$ to $\mathrm{Seq}(A)$ defined $f(n)=g_n$ for $n<\omega$. Clearly this is a injective function since, for any $n_1$ and $n_2$ in $\omega$ where $n_1\ne n_2$, we have that $f(n_1)=g_{n_1}$ and $f(n_2)=g_{n_2}$ are sequences of different lengths so cannot be equal. Thus we have ${\aleph }_0=\left|\omega \right|\le \left|\mathrm{Seq}(a)\right|$ as well so that $\left|\mathrm{Seq}(A)\right|={\aleph }_0$ by the Cantor-Bernstein Theorem. □

Proof. First let ${\left[{\aleph }_{\alpha }\right]}^{<\omega }$ again denote the set of finite subsets of ${\aleph }_{\alpha }$. Since $\left|A\right|={\aleph }_{\alpha }$ there is a bijective $f:A\to {\aleph }_{\alpha }$. We then define $g:{\left[A\right]}^{<\omega }\to {\left[{\aleph }_{\alpha }\right]}^{<\omega }$ by letting $g(B)=f[B]$ for any $B\in {\left[A\right]}^{<\omega }$, noting that clearly $g(B)\subseteq {\aleph }_{\alpha }$ and $g(B)$ is finite so that $g(B)\in {\left[{\aleph }_{\alpha }\right]}^{<\omega }$. We now show that $g$ is bijective.

First consider any $B_1$ and $B_2$ in ${\left[A\right]}^{<\omega }$ where $g(B_1)=g(B_2)$. Hence $f[B_1]=g(B_1)=g(B_2)=f[B_2]$. So consider any $x\in B_1$ so that $f(x)\in f[B_1]$. Then also $f(x)\in f[B_2]$ so that there is a $y\in B_2$ such that $f(y)=f(x)$. But since $f$ is injective it has to be that $y=x$ so that $x=y\in B_2$. Hence $B_1\subseteq B_2$ since $x$ was arbitrary. A similar argument shows that $B_2\subseteq B_1$ as well so that $B_1=B_2$. This shows that $g$ is injective.

Now consider any $C\in {\left[{\aleph }_{\alpha }\right]}^{<\omega }$ and let $B=f^{-1}[C]$, noting that $f^{-1}$ is a bijective function since $f$ is. We claim then that $g(B)=C$. So consider any $y\in g(B)=f[B]$ so that there is a $x\in B$ such that $f(x)=y$. Then we have $x\in f^{-1}[C]$ by the definition of $B$ so that there is a $z\in C$ such that $f^{-1}(z)=x$. Hence $z=f(f^{-1}(z))=f(x)=y$ so that $y=z\in C$. Thus $g(B)\subseteq C$ since $y$ was arbitrary. Now consider any $y\in C$ so that clearly $x=f^{-1}(y)\in f^{-1}[C]=B$ and also $f(x)=y$. Hence clearly $y=f(x)\in f[B]=g(B)$ so that $C\subseteq g(B)$ since $y$ was arbitrary. This shows that $g(B)=C$ so that $g$ is surjective since $C$ was arbitrary.

We have just shown that $g$ is bijective so that $\left|{\left[A\right]}^{<\omega }\right|=\left|{\left[{\aleph }_{\alpha }\right]}^{<\omega }\right|={\aleph }_{\alpha }$ by Exercise 7.2.3c. □

Proof. To show this we reference the representation of ordinal exponentiation discussed in Exercise 6.5.16. In that exercise we showed that the set $S(\beta ,\alpha )=\left\{f\mid f:\beta \to \alpha \text{ and }s(f)\text{ is finite}\right\}$, where $s(f)=\left\{\xi <\beta \mid f(\xi )\ne 0\right\}$ for any $f:\beta \to \alpha$, can be ordered to be isomorphic to ${\alpha }^{\beta }$. From this it clearly follows that $\left|S(\beta ,\alpha )\right|=\left|{\alpha }^{\beta }\right|$.

We now construct an injective function $f$ from $S(\beta ,\alpha )$ to ${\left[\beta \right]}^{<\omega }\times \mathrm{Seq}(\alpha )$, where ${\left[\beta \right]}^{<\omega }$ is the set of all finite subsets of $\beta$ and $\mathrm{Seq}(\alpha )$ is the set of all finite sequences of elements of $\alpha$. So consider any $g\in S(\beta ,\alpha )$ so that $g:\beta \to \alpha$ and $s(g)$ is a finite subset of $\beta$. Also clearly $s(g)$ is a finite set of ordinals so that there is a unique isomorphism $h$ from some natural number $n$ to $s(g)$. Clearly then $g\circ h$ is a finite sequence from $n$ to $\alpha$. Thus we have that $s(g)\in {\left[\beta \right]}^{<\omega }$ and $g\circ h\in \mathrm{Seq}(\alpha )$, so we set $f(g)=(s(g),g\circ h)$.

To see that this mapping is injective consider $g_1$ and $g_2$ in $S(\beta ,\alpha )$ where $g_1\ne g_2$. Then there is some $\xi <\beta$ where $g_1(\xi )\ne g_2(\xi )$. Let $h_1$ and $h_2$ be the isomorphisms from natural numbers $n_1$ and $n_2$ to $s(g_1)$ and $s(g_2)$, respectively, as described above. If $s(g_1)\ne s(g_2)$ then clearly $f(g_1)=(s(g_1),g_1\circ h_1)\ne (s(g_2),g_2\circ h_2)=f(g_2)$. So assume that $s(g_1)=s(g_2)$, from which it follows that $n_1=n_2$ and $h_1=h_2$. Since $h_1=h_2$ are bijections there is a $k\in n_1=n_2$ such that $h_1(k)=h_2(k)=\xi$, noting that it has to be that $\xi \in s(g_1)=s(g_2)$ since otherwise we would have $g_1(\xi )=0=g_2(\xi )$. We then have $(g_1\circ h_1)(k)=g_1(h_1(k))=g_1(\xi )\ne g_2(\xi )=g_2(h_2(k))=(g_2\circ h_2)(k)$ so that $g_1\circ h_1\ne g_2\circ h_2$. Thus once again $f(g_1)=(s(g_1),g_1\circ h_1)\ne (s(g_2),g_2\circ h_2)=f(g_2)$, which shows that $f$ is injective.

So since $f$ is injective it follows that $\left|{\alpha }^{\beta }\right|=\left|S(\beta ,\alpha )\right|\le \left|{\left[\beta \right]}^{<\omega }\times \mathrm{Seq}(\alpha )\right|=\left|{\left[\beta \right]}^{<\omega }\right|\cdot \left|\mathrm{Seq}(\alpha )\right|$. Suppose first that $\left|\alpha \right|\le \left|\beta \right|$ so it has to be that $\beta$ is infinite so that $\max <!--\; FUNCTION\; APPLICATION\; -->\left(\left|\alpha \right|,\left|\beta \right|\right)=\left|\beta \right|={\aleph }_{\gamma }$ for some ordinal $\gamma$. Thus by Lemma 6 we have $\left|{\left[\beta \right]}^{<\omega }\right|={\aleph }_{\gamma }$. If $\alpha =0=\varnothing$ then clearly $\mathrm{Seq}(\alpha )=\left\{\text{∅}\right\}$ so that $\left|\mathrm{Seq}(\alpha )\right|=1$. If $\alpha$ is finite but nonzero then it is nonempty so that $\left|\mathrm{Seq}(\alpha )\right|={\aleph }_0$ by Corollary 5. Lastly, if $\alpha$ is infinite then $\left|\alpha \right|={\aleph }_{\delta }$ for some $\delta \le \gamma$ since ${\aleph }_{\delta }=\left|\alpha \right|\le \left|\beta \right|={\aleph }_{\gamma }$. Hence $\left|\mathrm{Seq}(\alpha )\right|={\aleph }_{\gamma }$ by Lemma 4. Thus in all three cases $\kappa =\left|\mathrm{Seq}(\alpha )\right|$ is either a natural number or ${\aleph }_{\delta }$ for some $\delta \le \gamma$. It then follows from Corollary 7.2.2 that

On the other hand if $\left|\beta \right|\le \left|\alpha \right|$ then it must be that $\alpha$ is infinite so that $\max <!--\; FUNCTION\; APPLICATION\; -->\left(\left|\alpha \right|,\left|\beta \right|\right)=\left|\alpha \right|={\aleph }_{\gamma }$ for some ordinal $\gamma$. Thus by Lemma 4 we have $\left|\mathrm{Seq}(\alpha )\right|={\aleph }_{\gamma }$ as well. If $\beta$ is finite then clearly every subset of $\beta$ is finite so that ${\left[\beta \right]}^{<\omega }=𝒫\left(\beta \right)$ is finite by Theorem 4.2.8. Hence $\left|{\left[\beta \right]}^{<\omega }\right|=n$ for some natural number $n$. If $\beta$ is infinite then $\left|\beta \right|={\aleph }_{\delta }$ for some $\delta \le \gamma$ since ${\aleph }_{\delta }=\left|\beta \right|\le \left|\alpha \right|={\aleph }_{\gamma }$. We then have that $\left|{\left[\beta \right]}^{<\omega }\right|={\aleph }_{\delta }$ as well by Lemma 6. Hence in either case $\kappa =\left|{\left[\beta \right]}^{<\omega }\right|$ is a natural number or ${\aleph }_{\delta }$ for some $\delta \le \gamma$. Hence we have

again by Corollary 7.2.2. Thus in all cases we have shown that $\left|{\alpha }^{\beta }\right|\le \max <!--\; FUNCTION\; APPLICATION\; -->\left(\left|\alpha \right|,\left|\beta \right|\right)$ as desired. □

Proof. That $\left|\alpha +\beta \right|\le {\aleph }_{\gamma }$ follows almost immediately from Lemma 1. We have that $\left|\alpha +\beta \right|=\left|\alpha \right|+\left|\beta \right|\le {\aleph }_{\gamma }+{\aleph }_{\gamma }={\aleph }_{\gamma }$, where we have also used property (c) of cardinal numbers after Lemma 5.1.2, and Corollary 7.2.3.

Similarly, $\left|\alpha \cdot \beta \right|\le {\aleph }_{\gamma }$ follows from Lemma 2. We have that $\left|\alpha \cdot \beta \right|=\left|\alpha \right|\cdot \left|\beta \right|\le {\aleph }_{\gamma }\cdot {\aleph }_{\gamma }={\aleph }_{\gamma }$, where we have used property (i) of cardinal numbers following Lemma 5.1.4, and Theorem 7.2.1.

The analogous lemma for ordinal exponentiation (i.e. that $\left|{\alpha }^{\beta }\right|={\left|\alpha \right|}^{\left|\beta \right|}$ for ordinals $\alpha$ and $\beta$) is evidently not true. As a counterexample consider $\alpha =2$ and $\beta =\omega$. We then have that $\left|{\alpha }^{\beta }\right|=\left|2^{\omega }\right|=\left|\omega \right|={\aleph }_0$ is countable whereas we know that ${\left|\alpha \right|}^{\left|\beta \right|}={\left|2\right|}^{\left|\omega \right|}=2^{{\aleph }_0}$ is uncountable.

However, the somewhat analogous Lemma 7 will help us show the desired result. First, if both $\alpha$ and $\beta$ are finite then clearly ${\alpha }^{\beta }$ is also finite so that clearly $\left|{\alpha }^{\beta }\right|\le {\aleph }_{\gamma }$. On the other hand, if at least one of $\alpha$ or $\beta$ is infinite, then have we have that $\left|{\alpha }^{\beta }\right|\le \max <!--\; FUNCTION\; APPLICATION\; -->\left(\left|\alpha \right|,\left|\beta \right|\right)\le {\aleph }_{\gamma }$ by Lemma 7 as desired, noting that clearly $\max <!--\; FUNCTION\; APPLICATION\; -->\left(\left|\alpha \right|,\left|\beta \right|\right)\le {\aleph }_{\gamma }$ since both $\left|\alpha \right|\le {\aleph }_{\gamma }$ and $\left|\beta \right|\le {\aleph }_{\gamma }$. □