Exercise 7.1.2

Proof. First we define two sets:

We also define the order ${<}_1$ on $W_1$ so that $(0,\gamma ){<}_1(0,\delta )$ if and only if $\gamma <\delta$ for $(0,\gamma )$ and $(0,\delta )$ in $W_1$ (so that $\gamma$ and $\delta$ are in $\alpha$). Similarly we define the order ${<}_2$ on $W_2$ so that $(1,\gamma ){<}_2(1,\delta )$ if and only if $\gamma <\delta$ for $(1,\gamma )$ and $(1,\delta )$ in $W_2$ (so that $\gamma$ and $\delta$ are in $\beta$).

Clearly $W_1$ and $W_2$ are disjoint, $(W_1,{<}_1)$ is isomorphic to $\alpha$, and $(W_2,{<}_2)$ is isomorphic to $\beta$. It then follows from Theorem 6.5.3 that the sum $(W,<)$ is isomorphic to $\alpha +\beta$.

Now, since they are isomorphic, clearly $W_1$ is equipotent to $\alpha$ and therefore is at most countable. Similarly $W_2$ is at most countable by virtue of being isomorphic to $\beta$. It then follows from Theorem 4.2.6 and Theorem 4.3.5 that $W=W_1\cup W_2$ is at most countable. Then, since $(W,<)$ is isomorphic to $\alpha +\beta$, $W$ and $\alpha +\beta$ are equipotent so that $\alpha +\beta$ must be at most countable too. □

Proof. Since $\alpha$ and $\beta$ are at most countable it follows from Exercise 4.2.2 and Theorem 4.3.7 that $\alpha \times \beta$ is at most countable. Then, since $\alpha \cdot \beta$ is isomorphic to the antilexicographic ordering of $\alpha \times \beta$ by Theorem 6.5.8, it follows that $\alpha \cdot \beta$ is equipotent to $\alpha \times \beta$ and there for at most countable. □

Proof. First if we have that $\alpha =0$ then then either ${\alpha }^{\beta }=0^{\beta }=1$ (if $\beta =0$) or ${\alpha }^{\beta }=0^{\beta }=0$ (if $\beta >0$). Clearly both $0$ and $1$ are both at most countable so in the following we assume that $\alpha \ne 0$.

Now, let $\mathrm{Seq}(\alpha \cdot \beta )$ be the set of all finite sequences of elements of $\alpha \cdot \beta$, and $S(\beta ,\alpha )$ be the set as defined in Exercise 6.5.16 such that $S(\beta ,\alpha )$ with the order defined there is isomorphic (and therefore equipotent) to ${\alpha }^{\beta }$. We shall construct a function $g:S(\beta ,\alpha )\to \mathrm{Seq}(\alpha \cdot \beta )$.

So consider any $f\in S(\beta ,\alpha )$ so that $f:\beta \to \alpha$ and $s(f)=\left\{\xi <\beta \mid f(\xi )\ne 0\right\}$ (as defined in the exercise) is finite. Hence there is a natural number $n$ such that $s(f)$ can be expressed as an increasing sequence $h:n\to s(f)$. We now define another sequence $t:n\to \alpha \cdot \beta$ by

for $k\in n$. We then set $g(f)=t$.

The first thing we show is that $g(f)$ is really a sequence whose elements are in $\alpha \cdot \beta$ for any $f\in S(\beta ,\alpha )$. Hence for any such $f$ again let $h$ be the increasing finite sequence whose range is $s(f)$ and let $t=g(f)$. Then for any $k\in n$ we we note that $h(k)<\beta$ since $h(k)\in s(f)$ so that $h(k)+1\le \beta$. We also note that $f(h(k))\in \alpha$ since $f:\beta \to \alpha$ so that $f(h(k))<\alpha$. Thus we have by definition that

Hence $t(k)<\alpha \cdot \beta$ so that $t(k)\in \alpha \cdot \beta$. Thus $t:n\to \alpha \cdot \beta$ and since clearly this sequence is finite it follows that $t\in \mathrm{Seq}(\alpha \cdot \beta )$.

Now we show that $g$ is injective. So consider $f_1$ and $f_2$ in $S(\beta ,\alpha )$ such that $f_1\ne f_2$. Let $h_1$, $n_1$ and $h_2$, $n_2$ be the increasing sequences and natural numbers for $f_1$ and $f_2$, respectively, as defined above. Also let $t_1=g(f_1)$ and $t_2=g(f_2)$.

Case: $n_1\ne n_2$. In this case the sequences are different sizes so that clearly $t_1\ne t_2$ since $t_1$ and $t_2$ are sequences of sizes $n_1$ and $n_2$, respectively.

Case: $n_1=n_2$. Since $f_1\ne f_2$ there must be a $\gamma \in \beta$ such that $f_1(\gamma )\ne f_2(\gamma )$. Without loss of generality we can assume that $f_1(\gamma )<f_2(\gamma )$.

If $f_1(\gamma )=0$ then by definition $\gamma \notin s(f_1)$ but $\gamma \in s(f_2)$. Hence there is a $k\in n_2$ such that $h_2(k)=\gamma$. Also since $n_1=n_2$ clearly $k\in n_1$. However, it must be that $h_1(k)\ne \gamma =h_2(k)$ since otherwise it would be that $\gamma \in s(f_1)$. Suppose that $h_1(k)<h_2(k)$ so that $h_1(k)+1\le h_2(k)$ and we have

so that $t_1(k)\ne t_2(k)$ and therefore $t_1\ne t_2$. The case in which $h_1(k)>h_2(k)$ is analogous.

On the other hand if $f_1(\gamma )\ne 0$ then $0<f_1(\gamma )<f_2(\gamma )$ so that $\gamma \in s(f_1)$ and $\gamma \in s(f_2)$. Thus there are $k_1$ and $k_2$ in $n_1=n_2$ such that $h_1(k_1)=h_2(k_2)=\gamma$. If $k_1=k_2$ then we have

so that $t_1\ne t_2$. If $k_1<k_2$ then since $h_1$ is increasing we have $h_2(k_2)=h_1(k_1)<h_1(k_2)$ so that $h_2(k_2)+1\le h_1(k_2)$ and so

and $t_1\ne t_2$. The final sub-case in which $k_1>k_2$ is analogous.

Hence in all cases and sub-cases $g(f_1)=t_1\ne t_2=g(f_2)$, which shows that $g$ is injective. From this it follows from Definition 4.1.4 that $\left|S(\beta ,\alpha )\right|\le \left|\mathrm{Seq}(\alpha \cdot \beta )\right|$. However, from what was shown above it follows that $\alpha \cdot \beta$ is at most countable since $\alpha$ and $\beta$ are. Thus $\mathrm{Seq}(\alpha \cdot \beta )$ is also at most countable by Exercise 4.2.4 and Theorem 4.3.10 so that $S(\beta ,\alpha )$ must be at most countable since it was just shown that $\left|S(\beta ,\alpha )\right|\le \left|\mathrm{Seq}(\alpha \cdot \beta )\right|$. Lastly, since $S(\beta ,\alpha )$ is equipotent to ${\alpha }^{\beta }$ it follows that ${\alpha }^{\beta }$ is at most countable as well. □