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.

  • $\begingroup$ Who has downvoted my question, and why? Please state the reasons for doing so also. $\endgroup$ – Saaqib Mahmood Oct 6 '14 at 9:00
  • $\begingroup$ 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. $\endgroup$ – Carl Mummert Oct 7 '14 at 17:43
  • $\begingroup$ 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. $\endgroup$ – hardmath Oct 8 '14 at 13:18

I think I've arrived at the answers to my own questions.

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.

From the above observations, it is now easy to show these three orderings to be different.

  • 1
    $\begingroup$ When you are unable to solve a problem that you post, and later work out the answer, it is fine to post it like this. I voted +1 $\endgroup$ – Carl Mummert Oct 7 '14 at 17:43
  • $\begingroup$ Carl Mummert, thanks, but have I managed to arrive at the correct answers to my own questions? Is what I've posted as an answer correct according to your knowledge and reckoning? $\endgroup$ – Saaqib Mahmood Oct 9 '14 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.