# Least upper bound proof (again)

1. Aug 18, 2011

### Syrus

1. The problem statement, all variables and given/known data

Okay, this is essentially the same question I had in an earlier thread, but i am trying to make my questions and uncertainties more clear for more accurate assistance:

Suppose R is a partial order on A and B ⊆ A. Let U be the set of all upper bounds for B.
a) Prove that every element of B is a lower bound for U.
b) Prove that if x is the greatest lower bound of U, then x is the least upper bound of B.

2. Relevant equations

My trouble is in proving part b). Also, I feel part a)- which i have proven below- is used in the part b) proof, I just can't seem to piece the two together appropriately.

3. The attempt at a solution

Here is my proof for part a)

Let b ∈ B. Let u ∈ U. Then by the definition of upper bound, (b,u) ∈ R. Since u was arbitrary, b is a lower bound of U. Since b was arbitrary, every element of B is a lower bound of U.

To prove part b) obviously you assume the antecedent of the statement to be proven. That is, x is the greatest lower bound of U. You can also assume the result obtained in part a). Now our goal is x is the least upper bound of B. Logically this translates to for all b in B, (b,x) is an element of R. Also, for all u in U, (x,u) is an element of R. So I am trying to prove these separately.

My confusion begins here:

Does the antecedent mean x is a lower bound of U AND x is the greatest element of the set of lower bounds of U (which, as far as i can come up with, is A\U)?

How do you show x is an upper bound of B? I feel this is a start to the rest of the proof.

2. Aug 18, 2011

### micromass

Staff Emeritus
So far so good.

Correct.

This is not true if you're only working with partial orders. Let A=B=[0,1] with the usual ordering and adjoin an element y that has no relationship with elements of A. Then U={1} is the only upper bound of A. But y is not a lower bound of U.

Take $b\in B$. We must prove that $b\leq x$. But b is a lower bound of U and x is the greatest lower bound.

3. Aug 18, 2011

### Syrus

I guess this was my "intuitive" understanding of the theorem. The only reason I can't seem to formalize it is that translating the antecedent into its logical form poses a problem:

Since x is the greatest lower bound of U, x is a lower bound of U AND x is the greatest element of the set of lower bounds of U. The first conjunct can be expressed by: for all u in U, (x,u) is an element of R. But for the second conjunct... for all z in (what set then?) (x,z) is an element of (what set)?

Is that making sense?

4. Aug 18, 2011

### micromass

Staff Emeritus
The second could be formalized as follows
if for all u in U it holds that (y,u) in R, then (y,x) is in R.