Greatest upper bound analysis proof

In summary: From the definition of least upper bound, if there exists some element in the set of lower bounds, call this b, such that |supB-b|<d, then b>a. But then b is supposed to be a lower bound of A, meaning it would be greater than a. So supB is greater than a, which is a contradiction.
  • #1
dancergirlie
200
0

Homework Statement


Use the completeness axiom to prove that to prove that every non-empty subset of real numbers, which is bounded below, has a greatest lower bound.


Homework Equations


N/A


The Attempt at a Solution


Assume A is a nonempty subset of real numbers which is bounded below. Define B as the set of of lower bounds for A, meaning for all b in B, b is less than or equal to all a in A. Since every element in A is greater than every element in B, A is the set of upper bounds for B. According to the completeness axiom, every non-empty set of real numbers that is bounded above has a least upper bound, which would mean that the B is bounded above and SupB is an element in A.

**This is where i get stuck. I need to show that the SupB=InfA, which would mean that the element is in both sets**

Any help/tips would be greatly appreciated :)
 
Physics news on Phys.org
  • #2
I think that B being the set of lower bounds for A implies that any [tex]b\in B\le a\in A[/tex] and so [tex]sup(B)\le inf(A)[/tex]. If sup(B) is an element in A as you said, then [tex]inf(A)\le sup(B) [/tex] hence they are equal from:

[tex]inf(A) \le sup(B)[/tex]

[tex]sup(B) \le inf(A)[/tex]
 
Last edited:
  • #3
I don't understand how you got that sup(B) is less than or equal to inf(A)? Just because something is the least upper bound, does not necessarily mean that it is in the set that it is bounding.
 
  • #4
First, supB is not necessarily an element of A, for example if A=(0,1) then supB=0

We want to show SupB is the greatest lower bound of A. What does that mean. Ok, by that we mean given any a in A, supB is less than or equal to a. Furthermore, for any e>0, there exists a in A such that |supB-a|<e. The first condition shows that supB is a lower bound, and the second condition that you can have no greater lower bound (since if K is a proposed lower bound and K-supB>0, pick e=(K-supB)/2

Suppose there exists a in A less than supB. Then by definition of least upper bound: let d=|supB-a|/2. There exists some element in the set of lower bounds, call this b, such that |supB-b|<d. But then b>a. b is supposed to be a lower bound of A, so this is a contradiction. supB is in fact a lower bound of A.

Now try the second part on your own
 
  • #5
I'm confused, wouldn't you say for any e>0, there exists a b in B such that |supB-b| <e?
 
  • #6
That's what you need to prove supB is in fact the least upper bound of B. But we're assuming it is (since we have the completeness axiom, and that's the definition of sup). To show supB is the greatest lower bound of A, you have to show that elements of A are arbitrarily close to supB.
 
  • #7
I think I may be getting confused by your wording, but I'm not exactly sure what you are saying. Are you trying to say we are proving that SupB is the least upper bound of A by assuming that it is NOT the least upper bound? I thought by the axiom of completeness, it is assumed that supB is the least upper bound of A.

I understand what you are saying about needing to show it is arbitrarily close, but I just don't understand what you are using for your proof by contradiction...
 
  • #8
We have supB is the least upper bound of B. Now we want to prove it is also the greatest lower bound of A. You do that in two steps:
1) Show it's a lower bound of A.
2) Show there is no larger lower bound of A.

The way you do part 1 I demonstrated in my post, using the property that supB is the least upper bound of B. Now you have to do part 2... I gave one way to start that part, but of course you can use any method you think of
 
  • #9
Ok, this makes a lot more sense now (sorry I'm really tired and a bit frustrated by this proof :/ thanks for being patient with me). This is what i got so far and where i get lost:
Claim: SupB is the greatest lower bound of A
*proof by contradiction*
Assume supB is not a lower bound of A. Meaning, there exists an a in A so that a is less than supB. Since supB is the least upper bound of B, it follows that for every e>0, there exists a b in B so that supB-b>e

*now I don't understand the whole d=|supB-a|/2 part... where did you get that from??
 
  • #10
Since supB is the least upper bound of B, it follows that for every e>0, there exists a b in B so that supB-b>e

This is just a statement regarding properties of the least upper bound.

I realized I might be complicating things... what's your classes definition for greatest lower bound?
 
  • #11
We never had a formal definition for it, however the book says it is similar to the definition for the least upper bound, so I'm guessing this would be it:
A real number s is the greatest lower bound for a set A contained in R if it meets the following two criteria:
1) s is an lower bound for A
2) if b is any lower bound for A then s is greater than or equal to b.

It really isn't saying much though.
 
  • #12
Ok I think I understand the first part without using all the e's and d's and such. Let me know if this is a reasonable way to prove it.
Claim: Sup(B) is the greatest lower bound of A
*proof by contradiction*
1) assume B is not a lower bound of A, meaning there exists an a in A so that a is less than the Sup(B).
Since the Sup(B) is the least upper bound of B, that means that if a in A is an upper bound of B, then:
sup(B) is less than or equal to a. Which is a contradiction, because we previously stated that in order for SupB not to be a lower bound for A, that there must be an a in A so that a is less than SupB.
Therefore, SupB is a lower bound of A.
 
  • #13
that means that if a in A is an upper bound of B, then:
sup(B) is less than or equal to a.

It looks good, except you probably want to justify why a is an upper bound of B.
 
  • #14
Alright, now that I understand the first part, how would I go about doing the second part. I'm guessing this is the part where I need to start using the error estimates. So If SupB is a lower bound of A that means for all e>0 there exists an a in A so that |SupB-a|<e. But wouldn't this also mean for all e>0, there exists a b in B so that |supB-b|<e as well?
 
  • #15
Nevermind, I found another way to prove that it is the greatest lower bound by making a similar argument to the one I used for proving that SupB is a lower bound. Thank you so much for your help, I understand it a lot better now!
 

What is a greatest upper bound analysis proof?

A greatest upper bound analysis proof is a mathematical technique used to determine the upper bound or maximum value of a given set of numbers or functions. It is commonly used in computer science and engineering to analyze the efficiency and performance of algorithms and data structures.

How is a greatest upper bound analysis proof performed?

The proof typically involves using mathematical principles such as induction, contradiction, and limit theorems to establish the upper bound. It may also involve the use of complex mathematical formulas and equations to derive the proof.

What is the significance of a greatest upper bound analysis proof?

By determining the upper bound of a set of numbers or functions, we can understand the maximum performance or efficiency that can be achieved. This is crucial in optimizing algorithms and data structures for various applications.

What are the limitations of a greatest upper bound analysis proof?

One limitation is that it only provides an upper bound and not the exact value. It also assumes that the input data is random and does not take into account worst-case scenarios. In addition, the proof may become more complex for more complex algorithms and functions.

How is a greatest upper bound analysis proof useful in real-world applications?

This type of analysis is commonly used in computer science and engineering to optimize algorithms and data structures for various applications such as data processing, network routing, and resource management. It helps in identifying the maximum performance that can be achieved and improving the overall efficiency of the system.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
881
  • Calculus and Beyond Homework Help
Replies
4
Views
463
  • Calculus and Beyond Homework Help
Replies
1
Views
458
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
25
Views
2K
  • Calculus and Beyond Homework Help
Replies
33
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
17
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
2K
Back
Top