nested interval property

The nested interval property is yet another way to state the completeness of the reals, sometimes it is also known as Cantor's intersection theorem, or sometimes a slightly more general version that talks about nested compact sets in a metric space receives Cantor's name. Most introductions to mathematical analysis in North America involve giving the students several different ways of saying that the real numbers are a complete ordered field, and the nested interval property is often another one of those ways. Basically, what it says is that if you have a bunch of nested closed intervals (well, an infinite sequence of them, just to make it interesting), then their intersection is not empty; that is, there is at least one real number that is in all of the nested intervals.

So what the heck are nested closed intervals anyways? Well, first, let me remind you from your calculus class that a closed interval of real numbers is simply defined to be two real numbers a and b (let us say that "infinity is not a real number", so that both a and b are finite), plus all the real numbers between those two; the usual notation for a closed interval from a to b is [a, b]. To say that two intervals are nested means that one is contained inside the other; metaphorically, the bigger interval is a "nest" for the smaller one. For example, [1,2] is nested inside [0,3]. To say that an entire infinite sequence of intervals is nested means that each interval in the sequence is nested inside the previous interval in the sequence.

To paraphrase the statement of the nested interval property, no matter how these closed nested intervals shrink, they're always going to trap at least one real number. The nested interval property is not true in the rationals Q, as the prototypical example of an ordered field that is not complete. There you can have a bunch of nested intervals centred on an irrational number (and to be perfectly rigourous, we'de have to find some roundabout way to say that they are nested around an irrational number without mentioning irrational numbers, since we're working only with rational numbers, but I don't want to be perfectly rigourous), and if their length shrinks to zero, then they would eventually miss every number around this irrational number, therefore miss everything, and have an empty intersection.

Just in order to get concrete about this example, consider the sequence of nested intervals defined by [√2 -1/2, √2 + 1/2 ], [√2 -1/3, √2 + 1/3 ], [√2 -1/4, √2 + 1/4 ] ..., as intervals in Q. Then this sequence of closed nested has an empty intersection in Q

A proof of sorts for R

So how does the proof of the nested interval property go for the real numbers R? Since it's essentially another statement of completeness of the reals, it is going to itself depend on some rephrasing of completeness of the reals. This isn't begging the question, because I'm not proving that the reals are complete, but merely that the nested interval property is another way to say that the reals are complete (the statement "the reals are complete" can either be taken as an axiom, as is customary, or it can be proven from a careful construction of the reals with Dedekind cuts or Cauchy sequences). What I'm going to do is take one phrasing of completeness of the reals and show how the nested interval property follows from this phrasing.

I'm going to choose one such phrasing that happens to be convenient: the monotone sequence property. A Hungarian professor of mine had a mantra that said something like "every increasing bounded sequence converges"; of course, the same can be said about every decreasing sequence. This seems to be a statement of completeness of the reals that is popular in introductory analysis courses nowadays in North America, and the statement that I shall adopt. It's a simple exercise to prove that the monotone sequence theorem is equivalent to the supremum property of the reals.

A translation from intervals to sequences now follows. Suppose that [a₁, b₁], [a₂, b₂], [a₃, b₃], ... is a nested sequence of closed intervals. By definition, this means that a₁ ≤ a₂ ≤ a₃ ≤ ..., and that b₁ ≥ b₂ ≥ b₃ ≥ ...; that is, the a's form a monotone increasing subsequence, and the b's form a monotone decreasing subsequence. Not only that, but the nested interval property also tells us that every a is smaller than every b, so the two monotone sequences both converge, say that the a's converge to A, and the b's converge to B. Because the a's are bounded by the b's and the b's are bounded by the a's, it follows that their limits are equally bounded and therefore A ≤ B.

It remains to prove that A and B are both in every interval of our nested sequence, which would prove more than what we set out to prove, since for our original intent, it would suffice to prove that merely one of them is in every interval. This is easy to prove, since for every a_n, it follows that a_n ≤ A, because the a's are a monotone increasing sequence, and thus their limit cannot be smaller than any element in this sequence; similarly, because every a is no larger than every b, it follows that the limit a's must be smaller than every b, that is, A ≤ b_n for all n, but being no smaller than every a and no larger than every b is exactly what it means to be in every interval of this nested sequence, and therefore A is in the intersection of this nested sequence of closed intervals. A symmetric argument holds for B, and in fact, the same argument holds for every real number between A and B, so that the entire closed interval [A, B ] is in the intersection of the sequence of nested closed intervals. Of course, the interval [A, B ] may degenerate into a single point in case that A = B, but that's no concern, so long as we have one point in it, which is what the nested interval property is all about.

But wait! There's more!

We have proven that the monotone sequence theorem implies the nested interval property. Let us now prove that the nested interval property implies the monotone sequence theorem and thus prove that the two statements are equivalent.

The idea is to use a bisection method for trapping the number to which the monotone sequnce converges. The nested interval property guarantees that the bisection method works and traps a unique real number, in this case, the limit of a monotone sequence. Details now follow.

Let x₁, x₂, x₃,... be a monotone bounded sequence, without loss of generality, an increasing subsequence, for we could otherwise take the negative of every number of the sequence in case that the sequence were decreasing. We construct another sequence of nested intervals in the following manner.

Let M be an upper bound for the sequence x₁, x₂, x₃... Define a₁ := x₁ and b₁ := M. Since the sequence is monotone increasing, all x's are greater than or equal to x₁ = a₁. Since M is an upper bound, all x's are also less than or equal to M = b₁. In other words, the entire sequence is found inside the closed interval [a₁, b₁].

Consider now the midpoint m₁ = (a₁ + b₁)/2. This is why I said that this would be a bisection method. Two things can happen. Either some x's are greater than m₁, or not. Consider those two cases.

1. No x's are greater than m₁. In this case m₁ is tighter upper bound for the monotone sequence of x's, so we can shrink our interval in the following way:
   1. a₂ := a₁
   2. b₂ := m₁
2. Some of the x's are greater than m₁ (and hence infinitely many, since the x's are a monotone increasing sequence). In this case, the tail of the sequence is to the right of m₁, and the limit of a sequence is by its tail, if it's anywhere. In this case, we define instead
   1. a₂ := m₁
   2. b₂ := b₁

Clearly, the intervals [a₁, b₁], [a₂, b₂], [a₃, b₃]... obtained by this bisection method are nested. Equally clearly, since their lengths are halved at each step, they are shrinking. By the nested interval property, they must have nonempty intersection. Let L be in this intersection. It is clear that there is only one such L, since the lengths of the intervals are shrinking to zero. I claim that L is the limit of the monotone sequence of x's.

To prove this last statement, we shall go to the definition of the limit of a sequence. Let ε > 0 be given. Choose an N large enough such that one of the intervals [a_N, b_N] has length smaller than ε. Such N exists since the length of the nested intervals shrinks to zero. We know that L is inside this interval, and we also know by the bisection method that this interval contains the tail of the x's, since the x's are a monotone increasing sequence. Let K be the index of some x_K in the interval [a_N, b_N]. Then for all n > K, x_n is also in this same interval, since the x's are a monotone increasing sequence and bounded above by b_N. That is, for this ε, whenever n > K, then |L - x_n| < ε. By definition of the limit, this means that L is indeed the limit of the x's, as was to be shown.

QED is what the cool kids like to say at this point.