Exercise 10.3

Proof. First, clearly $(1,1)$ is the smallest element of both ordered sets. For brevity let $A=\times {\mathbb{Z}}_{\text{+}}$, $B={\mathbb{Z}}_{\text{+}}\times$, and ${<}_A$ and ${<}_B$ be the corresponding dictionary orderings, with $<$ being the normal ordering of ${\mathbb{Z}}_{\text{+}}$.

So assume that they do have the same order type so that there is an order-preserving bijection $f:A\to B$. Consider $(2,1)\in A$, which is clearly not the smallest element since $(2,1)\ne (1,1)$. Let $(n,b)=f(2,1)\in B$, which cannot be the smallest element of $B$ since $f$ preserves order, so that $(n,b)\ne (1,1)$. Clearly $b\in$ so that $b=1$ or $b=2$. In the former cases we must have that $n>1$ so that $n-1\in {\mathbb{Z}}_{\text{+}}$. So set $y=(n-1,2)$. In the latter case set $y=(n,1)$. It is easy to see, and trivial to formally show, that $y$ is the immediate predecessor of $(n,b)$ in either case.

Now let $x=f^{-1}(y)$, noting that $f^{-1}$ is an order-preserving bijection from $B$ to $A$ since $f$ is an order-preserving bijection. It then follows that $x{<}_A(2,1)$ since $f(x)=y{<}_B(n,b)=f(2,1)$. If $x=(m,a)$ then it has to be that $m<2$ so that $m=1$ (because $m\in$) since there is no $a\in {\mathbb{Z}}_{\text{+}}$ where $a<1$. Thus $x=(1,a)$ for some $a\in {\mathbb{Z}}_{\text{+}}$. We then have that $a+1\in {\mathbb{Z}}_{\text{+}}$ so that clearly $x=(1,a){<}_A(1,a+1){<}_A(2,1)$. From this we have, $y=f(1,a){<}_{B}f(1,a+1){<}_{B}f(2,1)=(n,b)$, which contradicts the fact that $y$ is the immediate predecessor of $(n,b)$. So it has to be that they do not have the same order type. □