Archive for February 10th, 2009

1.3 Exercise 7

February 10th, 2009 No comments

After doing the same procedure for an exercise on equivalence relations, this question should pose no problem.  Important is starting to visualize relations on the Cartesian product of a set.  What does an order relation look like?  It is upper or lower triangular (by comparability and transitivity), with the identity line deleted (because of non-reflexivity).  Contrast this with what an equivalence relation looks like: a square (because of symmetry and transitivity) with an extended diagonal (the identity line by reflexivity).

"Show that the restriction of an order relation is an order relation."   

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



Suppose there is an order relation defined on the elements of  A .

Comparability:  Pick  x, y \in A with  x \neq y  (x, y) \in A \times A and  (y, x) \in A \times A , but importantly, either  (x, y) \in C or  (y, x) \in C (or both).  Now suppose these same elements  x, y \in A_0 .  Then  (x, y) \in A_0 \times A_0 , and  (y, x) \in A_0 \times A_0 .  We already know that either one or the other (or both) of such elements belong to  C .  Thus either  (x, y) \in C \cap A_0 \times A_0 or  (y, x) \in C \cap A_0 \times A_0 (or both).  The restriction inherits comparability.

Non-reflexivity.  Picking  x \in A , it is clear that  (x, x) \in A \times A .  We know, however, that  (x, x) \notin C .  If such  x is picked so that it also belongs to  A_0 , then  (x, x) \in A_0 .  But such an element of the cross product is not in  C , we've established, so it cannot possibly be in the intersection of  C with  A_0 \times A_0 .  Thus,  C \cap A_0 \times A_0 inherits non-reflexivity.

Transitivity.  Picking different elements  x, y, z \in A , it is clear that in particular the elements  (x, y), (y, z) , and  (x, z) \in A \times A .  Suppose these elements  x, y, z \in A_0 , and thus   (x, y), (y, z) , and  (x, z) \in A_0 \times A_0 .  Now further suppose  (x, y), (y, z) \in C .  By transitivity of the order relation in  A ,  (x, z) \in C .  This last element is in both  C and  A_0 \times A_0 , and thus it is in the intersection.  Transitivity of the order relation is inherited by the restriction.

We conclude that the restriction of an order relation is an order relation.