### Archive

Archive for March, 2009

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

Categories:

## 1.3 Exercise 13

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.

Categories: