Archive

Archive for March 11th, 2009

1.3 Exercise 14

March 11th, 2009 No comments

Rather than merely repeating the proof of 1.3.13 to show the converse, we can impose the "opposite" or symmetric order relation on the set  A to show that if it has the GLBP then it has the LUBP too.

"If  C is a relation on a set  A , define a new relation  D on  A by letting  (b, a) \in D if  (a,b) \in C

(a) Show that  C is symmetric if and only if  C = D

(b) Show that if  C is an order relation,  D is also an order relation.

(c) Prove the converse of the theorem in Exercise 13."

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

------

SOLUTION

(a) 

 C = D \Rightarrow C \textrm{ is symmetric} .

Pick any  a, b \in A .  Suppose  (a, b) \in C : this implies  (b, a) \in D .  Since  C = D , all elements of  D are also in  C . Thus  (b, a) \in C , and  C is symmetric.  

 C \textrm{ is symmteric} \Rightarrow C = D .

Pick  a, b \in A so that  (a, b) \in C .  Also  (b, a) \in C by symmetry of  C .  Now,  (a, b) \in C \Rightarrow (b, a) \in D , and also  (b, a) \in C \Rightarrow (a, b) \in D , and  D is symmetric.  Thus, we have the implication that   (a, b) \in C \Rightarrow (a, b) \in D via its symmetric partner, and  C = D :  C \subset D because all elements of  C are in  D , and  D \setminus C is empty because we're carbon-copying the elements of  C into  D and  D was otherwise empty. 

(b)

 C \textrm{ an order relation} \Rightarrow D \textrm{ an order relation} .

Comparability.  For  a, b \in A , either  (a, b) \in C or  (b, a) \in C  \Rightarrow (b, a) \in D or  (a, b) \in D . Thus,  D inherits comparability. 

Nonreflexivity.  For all  a \in A ,  (a, a) \notin C . Since such is not in  C , it could not have been generated in  D .  Thus,  (a, a) \notin D , and  D inherits nonreflexivity.

Transitivity.  For  a, b, c \in A such that  (a, b), (b, c), (a, c) \in C , where the presence of the first two implies the presence of the third. Next, we follow the implication for generating elements in set  D :  (b, a), (c, b), (c, a) \in D .  Rearranging,  (c, b), (b, a), (c, a) \in D , and  D is transitive because the presence of the first two implied the presence of the third (via  C ).

(c) 

First of all, if part (b) holds and  C \textrm{ order relation } \Rightarrow D \textrm{ order relation} , then  C is not symmetric (since if both  (x, y), (y, x) \in C , then  (x, x) \in C by transitivity, contradicting nonreflexivity).  Then,  C not symmetric implies  C \neq D by contrapositive of part (a).  We've shown that we're talking about two different order relations.

Say  A has the LUBP  \Rightarrow GLBP, ordered as  C .  This means that for any nonempty   A_0 \subset A bounded above, the set of upper bounds,  B \subset A , has a least element, say  b , so that   b \leq x \in B and  b \geq y \in A_0 .  In particular, this means  (b, x) \in C xor  b = x for all  x \in B and  (y, b) \in C xor  y = b for all  y \in A_0 . Additionally, since the LUBP implies the GLBP, for any nonempty set  A_1 \subset A bounded below, the set of lower bounds,  B' \subset A , has a greatest element,  b' \geq x' \in B' , and  b' \leq y' \in A_1 . This means  (x', b') \in C xor  x' = b' for all  x' \in B' and  (b', y') \in C xor  y' = b' for all  y' \in A_1 .

Now impose on  A , instead of  C , the order relation  D which is different. Following the implication for generating elements in this new order relation,   (x, b) \in D xor  x = b , for all  x \in B and  (b, y) \in D xor  b = y for all  y \in A_0 . Thus,  b is a greatest lower bound.  Also,  (b', x') \in D xor  b' = x' for all  x' \in B' , and  (y', b') \in D xor  b' = y' for all  y' \in A_1 .  Thus  b' is a least upper bound.  Hence, if the set  A has the GLBP, it has the LUBP, as we wanted to show.