Proof of Axiom of Completeness: Bisecting Intervals to Find LUB

[cragar]

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?

 

[jbunniii]

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.

 

[jbunniii]

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).

 

[cragar]

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.

 

[jbunniii]

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?

 

[cragar]

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 $\frac{M-c}{2^k}$ 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.

 

[jbunniii]

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 $\frac{M-c}{2^k}$ 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?

 

[cragar]

yes that makes sense, now I probably need to put in more variables and make it a little more precise.