NIP $\implies$ AoC.$\newcommand{\absval}[1]{\left\lvert #1 \right\rvert}$
Exercise 2.5.4 from Understanding Analysis by Abott.
The Bolzanno-Weierstrass theorem is extremely important, and so is the strategy employed in the proof. To gain some more experience with this technique, assume that the nested interval property is true and use it provide a proof of the Axiom of Completeness. To prevent the argument from being circular, assume also that $(1/2^n) \to 0$. (Why precisely is this last argument needed to avoid circularity?)
Does my proof check out? I hope my construction is rigorous.
Proof.
Claim. Every non-empty subset of real numbers that is bounded above has a least-upper bound.
Let $A$ be a subset of $\mathbf{R}$ bounded above by $M$. Bisect the interval $[-M,M]$ into two closed intervals $[-M,0]$ and $[0,M]$. Now, it must be that atleast one of these closed intervals contains both a point $a \in A$, and an upper bound for $A$. Select the half for which this is the case and label that interval $I_1$. Let $I_1 = [a_1,b_1]$ and let $s_1$ be an upper bound for $A$.
Bisect $I_1$ into two closed intervals of equal length and let $I_2$ be a half such that it contains both - a point in $A$ and an upper bound $s_2$ for $A$. In general, we construct a closed interval $I_k = [a_k,b_k]$ by taking a half of $I_{k-1}=[a_{k-1},b_{k-1}]$, containing a point in $A$ and an upper bound $s_k$ for $A$.
The set\begin{align*} I_1 \supseteq I_2 \supseteq I_3 \supseteq \ldots \end{align*}
forms a nested sequence of intervals. Also, $s_k \le s_{k-1} \le \ldots \le s_1$, so $s_k$ is a monotonically decreasing sequence. By the nested interval property, there exists atleast one point $x \in \mathbf{R}$, contained in every $I_k$. This provides us the candidate that we are looking for. It just remains to show that the sequence $(s_n) \to x$.
Pick an $\epsilon > 0$. By construction, the length of the interval $I_k = \frac{M}{2^{k-1}}$, which converges to $0$ as $k \to \infty$ (given). Thus, there exists $N \in \mathbf{N}$ such that, if $k \ge N$, the length of the interval $I_k$ can be made as small as we like; lesser than $\epsilon$. Since, $s_k$ and $x$ are both in the interval $I_k$, it follows that\begin{align*} \absval{s_k - x} < \epsilon \end{align*}
$\endgroup$ 22 Answers
$\begingroup$There’s a problem with your argument at the very beginning: it’s possible that $A\cap[-M,M]=\varnothing$. You can avoid this problem by picking any $a_1\in A$, letting $b_1=M$, and starting with the interval $I_1=[a_1,b_1]$.
There is an even bigger problem when you choose one of the two subintervals. The righthand subinterval of $I_1$ contains the upper bound $M$ for $A$, so you could choose it to be $I_2$. Then when you bisect $I_2$, its righthand subinterval contains the upper bound $M$ for $A$, so you could choose it to be $I_3$. In this way you could end up choosing the righthand subinterval every time and getting $\bigcap_{k\ge 1}I_k=\{M\}$. And there’s no reason to think that $M$ is the least upper bound of $A$: for instance, it’s entirely possible that $A=[0,1]$ and $M=2$.
You need to make sure that you always choose a subinterval that contains points of $A$. If $L_k$ and $R_k$ are the left and right subintervals of $I_k$, let
$$I_{k+1}=\begin{cases} R_k,&\text{if }A\cap R_k\ne\varnothing\\ L_k,&\text{otherwise.} \end{cases}$$
(Why must you not choose $L_k$ when $A\cap R_k\ne\varnothing$?)
Now let $x$ be the unique point in $\bigcap_{k\ge 1}I_k$ and show that $x$ is the least upper bound of $A$. First show that it’ an upper bound for $A$, and then use the fact that $A\cap I_k\ne\varnothing$ for each $k\ge 1$ to show that it’s the limit of a sequence in $A$, so no smaller number can be an upper bound for $A$.
$\endgroup$ 3 $\begingroup$I am also working through Abbott's book and came up with this proof:
Let $A$ be a non-empty set bounded above by $b$. If A is finite, one can take the maximum element (b) of the set and such element would satisfy the conditions of a supremum. If $A$ is infinite, there are two options: a) Either $A$ is a closed interval ($A=\{x \in \mathbb{R} : x \leq b \}$), or has a single element greater than the rest ($A=\{x \in \mathbb{R} : x \leq a, \text{and} \, b \}$), in which case we can choose $b$ and get the supremum; or b) $A$ is an open interval, in which case case we would use the NIP in order to prove the existence of a supremum.
Let $A=\{x \in \mathbb{R} : x<b \}$. Now we select any point in $a \in A$, so that there are infinite elements between $a$ and $b$, and construct an interval defined as $I_{0}=[a, b]$. We continue building intervals by taking the middle point in the previous interval as the lower bound, and keeping $b$ as the upper bound of the interval. Then, $I_{0} \subset I_{1} \subset \dots$ is a sequence of closed nested intervals, where all the elements of those intervals are in $A$. By the nested interval property, the countably infinite intersection of the intervals is not empty: $\bigcap_{i=0}^{\infty}I_{i}\neq \emptyset$. Then, the element in the intersection is a supremum for the set $A$:
i) for all $x \in A$ it holds that $x \leq b$; and
ii) for all alternative least upper bounds $u$, $b \leq u$.
The argument that $1/2^{n} \rightarrow 0$ is used in i), since all the elements in the intervals belong to $A$, so that if you subtract an $\epsilon > 0$ to the supremum we just found, it will no longer be an upper bound.
$\endgroup$
