Least upper bound/ greatest lower bound proof


by Syrus
Tags: bound, bound or, greatest, proof, upper
Syrus
Syrus is offline
#1
Aug16-11, 11:25 PM
P: 202
1. The problem statement, all variables and given/known data
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

3. The attempt at a solution
I have proven a)

Let b ∈ B. Let u ∈ U. Then by the definition of upper bound, (b,u) ∈ R.


For the proof of b), you obviously assume the antecedent of the statement to be shown. I can't, however, seem to make out the logical form of this. Also, it appears you must use part a) in the proof of part b) as well. I have an intuitive understanding of the idea of the statement to be proven, I am just having a hard time (in-)formalizing it.

The logical form of the goal- i would think- is (∀b ∈ B)((b,x) ∈ R) and (∀u ∈ U)((x,u) ∈ R); I assume this means that x is an upper bound of B AND that x is the least upper bound of B (hence, x is the least upper bound of B).

So naturally, my proof thus far is:
Suppose x is the greatest lower bound of U. Let b ∈ B....
Phys.Org News Partner Science news on Phys.org
Going nuts? Turkey looks to pistachios to heat new eco-city
Space-tested fluid flow concept advances infectious disease diagnoses
SpaceX launches supplies to space station (Update)
AdrianZ
AdrianZ is offline
#2
Aug17-11, 02:30 AM
P: 320
Quote Quote by Syrus View Post
1. The problem statement, all variables and given/known data
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

3. The attempt at a solution
I have proven a)

Let b ∈ B. Let u ∈ U. Then by the definition of upper bound, (b,u) ∈ R.


For the proof of b), you obviously assume the antecedent of the statement to be shown. I can't, however, seem to make out the logical form of this. Also, it appears you must use part a) in the proof of part b) as well. I have an intuitive understanding of the idea of the statement to be proven, I am just having a hard time (in-)formalizing it.

The logical form of the goal- i would think- is (∀b ∈ B)((b,x) ∈ R) and (∀u ∈ U)((x,u) ∈ R); I assume this means that x is an upper bound of B AND that x is the least upper bound of B (hence, x is the least upper bound of B).

So naturally, my proof thus far is:
Suppose x is the greatest lower bound of U. Let b ∈ B....
You've proven the part a rightly but It's not complete I guess. to prove a, remember that U is the set of all upper bounds of B which means for any b in B we have: (b,u)∈R (u in U). now let u be any element of U and fix b. that means u is bounded by an element of b. now let b vary, that means every element of B is a lower bound for you and that means B is the set of lower bounds of U.

to prove the part b, It's easy to show if x is the glb of U then x is an upper bound of B. what you need to prove is that x is also the least upper bound. that means there exists no other element like y s.t y is an upper bound of B and (y,x)∈R. It's easy to show that, I leave the proof to you. prove it by reductio ad absurdum (indirect argument).
Syrus
Syrus is offline
#3
Aug17-11, 09:50 AM
P: 202
Coulnd't there also be lower bounds which are not in B? Part of my trouble is specifying a set containing a lower bound of U, since b need not be in B.

AdrianZ
AdrianZ is offline
#4
Aug17-11, 10:16 AM
P: 320

Least upper bound/ greatest lower bound proof


Quote Quote by Syrus View Post
Coulnd't there also be lower bounds which are not in B? Part of my trouble is specifying a set containing a lower bound of U, since b need not be in B.
Maybe there are lower bounds of U that are not in B. I guess that might happen when B is left-bounded and I'm not 100% sure about that. but in our case, that doesn't matter. because if m is a lower bound for U that is not in B and we have: [itex]\forall[/itex]b[itex]\forall[/itex]u: b<l<u then that leads us to a contradiction. that's all we need to know to prove that glb(U)=lub(B). I don't think we need anything else to prove the problem.
Syrus
Syrus is offline
#5
Aug17-11, 11:32 AM
P: 202
Quote Quote by AdrianZ View Post
You've proven the part a rightly but It's not complete I guess. to prove a, remember that U is the set of all upper bounds of B which means for any b in B we have: (b,u)∈R (u in U). now let u be any element of U and fix b. that means u is bounded by an element of b. now let b vary, that means every element of B is a lower bound for you and that means B is the set of lower bounds of U.
But then B is not "the set of lower bounds of U" rather, A set of lower bounds of U.

Another thing... i am struggling with how to show that x is an upper bound of B... Even though x is the glb of U doesn't necesserily mean it is an element of U. Still somewhat confused i guess.


Register to reply

Related Discussions
Upper bound and lower bound Calculus & Beyond Homework 1
How do we find the least upper bound and greatest lower bound? Calculus & Beyond Homework 2
Greatest upper bound analysis proof Calculus & Beyond Homework 14
Upper bound/Lower Bound Set Theory, Logic, Probability, Statistics 10
max, min, least upper, and greatest lower bound for sets question Calculus 14