Exercise 3.12

Proof. This may seem fairly obvious but we show it formally anyway. Suppose that ${<}_A$ and ${<}_B$ are the orders on $A$ and $B$, respectively. Let $a$ be the smallest element of $A$ and suppose to the contrary that they do have the same order type. Then there is a bijection $f:A\to B$ that preserves order, noting that $f^{-1}$ is also then a bijection. Now, since $B$ has no smallest element, there must be a $b\in B$ where $b{<}_{B}f(a)$. Setting $a^{\prime }=f^{-1}(b)$ so that $f(a^{\prime })=b$ we have that $f(a^{\prime })=b{<}_{B}f(a)$, and hence it has to be that $a^{\prime }{<}_{A}a$ since otherwise we’d have $a{\text{≤}}_A{a}^{\prime }$ so that $f(a){\text{≤}}_{B}f(a^{\prime })$. However, $a^{\prime }<a$ means that it is not true that $a\le a^{\prime }$ by Lemma 1, which contradicts the fact that $a$ is the smallest element of $A$. Therefore it must be that no such $f$ exists so that $A$ and $B$ have different order types. □

Proof. First consider any point $(x_1,y_1)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ where $(x_1,y_1)\notin A$ so that $y_0\ne 1$. It then follows that $y_1>1$ since $1$ is the smallest positive integer. Then set $x_0=x_1$ and $y_0=y_1-1$ so that clearly $(x_0,y_0)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ since $y_0>0$ because $y_1>1$. Clearly also $x_0=x_1$ and $y_0<y_1$ so that $(x_0,y_0)<(x_1,y_1)$ in the dictionary order. We claim that $(x_0,y_0)$ is the immediate predecessor of $(x_1,y_1)$. So suppose to the contrary that there is an $(x_2,y_2)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ such that $(x_0,y_0)<(x_2,y_2)<(x_1,y_1)$. It cannot be that $x_0<x_2$ since then we would have $x_1=x_0<x_2$ so that $(x_1,y_1)<(x_2,y_2)$, which by Lemma 1 contradicts the fact that $(x_2,y_2)<(x_1,y_1)$. So it has to be that $x_0=x_2$ and $y_0<y_2$. Since then $x_2=x_0=x_1$, it must also be that $y_2<y_1$ since $(x_2,y_2)<(x_1,y_1)$. But then we have $y_0<y_2<y_1=y_0+1$, which is not possible since $y_1=y_0+1$ is the immediate successor of $y_0$ in ${\mathbb{Z}}_{\text{+}}$ so that there can be no integers between them. So it must be that no $(x_2,y_2)$ exists so that $(x_0,y_0)$ is the immediate predecessor of $(x_1,y_1)$. Thus every element not in $A$ has an immediate predecessor.

Now consider any $(x_1,y_1)\in A$ so that $y_1=1$, and consider any point $(x_0,y_0)<(x_1,y_1)$. It cannot be that $x_0=x_1$ since then we would have $y_0<y_1=1$, which is not possible since $1$ is the smallest positive integer. So it must be that $x_0<x_1$. Then let $x_2=x_0$ and $y_2=y_0+1$ so that clearly $(x_2,y_2)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ since $y+1$ is always still a positive integer if $y$ is. Then we have that $x_0=x_2$ and $y_0<y_0+1=y_2$, and hence $(x_0,y_0)<(x_2,y_2)$. We also have $x_2=x_0<x_1$ so that $(x_2,y_2)<(x_1,y_1)$. Therefore $(x_0,y_0)<(x_2,y_2)<(x_1,y_1)$, which shows that $(x_0,y_0)$ is not the immediate predecessor of $(x_1,y_1)$. This shows that $(x_1,y_1)$ has no immediate predecessor since $(x_0,y_0)<(x_1,y_1)$ was arbitrary. Since $(x_1,y_1)\in A$ was arbitrary, this completes the proof that every element in ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ has an immediate predecessor except those in $A$.

It is easy to prove that $(1,1)$ is the smallest element in the dictionary order. Consider any $(x_0,y_0)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ and suppose that $(x_0,y_0)<(1,1)$. It cannot be that $x_0<1$ since $1$ is the smallest positive integer. So then $x_0=1$ and $y_0<1$, but this is also not possible, again since $1$ is the smallest positive integer. Thus it cannot be that $(x_0,y_0)<(1,1)$, so it must be that $(1,1)\le (x_0,y_0)$ by Lemma 1. This shows that $(1,1)$ is the smallest element since $(x_0,y_0)$ was arbitrary. □

Proof. First consider any $(x_1,y_1)\notin A$ so that $x_1\ne 1$ and $y_1\ne 1$. Then it has to be that $x_1,y_1>1$. So set $(x_0,y_0)=(x_1-1,y_1-1)$ so that clearly still $(x_0,y_0)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$. Then $x_0-y_0=(x_1-1)-(y_1-1)=x_1-1-y_1+1=x_1-y_1$. We also have $y_0=y_1-1<y_1$ so that $(x_0,y_0)<(x_1,y_1)$. Now suppose that there is an $(x_2,y_2)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ where $(x_0,y_0)<(x_2,y_2)<(x_1,y_1)$. It cannot be that $x_0-y_0<x_2-y_2$ since then we would have $x_1-y_1=x_0-y_0<x_2-y_2$ so that $(x_1,y_1)<(x_2,y_2)$, which we know cannot be the case since $(x_2,y_2)<(x_1,y_1)$. So it must be that $x_2-y_2=x_0-y_0=x_1-y_1$ and $y_0<y_2$, but then we must have $y_0<y_2<y_1=y_0+1$, noting that $y_2<y_1$ because $x_2-y_2=x_1-y_1$ and $(x_2,y_2)<(x_1,y_1)$. However, this is not possible since of course $y_0+1$ is the immediate successor of $y_0$ in ${\mathbb{Z}}_{\text{+}}$. So then it has to be that no such $(x_2,y_2)$ exists so that $(x_0,y_0)$ is the immediate predecessor of $(x_1,y_1)$. This shows that every point not in $A$ has an immediate predecessor since $(x_1,y_1)$ was arbitrary.

Now suppose that $(x_1,y_1)\in A$ so that $x_1=1$ or $y_1=1$, and consider any $(x_0,y_0)<(x_1,y_1)$.

• Case: $x_1=1$. Suppose that $x_0-y_0=x_1-y_1$ and $y_0<y_1$. Then we would have $-y_0>-y_1$ and $x_0-y_0=x_1-y_1=0-y_1=-y_1<-y_0$ so that $x_0<0$ (by adding $y_0$ to both sides), which is not possible.
• Case: $y_1=1$. It clearly cannot be that case that $x_0-y_0=x_1-y_1$ and $y_0<y_1$ since then $y_0<y_1=1$, which is not possible.

So in either case it must be that $x_0-y_0<x_1-y_1$ since $(x_0,y_0)<(x_1,y_1)$. So set the point $(x_2,y_2)=(x_0+1,y_0+1)$, which is clearly still an element of ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$. We then have $x_2-y_2=(x_0+1)-(y_0+1)=x_0+1-y_0-1=x_0-y_0<x_1-y_1$ so that $(x_2,y_2)<(x_1,y_1)$. We also have $x_0-y_0=x_2-y_2$ and $y_0<y_0+1=y_2$ so that also $(x_0,y_0)<(x_2,y_2)$. Hence $(x_0,y_0)<(x_2,y_2)<(x_1,y_1)$ so that $(x_0,y_0)$ is not the immediate predecessor of $(x_1,y_1)$. Since $(x_0,y_0)<(x_1,y_1)$ was arbitrary, this shows that $(x_1,y_1)$ has no immediate predecessor at all. Since $(x_1,y_1)\in A$ was arbitrary, this shows that no element of $A$ has an immediate predecessor.

To show that ${\mathbb{Z}}_{\text{+}}$ in this order has no smallest element, consider absolutely any $(x_1,y_1)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$. Let $(x_0,y_0)=(x_1,y_1+1)$ so that of course $(x_0,y_0)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$. We then have that $x_0-y_0=x_1-(y_1+1)=(x_1-y_1)-1<x_1-y_1$ so that $(x_0,y_0)<(x_1,y_1)$. Then of course is it not true that $(x_1,y_1)\le (x_0,y_0)$ by Lemma 1 so that $(x_1,y_1)$ cannot be the smallest element. Then, since $(x_1,y_1)$ was arbitrary, this shows that ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ has no smallest element in this order. □

Proof. First we show that $(x_0,y_0)=(1,1)$ is the smallest element, from which it follows that it cannot have an immediate predecessor since it has no predecessors at all. Consider any $(x_1,y_1)$ in ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$. If $(x_1,y_1)=(1,1)$ then of course $(x_0,y_0)=(1,1)\le (x_1,y_1)$ is true, so assume that $(x_1,y_1)\ne (1,1)$ so that either $x_1\ne 1$ or $y_1\ne 1$. If $x_1\ne 1$ then it has to be that $x_1>1$ so that $x_0+y_0=1+1\le 1+y_1<x_1+y_1$, and hence $(x_0,y_0)<(x_1,y_1)$. If $y_1\ne 1$ then $y_1>1$ so that again $x_0+y_0=1+1\le x_1+1<x_1+y_1$, and hence $(x_0,y_0)<(x_1,y_1)$. Thus in every case $(x_0,y_0)\le (x_1,y_1)$, which shows that $(x_0,y_0)=(1,1)$ is the smallest element since $(x_1,y_1)$ was arbitrary.

Now we show that every other element of ${\mathbb{Z}}_{\text{+}}$ has an immediate predecessor in this order. So consider any $(x_1,y_1)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ where $(x_1,y_1)\ne (1,1)$. Hence either $x_1\ne 1$ or $y_1\ne 1$.

• Case: $y_1=1$. Then it has to be that $x_1\ne 1$ so that $x_1>1$. We claim that $(x_0,y_0)=(1,x_1-1)$ is the immediate predecessor of $(x_1,y_1)$. First we note that clearly $(x_0,y_0)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ since $x_1>1$. We also have that $x_0+y_0=1+x_1-1=x_1<x_1+y_1$ since $0<1=y_1$, and so $(x_0,y_0)<(x_1,y_1)$. Now suppose that there is a point $(x_2,y_2)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ where $(x_0,y_0)<(x_2,y_2)<(x_1,y_1)$. It cannot be that $x_1+y_1=x_2+y_2$ and $y_1<y_2$ because then we would have $y_2<y_1=1$, which is not possible since $y_2\in {\mathbb{Z}}_{\text{+}}$. So it must be that $x_2+y_2<x_1+y_1=x_1+1$ since $(x_2,y_2)<(x_1,y_1)$. Now, since also $(x_0,y_0)<(x_2,y_2)$, it must be that $x_0+y_0\le x_2+y_2$, but then we have $x_1=1+(x_1-1)=x_0+y_0\le x_2+y_2<x_1+1$, which is impossible. So it has to be that no such $(x_2,y_2)$ exists so that $(x_0,y_0)$ is the immediate predecessor of $(x_1,y_1)$.

• Case: $y_1\ne 1$. Then it has to be that $y_1>1$ so that the point $(x_0,y_0)=(x_1+1,y_1-1)$ is still an element of ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$. We show that $(x_0,y_0)$ is the immediate predecessor of $(x_1,y_1)$. First we have that $x_0+y_0=(x_1+1)+(y_1-1)=x_1+y_1$ and $y_0=y_1-1<y_1$ so that $(x_0,y_0)<(x_1,y_1)$. Now suppose that there a point $(x_2,y_2)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ where $(x_0,y_0)<(x_2,y_2)<(x_1,y_1)$. Then it has to be that $x_0+y_0\le x_2+y_2\le x_1+y_1$ so that we have $x_1+y_1=(x_1+1)+(y_1-1)=x_0+y_0\le x_2+y_2\le x_1+y_1$ so that $x_0+y_0=x_2+y_2=x_1+y_1$. But then we must have $y_1-1=y_0<y_2<y_1$, which is not possible since $y_1-1$ is the immediate predecessor of $y_1$ in ${\mathbb{Z}}_{\text{+}}$. So no such $(x_2,y_2)$ can exists, and hence $(x_0,y_0)$ is the immediate predecessor of $(x_1,y_1)$.

  This in all cases $(x_1,y_1)$ has an immediate predecessor, which shows the desired result since $(x_1,y_1)\ne (1,1)$ was arbitrary.

Proof. It follows immediately from Lemma that order (i) and order (ii) do not have the same order type since (i) has a smallest element while (ii) does not. Similarly order (iii) and order (ii) cannot have the same order type for the same reason. So all that remains to be shown is that orders (i) and (iii) have different order types.

So denote order (i) with $<$ and order (iii) with $\prec$ and suppose to the contrary that they do have the same order type. Then there is a bijection $f:{\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}\to {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ that preserves order, supposing that the domain has the dictionary order $<$ and the range has the order $\prec$. Then of course $f^{-1}$ is also a bijection that preserves order. It was shown above that ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ with $<$ has countably many elements with no immediate predecessor, whereas ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ with $\prec$ has only a single such element, namely the smallest element $(1,1)$.

Thus we can choose an element $(x_1,y_1)$ of ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ that has no immediate predecessor in $<$ but also such that $f(x_1,y_1)\ne (1,1)$ so that $f(x_1,y_1)$ does have an immediate predecessor in $\prec$. So let $(u_0,v_0)$ be the immediate predecessor of $f(x_1,y_1)$ in $\prec$ and set $(x_0,y_0)=f^{-1}(u_0,v_0)$ so that $(u_0,v_0)=f(x_0,y_0)$. Then of course $(x_0,y_0)<(x_1,y_1)$ since $f(x_0,y_0)=(u_0,v_0)\prec f(x_1,y_1)$ and $f$ preserves order. But since $(x_1,y_1)$ has no immediate predecessor in $<$, there is a point $(x_2,y_2)$ such that $(x_0,y_0)<(x_2,y_2)<(x_1,y_1)$. We then have that $(u_0,v_0)=f(x_0,y_0)\prec f(x_2,y_2)\prec f(x_1,y_1)$ since $f$ preserves order, which is a contradiction since $(u_0,v_0)$ is the immediate predecessor of $f(x_1,y_1)$. So it must be that no such order-preserving $f$ exists and hence the two orders do not have the same order type. □