Proof of Axiom of Completeness: Bisecting Intervals to Find LUB

In summary: So my algorithm should be to choose the interval that has the smallest length.The algorithm should be to choose the interval that has the smallest length.
  • #1
cragar
2,552
3

Homework Statement


Assume the nested Interval property it true and use a technique similar to the one used to prove the Bolzano Weierstrass theorem, to give a proof of the axiom of completeness.
axiom of completeness: Every non-empty set of reals that is bounded above has a least upper bound.

The Attempt at a Solution


Suppose we knew of an upper bound for our set. and another point in our set. Now we bisect this interval. Now when we bisect this interval we could get an interval which only consisted of points in the set or get an interval that had some points in the set and some that aren't in the set. We will pick the interval that has some points in the set and some that are not. So we keep doing this forever and eventually we will chisel it down to a unique point and this will be the least upper bound. Is this the right approach?
 
Physics news on Phys.org
  • #2
cragar said:

Homework Statement


Assume the nested Interval property it true and use a technique similar to the one used to prove the Bolzano Weierstrass theorem, to give a proof of the axiom of completeness.
axiom of completeness: Every non-empty set of reals that is bounded above has a least upper bound.

The Attempt at a Solution


Suppose we knew of an upper bound for our set. and another point in our set. Now we bisect this interval. Now when we bisect this interval we could get an interval which only consisted of points in the set or get an interval that had some points in the set and some that aren't in the set. We will pick the interval that has some points in the set and some that are not.
The idea seems fine, but this step is unclear. Suppose the set is [a,b], and I choose the upper bound b, and the other point in the set is a. Bisect the interval [a,b]. Both subintervals contain only points from [a,b]. So your algorithm for picking the next interval doesn't work in this case.
 
  • #3
You can avoid the problem I mentioned as follows.

Choose an upper bound M. If the upper bound is in the set, then we're done: M is the supremum (indeed, the maximum) of the set.

Otherwise, M is not in the set. Choose a second point that is in the set, and continue as you argued. However, be careful - there are actually three possibilities for each subinterval I:

1) I contains only points in the set
2) I contains only points NOT in the set
3) I contains both points in the set and points not in the set.

For example, if the set is [0,1] and I choose an upper bound M = 2 and the point in the set is 1. Subdivide [1,2] and you get [1,3/2] and [3/2, 2]. The first is of type (3) and the second is of type (2).

You should be able to argue pretty easily that after any bisection, at least one of the two subintervals will be of type (3).
 
Last edited:
  • #4
To prove that the common point to all the sub intervals is the supremum, Could I do a proof by contradiction and assume that the point common to all of them was bigger than the sup, this would imply that is was not in the set and that we would had to have picked an interval that had no points in the set when we were bisecting the intervals. Then we would assume that the common point was less than the sup, this would imply that we picked an interval that had all of its points in the set which contradicts how we picked our intervals.
 
  • #5
cragar said:
To prove that the common point to all the sub intervals is the supremum, Could I do a proof by contradiction and assume that the point common to all of them was bigger than the sup, this would imply that is was not in the set and that we would had to have picked an interval that had no points in the set when we were bisecting the intervals. Then we would assume that the common point was less than the sup, this would imply that we picked an interval that had all of its points in the set which contradicts how we picked our intervals.

Certainly worth trying. If you write out the details here I'll be happy to check your logic.

So did you decide exactly what your algorithm is for choosing one of the two subintervals resulting from each bijection?
 
  • #6
ok so if M is an upper bound and c is a point inside the set then the length of this will
be (M-c) and now I will cut this interval in half so the length of my intervals
should be [itex] \frac{M-c}{2^k} [/itex] Now when I bisect the interval we want to pick one of the intervals. At my bisection point if I look just to the right of it and there are no elements in the set, then I will want to the left one. And If at my bisection point if there are element just to the left then I will want to pick the right one. If there are elements to the left and none to the right then I am on the sup for that set. After we have done an infinite number of bisections we should have enclosed one point and we need to show that this point is the sup of the set. Suppose the point that was common to all these sub intervals was greater than the sup of the set. This would imply that I could make an epsilon neighborhood around this point and have no elements in the set around his point, but this would imply That I picked an interval that had no points in the set. Assume that the point common to these interval was less than the sup of the set. This would imply that I could make an epsilon neighborhood around this point and I would have elements on both sides of the point but this would contradict how i picked my intervals because for this to happen I would have had to pick and interval that was a solid line.
 
  • #7
cragar said:
ok so if M is an upper bound and c is a point inside the set then the length of this will
be (M-c) and now I will cut this interval in half so the length of my intervals
should be [itex] \frac{M-c}{2^k} [/itex] Now when I bisect the interval we want to pick one of the intervals. At my bisection point if I look just to the right of it and there are no elements in the set, then I will want to the left one. And If at my bisection point if there are element just to the left then I will want to pick the right one. If there are elements to the left and none to the right then I am on the sup for that set.

This doesn't seem to handle the case in which there are elements of the set in both the left and right halves.

Also, don't these two sentences conflict?

"At my bisection point if I look just to the right of it and there are no elements in the set, then I will want to the left one. And If at my bisection point if there are element just to the left then I will want to pick the right one."

It seems to me that you want the following rule:

"If the right interval contains no points of the set, then choose the left interval. Otherwise choose the right interval."

This guarantees the following two things:

1. The interval you choose will always contain at least one point of the set.
2. There are no elements of the set to the right of the interval you choose.

Then your argument should work. Does that make sense?
 
  • #8
yes that makes sense, now I probably need to put in more variables and make it a little more precise.
 

Related to Proof of Axiom of Completeness: Bisecting Intervals to Find LUB

1. What is the Axiom of Completeness?

The Axiom of Completeness, also known as the Least Upper Bound Property, states that every non-empty set of real numbers that is bounded above has a least upper bound (LUB).

2. Why is the Axiom of Completeness important?

The Axiom of Completeness is important because it allows us to prove the existence of real numbers and provides a foundation for the concept of infinity. It also allows us to make precise mathematical statements and proofs.

3. How do we prove the Axiom of Completeness using bisecting intervals?

To prove the Axiom of Completeness, we use a method called bisecting intervals. This involves dividing an interval in half and determining which half contains the LUB. This process is repeated until the LUB is narrowed down to a specific value.

4. What is the role of LUB in the Axiom of Completeness?

The LUB is a crucial component of the Axiom of Completeness as it represents the smallest possible upper bound for a set of real numbers. It ensures that the set has a well-defined limit and allows us to make precise mathematical statements about the set.

5. Can the Axiom of Completeness be applied to sets of complex numbers?

No, the Axiom of Completeness only applies to sets of real numbers. Complex numbers do not have a natural ordering that is required for the concept of LUB to be defined.

Similar threads

  • Calculus and Beyond Homework Help
Replies
25
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
4K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
Replies
5
Views
3K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
2K
  • Calculus and Beyond Homework Help
Replies
15
Views
11K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
Back
Top