1.3 Exercise 14

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.

  1. No comments yet.
  1. No trackbacks yet.

*