Exercise 6.1.8

Proof. Let $\prec$ be the lexicographic ordering of $W=𝑵\times \left\{0,1\right\}$ and ${\prec }^{\prime }$ be the lexicographic ordering of $W^{\prime }=\left\{0,1\right\}\times 𝑵$.

First we define $f:W\to \omega$ by

for $(n,m)\in W$. Clearly each $f(n,m)\in 𝑵=\omega$.

Now consider any $k\in \omega =𝑵$. If $k$ is even then $k=2n$ for some $n\in 𝑵$ so set $w=(n,0)\in W$. Then clearly $f(w)=f(n,0)=2n=k$. On the other hand if $k$ is even then $k=2n+1$ for some $n\in 𝑵$ so set $w=(n,1)\in W$. Then clearly $f(w)=f(n,1)=2n+1=k$. This shows that $f$ is surjective.

Now consider any $w_1=(n_1,m_1)$ and $w_2=(n_2,m_2)$ in $W$ where $w_1\prec w_2$.

Case: $n_1=n_2$. Then since $w_1\prec w_2$ it has to be that $m_1<m_2$, and since $m_1,m_2\in \left\{0,1\right\}$ it has to be that $m_1=0$ and $m_2=1$. From this it follows that

Case: $n_1\ne n_2$. Then since $w_1\prec w_2$ it has to be that $n_1<n_2$. Then $n_1+1\le n_2$ and since also $m_1<2$ we have

Hence in all cases $f(w_1)<f(w_2)$ so that $f$ is increasing and therefore injective and isomorphic. Therefore $W$ is isomorphic to $\omega$.

Now we define $g:W^{\prime }\to \omega +\omega$ by

for $(n,m)\in W^{\prime }$. Clearly since $m\in 𝑵$ we have that $g(n,m)\in \omega +\omega$ for all $(n,m)\in W^{\prime }$.

Now consider any $\alpha \in \omega +\omega$. If $\alpha \in \omega =𝑵$ then $(0,\alpha )\in W^{\prime }$ and $g(0,\alpha )=\alpha$. On the other hand if $\alpha =\omega +m$ for some $m\in 𝑵$ then $(1,m)\in W^{\prime }$ and $g(1,m)=\omega +m=\alpha$. Therefore $g$ is surjective.

Now consider any $w_1=(n_1,m_1)$ and $w_2=(n_2,m_2)$ in $W^{\prime }$ where $w_1{\prec }^{\prime }{w}_2$.

Case: $n_1=n_2$. Then since $w_1{\prec }^{\prime }{w}_2$ it has to be that $m_1<m_2$. If $n_1=n_2=0$ then

On the other hand if $n_1=n_2=1$ then

Case: $n_1\ne n_2$. Then since $w_1{\prec }^{\prime }{w}_2$ it has to be that $n_1<n_2$. Moreover since $n_1,n_2\in \left\{0,1\right\}$ it has to be that $n_1=0$ and $n_2=1$ so that

Hence in all cases $g(w_1)<g(w_2)$ so that $g$ is increasing and therefore injective and an isomorphism. Therefore $W^{\prime }$ is isomorphic to $\omega +\omega$.

Now, since $w\in \omega +\omega$ we have that $\omega <\omega +\omega$ and so are distinct ordinals. Therefore by the remarks following Theorem 6.2.10 $\omega$ and $\omega +\omega$ are not isomorphic. If $W$ and $W^{\prime }$ were isomorphic with $h$ as the isomorphism then $g\circ h\circ f^{-1}$ would be an isomorphism from $\omega$ to $\omega +\omega$, which is impossible. So it must be that $W$ and $W^{\prime }$ are not isomorphic. □