# How ae these three order types on $Z_+ \times Z_+$ different?

Let $Z_+$ denote the set of positive integers. Consider the following relations on $Z_+ \times Z_+$:

1. The dictionary order; that is, $(x_0,y_0) < (x_1,y_1)$ if either $x_0 < x_1$, or $x_0 = x_1$ and $y_0 < y_1$.

2. $(x_0, y_0) < (x_1,y_1)$ if either $x_0 - y_0 < x_1 - y_1$, or $x_0 - y_0 = x_1 - y_1$ and $y_0 < y_1$.

3. $(x_0, y_0) < (x_1,y_1)$ if either $x_0 + y_0 < x_1 + y_1$, or $x_0 + y_0 = x_1 + y_1$ and $y_0 < y_1$.

In these order relations, which elements have immediate predecessors?

In which order relations, does the set $Z_+ \times Z_+$ have a smallest element?

How to show that all the above three order types are different?

Let $A$ and $B$ be two non-empty sets with the order relations $<_A$ and $<_B$, respectively. Then the sets $A$ and $B$ are said to have the same order types if there exists a bijective function $f \colon A \to B$ such that $a_1 <_A a_2$ implies $f(a_1) <_B f(a_2)$ for any pair of elements $a_1$, $a_2$ in $A$. Otherwise, $A$ and $B$ are said to have different order types.

• Who has downvoted my question, and why? Please state the reasons for doing so also. – Saaqib Mahmood Oct 6 '14 at 9:00
• The most likely reason for the downvotes is that the question looks like a homework question that has just been copied onto this site. Of course, it's not possible to tell if it really is homework, or it it's an extra problem for self-study, or just something you made up. But questions that look indistinguishable from homework are often downvoted or put "on hold". In general, to avoid this, you should include additional context or work in the question itself. – Carl Mummert Oct 7 '14 at 17:43
• This Question has multiple parts. For example, it asks about identifying (for each of the three orderings) which elements have immediate predecessors. Again (for each of the orderings) when does a smallest element exist? Clearly the answers to these subquestions may help to answer the overall Question about order isomorphisms between these relations, but there is a lot of spade work to be done before one can say if a difficulty was really encountered. It's good that the definition of order types was added, but more needs to be done with the parts of the problem mentioned above. – hardmath Oct 8 '14 at 13:18

In the dictionary order relation, each element of $Z_+ \times Z_+$ has an immediate predecessor, except for elements of the form $(m, 1)$ for any $m \in Z_+$. Thus, the elements $(1,1)$, $(2,1)$, $(3,1)$, $...$ have no immediate predecessors; all other elements have immediate predecessors. The element $(1,1)$ is the smallest element in the dictionary ordering of $Z_+ \times Z_+$.
In the order defined as $(x_0,y_0) < (x_1,y_1)$ if $x_0-y_0 < x_1-y_1$, or $x_0-y_0 = x_1-y_1$ and $y_0 < y_1$, each element $(m,n)$ has as its immediate predecessor the element $(m-1, n-1)$, provided that $m>1$ and $n>1$; the elements of the form $(m,1)$ and $(1,n)$ have no immediate predecessors. For every element $(m,n)$, the element $(m,n+1)$ precedes it in this ordering; so there's no smallest element under this ordering of $Z_+ \times Z_+$.
In the order defined as $(x_0,y_0) < (x_1,y_1)$ if $x_0+y_0 < x_1+y_1$, or $x_0+y_0 = x_1+y_1$ and $y_0 < y_1$, every element $(m,n)$ has an immediate predecessor, namely the element $(m+1,n-1)$, except the element $(1,1)$, which has no immediate predecessor. The element $(1,1)$ is the smallest element.