### Archive

Archive for February 27th, 2009

## 1.3 Exercise 12

This problem, although cool because it exposes us to out-of-the-ordinary order relations on the Cartesian plane, was a little long, I felt.  Nevertheless, it shows that we can create order relations with smallest elements, with elements with no immediate predecessors, and with no smallest elements, and any happy combination as well.

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

(i) The dictionary order.

(ii) $(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$.

(iii) $(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?  Does the set have a smallest element?  Show that all three order types are different."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 29.)

------

SOLUTION

In this problem, I found it very helpful to write out the order sequence for the three cases, or even try to picture each on the Cartesian plane $\mathbb{Z}_+ \times \mathbb{Z}_+$.  Thus, for the dictionary order:

Having done so, it is a lot easier to see that the elements that do not have immediate predecessors are of the form $(j, 1)$. For, choose any element in column $j-1$ as a candidate, $(j-1, k)$.  The problem is that the set $\{(x, y) \verb| | \vert \verb| | (j-1, k) < (x, y) < (j, 1)\}$ is nonempty because the element $(j-1, k+1)$ is in it.  The tricky part may be the element  $(1, 1)$.  This element has no immediate predecessor because it is the smallest element (since it is less than any other element and equal to itself).

For the order of (ii), the order sequence looks like:

where $C = j-1$ and $D = 1-k$ are constants determined by the choice of $j$ or $k$.  Elements with no immediate predecessors are $(j, 1)$ and $(1, k)$.  In the first case, candidates to be the immediate predecessor of $(j, 1)$ are $((j+1)+m, (j+1)+m-C)$, but then set $\{(x, y) \verb| | \vert \verb| | ((j+1)+m, (j+1)+m-C) < (x, y) < (j, 1)\}$ is never empty, because the element $((j+1) + (m + 1), (j+1)+(m+1)-C)$ is in it.   Next for $(k, 1)$, candidates to be the immediate predecessor are of form $((k-1) + n + D, (k-1) + n)$, but then again the set $\{(x, y) \verb| | \vert \verb| | ((k-1)+n+D, (k-1)+n) < (x, y) < (1, k)\}$ is never empty, because the element $((k-1) + (n+1)+D, (k-1)+(n+1))$ is in it.

It is quite clear that there is no smallest element: for every element of form $(j, 1)$ and $(1, k)$ we can find a smaller element, as we've seen, and any other element $(j+m, j+m - C)$ a smaller element is $(j+(m-1), j+(m-1)-C)$.  Similarly, for any element $(k+n+D, k+n)$, a smaller element is $(k+(n-1)+D, k+(n-1))$.

Finally, for (iii):

with $C = j+1$.  Here, $(1, 1)$ is clearly the smallest element (it is less than every other element and equal to itself).  Furthermore, every element except the smallest has an immediate predecessor.

All of these order relations are of different order type.  First we show that there is no order preserving bijection from $\mathbb{Z_+} \times \mathbb{Z_+}$ ordered by $<_{ii}$ to $\mathbb{Z_+} \times \mathbb{Z_+}$ ordered by $<_i$ or $\mathbb{Z_+} \times \mathbb{Z_+}$ ordered by $<_{iii}$.  For, suppose there is.  Then there exists an element $(j, 1)$, $(k, 1)$, $(j+m, j+m-C)$, or $(k+n+D, k+n)$ ordered by $<_{ii}$ that maps to the smallest element of $\mathbb{Z_+} \times \mathbb{Z_+}$ ordered by $<_i$ or $<_{iii}$.  The problem is that, as we've seen, for each of these we can find a smaller element, where we cannot find a smaller element for the smallest element of $\mathbb{Z_+} \times \mathbb{Z_+}$ ordered by $<_i$ or $<_{iii}$.  Next we show that there cannot exist a bijection from $\mathbb{Z_+} \times \mathbb{Z_+}$ ordered by $<_i$ to $\mathbb{Z_+} \times \mathbb{Z_+}$ ordered by $<_{iii}$. Suppose there is.  An element $(j, 1)$, having no immediate predecessors under $<_{i}$, would have to map to the only element that does not have immediate predecessors under $<_{iii}$, the smallest element.  But then there are elements $(j-1, k)$ that are less than $(j, k)$ that would be undefined under such a map, so the map is not bijective.

Thus, the three order relations are different order type.

Categories: