## 1.3 Exercise 9

The dictionary order relation is very important, because it describes in probably the most sensible way how we can order points on the Cartesian plane (or on any Cartesian product).

"Check that the dictionary order is an order relation."

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

-----

SOLUTION

First, notice that the dictionary order is defined on (and thus the dictionary order relation lives in ).

Comparability. Pick . Then either , or (or both). If , then either or (or both). Notice that if , then , contrary to our pick or assumption. Thus, comparability is true for all elements of .

Non-reflexivity. We want to show that for no the statement holds. Suppose it does for some element. Then this means , but this contradicts the identity or reflexive property of equality. It follows , but then , again a contradiction. Non-reflexivity holds therefore for all elements .

Transitivity. Picking , , and , we have to show that and implies . As in previous problems, we can check this by proceeding in cases. In the first case, and . This means . Here may be a sticky part: we have to know that the set is ordered (and transitivity holds in that set), as we do because we know is an ordering relation. Thus, by transitivity of the set , . In the second case, and . In this case we use substitution and arrive at . In the third case, and . Again by substitution . In the fourth case, and . This implies and . In turn, this means . Again, we have to know that is ordered (as we do, by ), and thus transitivity holds for the elements of : . It follows that the order relation on inherits transitivity.