Exercise 6.1.5

Proof. Suppose that $(W,\prec )$ is the sum and associated order as defined in Lemma 4.4.5. By that lemma $\prec$ is a linear ordering but we must show that it is also a well-ordering.

First we note that clearly $W_1$ and $W_2$ are both well-orderings since they are both isomorphic to $(𝑵,<)$. So consider any non-empty subset of $A$ of $W=W_1\cup W_2$. Let $A_1=A\cap W_1$ and $A_2=A\cap W_2$ so that clearly they are disjoint since $W_1$ and $W_2$ are and $A_1\subseteq W_1$ and $A_2\subseteq W_2$. Also since $A$ is not empty either $A_1$ or $A_2$ (or both) are also not empty. If $A_1$ is not empty then since $A_1\subseteq W_1$ and $(W_1,{<}_1)$ is a well-ordering there is a least element $a\in A_1$. Otherwise if $A_1$ is empty then $A_2$ is not and it has a least element $a$ since it is a non-empty subset of the well-ordered $(W_2,{<}_2)$. Now consider any $b\in A$ so that also $b\in W$. If $b\in W_1$ then $b\in A_1$ so that $A_1$ is not empty. In this case since $a$ is the least element of $A_1$ we have $a{\le }_{1}b$ so that by definition $a\preccurlyeq b$. On the other hand if $b\in W_2$ then $b\in A_2$. If $A_1$ was empty then $a$ is the least element of $A_2$ and $b\in A_2$ so that again $a{\le }_{2}b$, hence by definition $a\preccurlyeq b$. If $A_1$ is not empty then $a\in A_1\subseteq W_1$ so that by the definition of the sum $(W,\prec )$ we have that $a\prec b$ since $b\in W_2$. Hence also $a\preccurlyeq b$. Thus in all cases $a\preccurlyeq b$ so that $a$ is the least element of $A$ since $b$ was arbitrary.

Now we show that $(W,\prec )$ is isomorphic to $(\omega +\omega ,<)$. First, since $(W_1,{<}_1)$ and $(W_2,{<}_2)$ are both isomorphic to $(𝑵,<)$ let $f_1:W_1\to 𝑵$ and $f_2:W_2\to 𝑵$ be isomorphisms. Now we define $g:W\to \omega +\omega$ by

for $w\in W=W_1\cup W_2$, noting that $g$ is well defined since $W_1$ and $W_2$ are disjoint. Clearly since $\mathrm{ran}(f_1)=\mathrm{ran}(f_2)=𝑵$ we have that $g(w)\in \omega +\omega$ for all $w\in W$.

Consider any $k\in \omega +\omega$ so that $k\in 𝑵$ or $k=\omega +n$ for some $n\in 𝑵$. In the former case let $w=f_1^{-1}(k)$, which exists since $f_1$ is bijective. Thus $w\in W_1$ so that by definition $g(w)=f_1(w)=k$. In the latter case let $w=f_2^{-1}(n)$, which exists since $f_2$ is bijective. Thus $w\in W_2$ so that by definition $g(w)=\omega +f_2(w)=\omega +n=k$. This shows that $g$ is surjective.

Now we show that $g$ is an increasing function. So consider any $w_1,w_2\in W$ where $w_1\prec w_2$.

Case: $w_1,w_2\in W_1$. Then since $w_1\prec w_2$ we have that $w_1{<}_1{w}_2$. It then follows that $g(w_1)=f(w_1)<f_{(}{w}_2)=g(w_2)$ since $f_1$ is an isomorphism.

Case: $w_1,w_2\in W_2$. Then since $w_1\prec w_2$ we have that $w_1{<}_2{w}_2$. It then follows that $f_2(w_1)<f_2(w_2)$ since $f_2$ is an isomorphism. Hence we clearly then have $g(w_1)=\omega +f_2(w_1)<\omega +f_2(w_2)=g(w_2)$.

Case: $w_1\in W_1$ and $w_2\in W_2$. Then we have that $g(w_1)=f_1(w_1)\in 𝑵$ and $g(w_2)=\omega +f_2(w_2)$ so that clearly $g(w_1)<\omega \le g(w_2)$ since $f_2(w_2)\in 𝑵$.

Case: $w_2\in W_1$ and $w_1\in W_2$. If this were the case then by the definition of $\prec$ we would have that $w_2\prec w_1$, which contradicts the established hypothesis that $w_1\prec w_2$. Hence this case is impossible.

Hence in all cases $g(w_1)<g(w_2)$ so that $g$ is increasing. Therefore it is also injective and an isomorphism (since we’ve shown that it is surjective as well). Thus we’ve shown that $W$ is isomorphic to $\omega +\omega$ as desired. □