Exercise 7.1.1

Proof. First we note that since $\alpha$ is infinite we have $\alpha +1>\alpha \ge \omega$. We then construct a bijection from $\alpha +1$ to $\alpha$. So define $f:\alpha +1\to \alpha$ by

for $\beta \in \alpha +1$.

First we show that $f$ is injective. So consider any $\beta$ and $\gamma$ in $\alpha +1$ where $\beta \ne \gamma$. Without loss of generality we can assume that $\beta <\gamma$. We then have the following:

Case: $\beta <\omega$. Then clearly $f(\beta )=\beta +1<\omega$ since $\beta <\omega$ and $\omega$ is a limit ordinal, but we also clearly have that $0<\beta +1=f(\beta )$. Now, if also $\gamma <\omega$ then clearly $f(\beta )=\beta +1<\gamma +1=f(\gamma )$ since $\beta <\gamma$. If $\gamma \ge \omega$ and $\gamma \ne \alpha$ then we have $f(\beta )<\omega \le \gamma =f(\gamma )$. Lastly if $\gamma =\alpha$ then we have $f(\gamma )=0<f(\beta )$.

Case: $\beta \ge \omega$ and $\beta \ne \alpha$. Here since $\beta <\gamma$ we have $\omega \le \beta <\gamma$. Thus if also $\gamma \ne \alpha$ then clearly we have $f(\beta )=\beta <\gamma =f(\gamma )$. On the other hand if $\gamma =\alpha$ then $f(\gamma )=0<\omega \le \beta =f(\beta )$.

Thus in every case we have $f(\beta )\ne f(\gamma )$, thereby showing that $f$ is injective. We note that the case in which $\beta =\alpha$ is impossible since $\alpha$ is the greatest element of $\alpha +1$ but $\gamma >\beta$ and $\gamma \in \alpha +1$.

Next we show that $f$ is surjective. So consider any $\beta \in \alpha$.

Case: $\beta <\omega$. If $\beta =0$ then clearly $f(\alpha )=0=\beta$. On the other hand if $0<\beta <\omega$ then $\beta$ is a successor ordinal, say $\beta =\gamma +1$, so that $\gamma <\beta <\omega$ hence clearly $\gamma \in \alpha +1$ and $f(\gamma )=\gamma +1=\beta$.

Case: $\beta \ge \omega$. Then since $\beta \in \alpha$ we have $\beta <\alpha <\alpha +1$ so that $\beta \ne \alpha$ but $\beta \in \alpha +1$. Then clearly $f(\beta )=\beta$.

Hence in all cases there is a $\gamma \in \alpha +1$ such that $f(\gamma )=\beta$ so that $f$ is injective. Therefore we have shown that $f$ is a bijection so that by definition $\alpha +1$ and $\alpha$ are equipotent. □

Proof. Since $A$ is infinite and the isomorphism from $A$ to $\alpha$ is a bijective function, it follows that they are equipotent so that $\alpha$ is also infinite. Then by Lemma 1 $\alpha$ is equipotent to $\alpha +1$ so that $A$ is also equipotent to $\alpha +1$. Hence there is an $f:A\to \alpha +1$ that is bijective. We then simply re-order $A$ according to $\alpha +1$, i.e. we create the following order on $A$:

so that clearly $(A,R)$ is isomorphic to $(\alpha +1,<)$. □

Proof. For an infinite well-orderable set $X$ we show that $X$ has an infinite number of non-isomorphic well-orderings. So let $\prec$ be a well-ordering of $X$ so that by Theorem 6.3.1 $(X,\prec )$ is isomorphic to some ordinal $\alpha$. We then show by induction that, for any natural number $n$, there is an ordering $R_n$ of $X$ such that it is isomorphic to $\alpha +n$. For $n=0$ we have that, for $R_0=\prec$, clearly $(X,R_0)$ is isomorphic to $(\alpha ,<)$ by what has already been established. Now suppose that there is an ordering $R_n$ of $X$ such that $(X,R_n)$ is isomorphic to $(\alpha +n,<)$. Then since $X$ is an infinite set it follows from Lemma 2 that there is an ordering $R_{n+1}$ such that $X$ is isomorphic to $(\alpha +n)+1=\alpha +(n+1)$. This completes the inductive proof. We note that clearly each of these re-orderings are mutually non-isomorphic since different ordinals are not isomorphic to each other. □