Register to reply

Least upper bound/ greatest lower bound proof

by Syrus
Tags: bound, bound or, greatest, proof, upper
Share this thread:
Syrus
#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
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
AdrianZ
#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
#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
#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
#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