Exercise 6.5.16

Proof. First we note that if $\beta =0=\varnothing$ then the only function from $\beta$ to $\alpha$ (it could even be here that $\alpha =0=\varnothing$) is the vacuous function $\text{∅}$. Hence $S(\beta ,\alpha )=\left\{\text{∅}\right\}$, which is clearly vacuously isomorphic to (in fact identical to) ${\alpha }^{\beta }={\alpha }^0=1=\left\{0\right\}=\left\{\text{∅}\right\}$. Thus in the following we assume that $\beta \ne 0$, which implies that $\alpha \ne 0$ as well since functions from $\beta$ to $\alpha$ cannot exist when $\beta \ne 0=\varnothing$ but $\alpha =0=\varnothing$.

Also if $\alpha =1=\left\{0\right\}$ (and still $\beta \ne 0$) then there is clearly only a single function $f:\beta \to \alpha$, namely that where $f(\xi )=0$ for all $\xi \in \beta$. Hence $S(\beta ,\alpha )=\left\{f\right\}$, which is clearly trivially isomorphic to ${\alpha }^{\beta }=1^{\beta }=1=\left\{0\right\}$. Thus in what follows we shall assume the more interesting case when $\alpha >1$ (and $\beta >0$).

Now we define a function $h:S(\beta ,\alpha )\to {\alpha }^{\beta }$. For any $f\in S(\beta ,\alpha )$ since $s(f)$ is a finite set of ordinals it follows that it is isomorphic to some natural number $n$. Thus its elements can be expressed as a strictly increasing sequence $\left\{s_k\right\}$ for $k<n$ where each $s_k\in \beta$ since $s(f)\subseteq \beta$. We now set

noting that it could be the case that $n=0$ so that $h(f)=0$, consistent with our convention.

First we show that $h(f)\in {\alpha }^{\beta }$ so that the range of $h$ is in fact a subset of ${\alpha }^{\beta }$. We begin by showing by induction on $m$ that

First for $m=0$ we have

Now suppose that

It follows from Exercise 6.5.14b that

since $\left\{s_k\right\}$ is a strictly increasing sequence so that $s_m+1\le s_{m+1}$. We then have

which completes the induction. Hence we have

by Exercise 6.5.14b since $s_{n-1}+1\le \beta$ since $s_{n-1}<\beta$. Clearly then $h(f)\in {\alpha }^{\beta }$ by definition of ordinal ordering.

Now we show that $h$ is an increasing function and therefore also injective. So consider any $f$ and $g$ in $S(\beta ,\alpha )$ such that $f\prec g$. Then by the definition of $\prec$ there is a ${\xi }_0<\beta$ such that $f({\xi }_0)<g({\xi }_0)$ and $f(\xi )=g(\xi )$ for all ${\xi }_0<\xi <\beta$. Now let $S=s(f)\cup s(g)$, which is clearly a finite set of ordinals since $s(f)$ and $s(g)$ are. Hence it is also isomorphic to a natural number $n$ so that it can be expressed as a strictly increasing sequence $\left\{s_k\right\}$ for $k<n$. Moreover

since for each term where $s_k\notin s(f)$ we have that $f(s_k)=0$ so that the term contributes nothing to the sum by Definition 6.5.6a (and similarly for $g$). Also since $f({\xi }_0)<g({\xi }_0)$ is has to be that $0<g({\xi }_0)$ so that ${\xi }_0\in s(g)$ and hence ${\xi }_0\in S$. From this it follows that there is an $m<n$ such that $s_m={\xi }_0$.

We then have

Thus it follows yet again from Lemma 6.5.4a that

which shows that $h$ is indeed increasing.

Lastly we show that $h$ is a surjective function, which then completes the proof that $h$ is an isomorphism so that $(S(\beta ,\alpha ),\prec )$ is isomorphic to $({\alpha }^{\beta },<)$ as desired. So consider any $\gamma \in {\alpha }^{\beta }$ so that by definition $\gamma <{\alpha }^{\beta }$.

We construct a function $f:\beta \to \alpha$ recursively by first initializing $f(\xi )=0$ for all $\xi \in \beta$. We then initialize $\rho =\gamma$ and perform the following iteratively:

If $\rho <\alpha$ then we set $f(0)=\rho$, noting that by definition $\rho \in \alpha$ and $0\in \beta$ since $\beta >0$. We then terminate the iteration, noting that it could be that $f(0)=\rho =0$.

If $\rho \ge \alpha$ then $1<\alpha \le \rho$ so that by Lemma 6.6.2 there is a greatest ordinal $\sigma$ such that ${\alpha }^{\sigma }\le \rho$. Then clearly we have ${\alpha }^{\sigma }\le \rho \le \gamma <{\alpha }^{\beta }$ so that it follows from Exercise 6.514b that $\sigma <\beta$ since $\alpha >1$ (the exercise only asserts implication in one direction but the other direction follows immediately similarly to the proof of Lemma 6.5.4a). Then since clearly ${\alpha }^{\sigma }\ne 0$ it follows from Theorem 6.6.3 that there are unique ordinals $\tau$ and ${\rho }^{\prime }$ such that

and ${\rho }^{\prime }<{\alpha }^{\sigma }$. We claim the following about these:

1.

$\tau <\alpha$. To the contrary, assume that $\tau \ge \alpha$ so that we have $$\rho ={\alpha }^{\sigma }\cdot \tau +{\rho }^{\prime }\ge {\alpha }^{\sigma }\cdot \tau +0={\alpha }^{\sigma }\cdot \tau \ge {\alpha }^{\sigma }\cdot \alpha ={\alpha }^{\sigma +1}$$

by Lemma 6.5.4, Exercise 6.5.7 since ${\alpha }^{\sigma }\ne 0$, and Definition 6.5.9b. However, this contradicts the definition of $\sigma$, i.e. that it is greatest ordinal $\xi$ such that $\rho \ge {\alpha }^{\xi }$. Hence it must be that $\tau <\alpha$.

2.

$0<\tau$. Were it the case that $\tau =0$ then we would have $$\rho ={\alpha }^{\sigma }\cdot \tau +{\rho }^{\prime }={\alpha }^{\sigma }\cdot 0+{\rho }^{\prime }=0+{\rho }^{\prime }={\rho }^{\prime }.$$

However, we then would have both $\rho \ge {\alpha }^{\sigma }$ and $\rho ={\rho }^{\prime }<{\alpha }^{\sigma }$, which is clearly a contradiction. So it must be that $\tau \ne 0$ so $\tau >0$.

3.

${\rho }^{\prime }<\rho$. We have $${\rho }^{\prime }<{\alpha }^{\sigma }={\alpha }^{\sigma }\cdot 1\le {\alpha }^{\sigma }\cdot \tau ={\alpha }^{\sigma }\cdot \tau +0\le {\alpha }^{\sigma }\cdot \tau +{\rho }^{\prime }=\rho$$

by Exercise 6.5.7 since ${\alpha }^{\sigma }\ne 0$ and Lemma 6.5.4 since $0\le {\rho }^{\prime }$, noting that we also just showed that $1\le \tau$ since $0<\tau$.

We therefore set $f(\sigma )=\tau$, noting that we have shown that $\sigma <\beta$ and $\tau <\alpha$ (so that $\sigma \in \beta$ and $\tau \in \alpha$). We then repeat the above, setting ${\rho }^{\prime }$ as the new $\rho$, noting that ${\rho }^{\prime }<\rho \le \gamma$ so that ${\rho }^{\prime }\le \gamma$ is still true.

Now it has to be that this construction terminates after a finite number of iterations since each $\rho$ in the iterations forms a strictly decreasing sequence of ordinals. Hence this sequence has to be finite since otherwise the range of this sequence would be a set of ordinals with no least element. It thus follows that $f(\xi )\ne 0$ for a finite number of $\xi \in \beta$ so that $s(f)$ is finite and $f\in S(\beta ,\alpha )$. The fact that $h(f)=\gamma$ follows immediately from the construction of $f$ so that $h$ is surjective since $\gamma$ was arbitrary. □