Archive

Posts Tagged ‘Relations’

1.3 Exercise 15

June 18th, 2009 No comments

Yes, after months, I'm back ;-).  This was an interesting problem to me because it explores a bit more deeply the concept of the LUBP.

"Assume that the real line has the least upper bound property.

(a) Show that the sets  [0,1] = \{x \ \vert \ 0 \leq x \leq 1\} and  [0,1) = \{x \ \vert \ 0 \leq x < 1\} have the least upper bound property.

(b) Does  [0, 1] \times [0, 1] in the dictionary order have the least upper bound property?  What about  [0,1] \times [0, 1) ?  What about  [0,1) \times [0,1] ?"

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

-------

SOLUTION

(a)

Pick any nonempty  A_0 \subset [0,1] , bounded above in  [0,1] .  Note that  A_0 \subset [0,1] \subset \mathbb{R} , and so  A_0 \subset \mathbb{R} , by transitivity of inclusion (a partial order axiom).  Since  \mathbb{R} has the LUBP (by assumption), the set of upper bounds of  A_0 (in  \mathbb{R} ), say  [b, \infty) , has a least upper bound, namely  b .   Restricted to  A = [0,1] , the upper bounds are  [b, \infty) \cap [0, 1] = [b, 1] , and  b is still the LUB in  A .  It follows that all nonempty subsets that are bounded above in  A have a least upper bound in  A , and  A has the LUBP.  Following the exact same recipe works with all nonempty subsets of  A' = [0,1) that are bounded above.  As a point of clarification, notice that the set  A_0' = A' = [0, 1) is not bounded above in  A' , and so it is not an impediment to the base set  A' having the LUBP.

(b)

Yes,   [0, 1] \times [0, 1] in the dictionary order have the least upper bound property.  Pick any nonempty subset of  A = [0, 1] \times [0, 1] that is bounded above, as the interval  (x_1 \times y_1, x_2 \times y_2) ,  [x_1 \times y_1, x_2 \times y_2) ,  (x_1 \times y_1, x_2 \times y_2] , xor  [x_1 \times y_1, x_2 \times y_2] with  x, y \in [0,1] of course.  For all these, the set of upper bounds are  [x_2 \times y_2, 1 \times 1] , and the LUB is  x_2 \times y_2 .

No,  [0,1] \times [0, 1) does not have the LUBP (in the dictionary order).  We need only show a counterexample: take the interval   (x_1\times y_1, x_1 \times 1) (nonempty, bounded above) with  x \in [0, 1] and  y \in [0, 1) .  The set of upper bounds is  (x_1 \times 0, 1 \times 1) , and this clearly has no smallest element.  In other words, by picking the smallest upper bound one could think of, say  x_2 \times 0 , the idea is that one can always come up with a (strictly) smaller one, say  \frac{x_2}{2} \times 0 .

Yes,  [0,1) \times [0,1] has the LUBP (in the dictionary order).  Pick any nonempty subset of  A = [0, 1) \times [0, 1] that is bounded above, as the interval  (x_1 \times y_1, x_2 \times y_2) ,  [x_1 \times y_1, x_2 \times y_2) ,  (x_1 \times y_1, x_2 \times y_2] , xor  [x_1 \times y_1, x_2 \times y_2] with  x \in [0, 1) and  y \in [0, 1] .  For all these,  x_2 \times y_2 is the LUB, since it's included in the upper bound set and it is its least element.

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.

1.3 Exercise 13

March 2nd, 2009 No comments

This theorem (and its converse) is needed everywhere in analysis and topology, and it is very important.

"Prove the following: 

Theorem.  If an ordered set  A has the least upper bound property, then it has the greatest lower bound property."

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

-----

SOLUTION

Suppose that  A does not have the GLBP. This means that there exists a nonempty  A_0 \in A that is bounded below but does not have a greatest lower bound, so that the set of lower bounds  B_l \in A (nonempty) does not have a largest element.  Additionally,  A_0 does not have a smallest element, for, if it did, this would in fact be its infimum (such an element would be in the set of lower bounds because it is lesser or equal to all elements of  A_0 ).  Next let's focus on  B_l , which is a set in  A as well.  It cannot possibly have the LUBP, because it has no greatest element and because  A_0 , which now bounds it above, has no smallest element. We found a nonempty subset of  A with no supremum, and we've proved the theorem by contrapositive.

1.3 Exercise 12

February 27th, 2009 No comments

This problem, although cool because it exposes us to out-of-the-ordinary order relations on the Cartesian plane, was a little long, I felt.  Nevertheless, it shows that we can create order relations with smallest elements, with elements with no immediate predecessors, and with no smallest elements, and any happy combination as well.

"Let  \mathbb Z_+ denote the set of positive integers.  Consider the following order relations on  \mathbb Z_+ \times \mathbb Z_+ :

(i) The dictionary order.

(ii)  (x_0,y_0) < (x_1, y_1) if either  x_0 - y_0 < x_1 - y_1 , or  x_0 - y_0 = x_1 - y_1 and  y_0 < y_1 .

(iii)  (x_0,y_0) < (x_1, y_1) if either  x_0 + y_0 < x_1 + y_1 , or  x_0 + y_0 = x_1 + y_1 and  y_0 < y_1

In these order relations, which elements have immediate predecessors?  Does the set have a smallest element?  Show that all three order types are different." 

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

------

SOLUTION  

In this problem, I found it very helpful to write out the order sequence for the three cases, or even try to picture each on the Cartesian plane  \mathbb{Z}_+ \times \mathbb{Z}_+ .  Thus, for the dictionary order: 

13121

Having done so, it is a lot easier to see that the elements that do not have immediate predecessors are of the form  (j, 1) . For, choose any element in column  j-1 as a candidate,  (j-1, k) .  The problem is that the set  \{(x, y) \verb| | \vert \verb| | (j-1, k) < (x, y) < (j, 1)\} is nonempty because the element  (j-1, k+1) is in it.  The tricky part may be the element   (1, 1) .  This element has no immediate predecessor because it is the smallest element (since it is less than any other element and equal to itself).

For the order of (ii), the order sequence looks like:

13122

where  C = j-1 and  D = 1-k are constants determined by the choice of  j or  k .  Elements with no immediate predecessors are  (j, 1) and  (1, k) .  In the first case, candidates to be the immediate predecessor of  (j, 1) are  ((j+1)+m, (j+1)+m-C) , but then set  \{(x, y) \verb| | \vert \verb| | ((j+1)+m, (j+1)+m-C) < (x, y) < (j, 1)\} is never empty, because the element  ((j+1) + (m + 1), (j+1)+(m+1)-C) is in it.   Next for  (k, 1) , candidates to be the immediate predecessor are of form  ((k-1) + n + D, (k-1) + n) , but then again the set  \{(x, y) \verb| | \vert \verb| | ((k-1)+n+D, (k-1)+n) < (x, y) < (1, k)\} is never empty, because the element  ((k-1) + (n+1)+D, (k-1)+(n+1)) is in it.  

It is quite clear that there is no smallest element: for every element of form  (j, 1) and  (1, k) we can find a smaller element, as we've seen, and any other element  (j+m, j+m - C) a smaller element is  (j+(m-1), j+(m-1)-C) .  Similarly, for any element  (k+n+D, k+n) , a smaller element is  (k+(n-1)+D, k+(n-1)) .

Finally, for (iii):

13123

with  C = j+1 .  Here,  (1, 1) is clearly the smallest element (it is less than every other element and equal to itself).  Furthermore, every element except the smallest has an immediate predecessor.

All of these order relations are of different order type.  First we show that there is no order preserving bijection from  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_{ii} to  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_i or  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_{iii} .  For, suppose there is.  Then there exists an element  (j, 1) ,  (k, 1) ,  (j+m, j+m-C) , or  (k+n+D, k+n) ordered by  <_{ii} that maps to the smallest element of  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_i or  <_{iii} .  The problem is that, as we've seen, for each of these we can find a smaller element, where we cannot find a smaller element for the smallest element of  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_i or  <_{iii} .  Next we show that there cannot exist a bijection from  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_i to  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_{iii} . Suppose there is.  An element  (j, 1) , having no immediate predecessors under  <_{i} , would have to map to the only element that does not have immediate predecessors under  <_{iii} , the smallest element.  But then there are elements  (j-1, k) that are less than  (j, k) that would be undefined under such a map, so the map is not bijective.

Thus, the three order relations are different order type.

1.3 Exercise 11

February 20th, 2009 No comments

"Show that an element in an ordered set has at most one immediate successor and at most one immediate predecessor.  Show that a subset of an ordered set has at most one smallest element and at most one largest element."   

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

-------

SOLUTION 

The element  a \in A ordered can have no more than one immediate successor, for, suppose there were. This means that  (a, b) and  (a, b') are both empty. Also,  a < b and  a < b' by definition and because the set is ordered.  In particular, however, either  b < b' xor  b' < b because the set is ordered. Suppose  b < b' .  Taking into account all the conditions,  a < b < b' and  (a, b') is nonempty, a contradiction.  Next suppose  b' < b .  Again, the conditions suggest  a < b' < b , and  (a, b) is nonempty, another contradiction.

We argue that an ordered set can have at most one immediate predecessor analogously.

To show that a subset of an ordered set has at most one smallest element, we argue again by contradiction.  Suppose otherwise, so that  a \in A_0 \subset A , an ordered set, and also  a' \in A_0 are smallest elements.  In particular, this means  a \leq x \verb| | \forall x \in A_0 , but also  a' \leq x \verb| | \forall x \in A_0 .  Since the set is ordered, however, either  a < a' xor  a' < a .  Suppose it is the first case, but then  a' is not less than all elements in  A_0 , because  a belongs to it.  It cannot be a smallest element too.  Suppose it is the second case, but then again  a is not less than all elements in  A_0 , because  a' belongs to it.  It cannot be a smallest element too.

We argue the fact that an ordered set has at most one largest element analogously.