# How can you prove the Nested Interval(s) Theorem in $\mathbb R$ without reference to the least upper bound property?

Claim: a nested sequence of closed bounded intervals in $\mathbb R$ has nonempty intersection.

A textbook provides a proof using the least upper bound property of the real numbers, but adds an aside that the theorem can be proved in $\mathbb R$ in alternate ways. I'm hoping for some examples of proofs that do not use the least upper bound property.

-
If the least upper bound property appears in the definition of ${\mathbb R}$ you can't do without it. So what is your model of the reals? (Dedekind cuts, Cauchy sequences, decimal expansions, etc.) –  Christian Blatter Jun 20 '11 at 16:31
@ChristianBlatter Interestingly the text first defines the reals as an ordered field with lub, then proves that any two ordered fields with lub are order isomorphic, then proves NIT, THEN reconstructs the reals as equiv. classes of Cauchy seqs, eventually proves that lub property holds for this set, and remarks that these constructed reals are order isomorphic to the earlier ones. Much later, the text proves the analogous result for nested compact sets in metric spaces, but the phrasing of the remark about other proofs suggested that it was not that later proof that the author was thinking of. –  Philip Jun 20 '11 at 16:40
Note that a similar result holds in every complete metric space and is false for general metric spaces, so it will have to rely somehow on the completeness of $\mathbb R$, which is equivalent to the lub property of $\mathbb R$. –  Alexander Thumm Jun 20 '11 at 17:05
More concretely: this property fails to hold for $\mathbb{Q}$. –  Yuval Filmus Jun 20 '11 at 17:09
I meant completeness. The related theorem sais: Let $(F,d)$ be a complete metric space and $A_1, A_2, \dots$ be a sequence of nested closed subsets of $F$, that is $F \supset A_1 \supset A_2 \supset \dots$ such that the diameters $\text{diam}(A_n) = \sup_{x,y \in A_n}d(x,y) \to 0$ as $n \to \infty$, then $\bigcap_{n \in \mathbb N} A_n \not = \emptyset$. –  Alexander Thumm Jun 21 '11 at 16:45

Here is a sense in which the LUB property and NIT property are mathematically equivalent for the purpose arising in your context. This theorem provides a sense (namely, separable linear orders) in which it isn't possible to prove the NIT in a context where LUB fails; they arrive together. Thus, the question is one of presentation rather than mathematical possibility.

Theorem. Suppose that $\langle R,\lt\rangle$ is any linear order with a countable dense set. Then it satisfies the LUB property if and only if it satisfies the NIT property.

Proof. Suppose it satisfies the LUB property, and $[a_0,b_0]\supset [a_1,b_1]\supset\cdots$ is a descending sequence of intervals. It follows easily that the least upper bound of the $a_n$ is in every interval, and so the NIT property holds. Conversely, suppose that the NIT property holds and that $A\subset R$ is nonempty and bounded above. Enumerate the countable dense set $Q=\{q_n\mid n\in\mathbb{N}\}$, and define a sequence of intervals $[a_n,b_n]$ as follows. The intervals will zero in on where we expect to find the lub of $A$. Choose any $a_0\in A$ and any upper bound $b_0$ of $A$ in $R$. If $[a_n,b_n]$ has been defined, then consider $q_n$. We keep the same interval, unless $a_n\lt q_n\lt b_n$. In this case, we shrink the interval so as to decide $q_n$. That is, if $A$ has elements from the top half $[q_n,b_n]$, then we shrink the interval on that side with $[a_{n+1},b_{n+1}]=[q_n,b_n]$, and otherwise we shrink the interval towards the other side with $[a_{n+1},b_{n+1}]=[a_n,q_n]$. One can now easily prove that $A$ has elements from every interval, that $A$ is bounded above by every $b_n$, that there is a unique element in the intersection of the intervals, and that this element is the least upper bound of $A$. QED

Things become interesting when one drops the countable-dense-set hypothesis. As the argument shows, the LUB property still implies the NIT property in any linear order, but the converse can fail. One easy (counter)example is the order $\mathbb{R}^\ell\oplus\mathbb{R}$, that is, the long line $\mathbb{R}^\ell$ with a copy of the reals on top; the order $\omega_1+\omega^\ast$ works just as well. These orders have the NIT, because any countable sequence of intervals that eventually stays on one side of the principal cut will be fine, and those that straddle the cut will have the left hand sides bounded in $\mathbb{R}^\ell$, since every countable subset of the long line is bounded, and hence have nonempty intersection. But the order does not have the LUB property because of the principal cut between the two orders.

One might be tempted to extend the NIT to longer transfinite nested sequences of intervals, but actually these two orders continue to have the NIT property even for such longer transfinite sequences. This is because of the mis-match in cofinality between the lower and upper sides of the principal cut. If the length of a sequence of intervals straddling this cut has countable cofinality, then it will be bounded in the lower part, and if it has uncountable cofinality, then it will be eventually constant in the upper part; so in any case, sequences of nested closed intervals of any transfinite length will have a nonempty intersection, but the LUB property fails.

The resolution is not to use sequences, but to use filters (or nets), and this is a standard idea in topology when one gets away from the separable case. A linear order has the LUB property if and only if every filter of closed intervals has nonempty intersection. The forward direction is similar to the above, and for the reverse, consider the collection of intervals that straddle where you think the LUB of a set $A$ should be, and the unique point in the intersection of them will be the LUB of $A$.

-
Joel, what is the proper generalization for $R$ with a $\kappa$-dense subset? (Is it some form of $\kappa$-Lindolef-ness or so?) –  Asaf Karagila Jun 20 '11 at 19:30
I edited to explain one such generalization, but it depends on which part you want to generalize. –  JDH Jun 20 '11 at 20:21
@JDH Thanks for this detail. In light of your helpful remarks, do you have any idea what the author might have meant when he said "it can be proved in other ways"? –  Philip Jun 21 '11 at 9:17
I suspect he meant only that one can present a proof that does not explicitly mention the LUB property. For example, you could pove it using the compactness of intervals, or the GLB property, etc., although the larger point remains that all these properties are equivalent in a general sense. For example, I guess one can prove LUB from Rolle's theorem, if you really want to give a crazy order, by considering a certain signed distance function. –  JDH Jun 21 '11 at 11:03
Joel, thanks for the further explanation! –  Asaf Karagila Jun 21 '11 at 12:20
As Yuval Filmus says in the comments, an important basic observation is that a nested collection of closed bounded intervals in $\mathbb{Q}$ may have empty intersection. Thus any proof of this property must make use of a property of $\mathbb{R}$ which is not a property of $\mathbb{Q}$. The least upper bound property is one of the most important such properties, and there are others, many of which turn out to be equivalent (in an appropriate sense) to the least upper bound property.