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 $A \times B$ (and thus the dictionary order relation lives in $(A \times B) \times (A \times B)$).

Comparability.   Pick $a_1 \times b_1 \neq a_2 \times b_2$.  Then either $a_1 <_A a_2$, or $a_1 >_A a_2$ (or both). If $a_1 = a_2$, then either $b_1 <_B b_2$ or $b_1 >_B b_2$ (or both).  Notice that if $b_1 = b_2$, then $a_1 \times b_1 = a_2 \times b_2$, contrary to our pick or assumption.  Thus, comparability is true for all elements of $A \times B$.

Non-reflexivity.  We want to show that for no $a \times b \in A \times B$ the statement $(a \times b, a \times b) \in C$ holds.  Suppose it does for some element.  Then this means $a <_A a$, but this contradicts the identity or reflexive property of equality.  It follows $a = a$, but then $b <_B b$, again a contradiction.  Non-reflexivity holds therefore for all elements $a \times b$.

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

Categories: