## 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 denote the set of positive integers. Consider the following order relations on :

(i) The dictionary order.

(ii) if either , or and .

(iii) if either , or and .

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 . 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 . For, choose any element in column as a candidate, . The problem is that the set is nonempty because the element is in it. The tricky part may be the element . 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 and are constants determined by the choice of or . Elements with no immediate predecessors are and . In the first case, candidates to be the immediate predecessor of are , but then set is never empty, because the element is in it. Next for , candidates to be the immediate predecessor are of form , but then again the set is never empty, because the element is in it.

It is quite clear that there is no smallest element: for every element of form and we can find a smaller element, as we've seen, and any other element a smaller element is . Similarly, for any element , a smaller element is .

Finally, for (iii):

with . Here, 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 ordered by to ordered by or ordered by . For, suppose there is. Then there exists an element , , , or ordered by that maps to the smallest element of ordered by or . 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 ordered by or . Next we show that there cannot exist a bijection from ordered by to ordered by . Suppose there is. An element , having no immediate predecessors under , would have to map to the only element that does not have immediate predecessors under , the smallest element. But then there are elements that are less than that would be undefined under such a map, so the map is not bijective.

Thus, the three order relations are different order type.