13

This is second attempt of me to prove:

The Nested Interval Property implies the Axiom of Completeness of the real numbers.

Nested interval property: If $I_1 \supseteq I_2 \supseteq I_3 \dots$ are closed intervals then $\bigcap_n I_n$ is not empty.

Axiom of completeness: If $S$ is a non-empty set in $\mathbb R$ that has an upper bound then $S$ has a least upper bound.

A first attempt is here.

Please can you check my proof again?

Proof: Let $K$ be an upper bound of $S$. Pick $s \in S$. Let $I_1 = [s,K]$. If $K$ is not the least upper bound there is a smaller upper bound $K_2$. Let $I_2 = [s,K_2]$. And so on. If no $K_n$ is a least upper bound for $S$ then because of nested interval property the intersection $I=\bigcap_n I_n$ is non-empty. Also, it is closed. Then the maximum $M$ of $I$ is a least upper bound of $S$: For all $K_n$ it holds that all $s \in S$ are $\le K_n$. The $M$ is the limit of the sequence $K_n$ therefore also $s \le M$ for every $s$. Also $M$ is the least upper bound because if it is not the least upper bound then by the construction $K_n = M$ for some $n$ and there is a smaller upper bound $K_{n+1}$. Then $M \notin \bigcap_n I_n$ which contradicts that $M$ is the maximum in the closed set $\bigcap_n I_n$.

Community
  • 1
blue
  • 2,884

3 Answers3

17

You need to make the gap between the upper bounds and $S$ shrink to $0$.

HINT: Given $s_n\in S$ and an upper bound $K_n$ of $S$, let $x_n=\frac12(s_n+K_n)$. If $x_n$ is an upper bound for $S$, let $s_{n+1}=s_n$ and $K_{n+1}=x_n$. If not, choose $s_{n+1}\in[x_n,K_n]$, and let $K_{n+1}=K_n$. Now consider the intervals $I_n=[s_n,K_n]$.

Brian M. Scott
  • 616,228
  • 1
    To finish the proof do I have to proof the two things: that $\bigcap_n I_n$ contains exactly one point and that this point is a least upper bound? – blue Dec 19 '13 at 07:23
  • @blue: Yes; for the first you can show that $\lim_{n\to\infty}(K_n-s_n)=0$. – Brian M. Scott Dec 19 '13 at 07:31
  • Thank you!! I appreciate your help! – blue Dec 19 '13 at 07:34
  • @blue: You’re welcome! – Brian M. Scott Dec 19 '13 at 07:38
  • 1
    Now, I could finally finish the proof: Let $K$ be an upper bound of $S$ and $s \in S$. Let $a_1 = s, b_1= K$ and $x_1 = {a_1 + b_1 \over 2}$. If $x_1$ is an upper bound of $S$ let $a_2 = a_1$ and $b_2 = x$ otherwise let $a_2=x$ and $b_2=K$. Let $I_n = [a_n,b_n]$. Then $I_n$ is a sequence of closed nested intervals hence by the nested interval property $\bigcap_n I_n$ is non-empty. Furthermore it contains exactly one point since the length of $I_n$ tends to $0$ (the lengths are strictly decreasing since $|I_{n+1}| = {|I_n| \over 2}$). – blue Dec 19 '13 at 08:22
  • This point, $x$, is an upper bound of $S$ since if there was any element $s \in S$ with $x < s$ then by construction $x \notin I_n$ for all $n$ greater some $N$. It is the least upper bound since if there was an upper bound $b < x$ then again $x$ would lie outside $I_n$ for all $n$ greater some $N$ by construction. – blue Dec 19 '13 at 08:23
  • @blue: You should give the general rule for constructing $a_{n+1}$ and $b_{n+1}$ from $a_n$ and $b_n$ instead of making the reader infer it from the construction of $a_2$ and $b_2$ from $a_1$ and $b_1$. The last bit isn’t quite right. Once you have $x$, if $x<s$ for some $s\in S$, then there is an $n$ such that $b_n<s$, which is impossible, since $b_n$ is an upper bound for $S$. Similarly, if you had an upper bound $b<x$, there would be an $n$ such that $a_n>b$, which is again impossible. – Brian M. Scott Dec 19 '13 at 08:36
  • For the first part, do you mean like this: Let $K$ be an upper bound of $S$ and $s \in S$. Let $a_1 = s, b_1= K$ and $x_1 = {a_1 + b_1 \over 2}$. If $x_1$ is an upper bound of $S$ let $a_2 = a_1$ and $b_2 = x$ otherwise let $a_2=x$ and $b_2=K$. Let $I_1 = [a_1,b_1]$. Assume $a_k, b_k$ have been constructed for all $k < n$. Construct $a_n,b_n$ as follows: Let $x = {a_{n-1} + b_{n-1} \over 2}$. If $x$ is an upper bound of $S$ let $a_n = a_{n-1}$ and $b_n = x$ otherwise let $a_n = x$ and $b_n = b_{n-1}$. Let $I_n = [a_n, b_n]$. – blue Dec 19 '13 at 09:01
  • @blue: Yes, exactly. – Brian M. Scott Dec 19 '13 at 09:16
  • And for last part I now do: This point, $x$, is an upper bound of $S$ since if there was any element $s \in S$ with $x < s$ there would be $n$ with $x \le b_n < s$ which would be a contradiction since $b_n$ is an upper bound of $S$ for every $n$. It is the least upper bound since if there was an upper bound $b < x$ then there would be $n$ with $b < a_n$ which would again be a contradiction since $a_n \in S$ for all $n$. – blue Dec 19 '13 at 09:31
  • @blue: You’ve got it. – Brian M. Scott Dec 19 '13 at 09:32
  • 2
    @BrianM.Scott : Is it possible to choose an $n$ large enough to get the contradictions in the last step without the Archimedean Property? – David Jul 10 '16 at 14:19
  • @BrianM.Scott Just one query in general: how did you assert that all $b_n's$ are upper bound ? It might be so, that the $b_n$ is just not an element of $S$ but not an upper bound? – Thomas Finley Jun 21 '23 at 13:02
  • @ThomasFinley: By definition each $b_n$ is an upper bound of $S$: that’s built into their construction. – Brian M. Scott Jun 21 '23 at 19:23
9

Actually Nested Interval Theorem implies Completeness Axiom, only if you assume that Archimedean Property holds. Under this hypothesis, as Brian M. Scott mentioned earlier, you can make the gap between the upper bounds and S shrink to 0.

Completeness Axiom implies both Archimedean Property and Nested Interval Theorem!!!! Though in Non-Archimedean Ordered Fields (like the field of Rational Polynomials) the Nested Interval Property ALONE does not entails Completeness Axiom

So in a general setting, Completeness Axiom is equivalent to Nested Interval Property+Archimedean Property

chailos.g
  • 91
  • 1
    I'm a little confused where the Archimedean property comes in. Abbott mentioned we need to assume that $(1/2^n) -> 0$ . I assume it comes in there, but I don't see it. I also don't see where it is used in the comment by blue above. Sorry for asking if the answer is obvious. – dylan7 Jul 29 '18 at 16:53
  • 1
    @dylan7 To say that (1/2^n) --> 0, we first note that 1/2^n < 1/n. What we want is that (1/2^n) gets arbitrarily close to 0 whenever n >= N i.e. 1/n <= 1/N. This implies 1/2^n <= 1/N. We want some epsilon > 0 such that 1/N < epsilon. The existence of such N and epsilon is guaranteed by Archimedean Property. Recall: For a given real number x, there exists a natural number n such that 1/n < x. I hope this helps :) – Aditya Kulkarni Jun 19 '20 at 03:41
3

It's not valid in its current state: All you can conclude is that $M$ is an upper bound for $S$. What happens, say, if we choose $S = [0, 1]$ and a sequence

$$K_n = 2 + \frac 1 n$$

If our initial choice of $s$ is $0$, then our intervals are $$I_n = \left[0, 2 + \frac 1 n\right] \implies \bigcap_n I_n = [0, 2]$$

So $M = 2$.

The gap starts in the line beginning "Also $M$ is the ...."