Archive for February 12th, 2009

1.3 Exercise 9

February 12th, 2009 No comments

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.)



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.