Explainer

Nested Interval Theorem

The nested interval theorem: completeness gives a common point, while shrinking interval lengths make it unique.

2022-04-24· Math · Analysis · Nested Interval Property

On this page

Interactive

Bisection traps a target inside nested intervals

Target x 0.37

Nested intervals around x

Move x, then press Halve to trap it.

I₀ ⊇ I₁ ⊇ … , |Iₙ| → 0 ⇒ ⋂ Iₙ = {x}

Each step keeps the half that contains x. The intervals are nested and their lengths halve, so the intersection is exactly one point. This is the nested interval theorem in action.

The nested interval theorem

Let $(I_n)_{n\in\mathbb{N}}$ be a sequence of nonempty closed intervals $I_n=[a_n,b_n]$ in $\mathbb{R}$ . Write $\lvert I_n\rvert=b_n-a_n$ for the length of $I_n$ .

$I_{n+1}\subseteq I_n$ for every $n\in\mathbb{N}$ , and
$\lvert I_n\rvert\to 0$ as $n\to\infty$ ,

then there is exactly one real number that belongs to every interval:

\bigcap_{n\in\mathbb{N}} I_n=\{x\}

The nesting and nonemptiness guarantee a common point; the condition that the lengths tend to zero guarantees that this point is unique.

I₀ = [0, 1]
I₁ = [0, 1/2]
I₂ = [0, 1/4]
I₃ = [0, 1/8]
I₄ = [0, 1/16]

First five intervals for the bisection example Iₙ = [0, 2⁻ⁿ]. Every bar contains 0; the right endpoints shrink toward it. The proof below treats the general theorem.

Proof

Because the intervals are nested, their left endpoints form a nondecreasing sequence: $a_n\leq a_{n+1}$ . They are bounded above by $b_1$ , since $a_n\leq b_n\leq b_1$ . By completeness of $\mathbb{R}$ , the set of left endpoints has a supremum. Define

x=\sup\{a_n:n\in\mathbb{N}\}.

We show that $x$ lies in every $I_n$ . Fix $n$ . For every index $m$ , we have $a_m\leq b_n$ : if $m\geq n$ , then $I_m\subseteq I_n$ ; if $m<n$ , then $a_m\leq a_n\leq b_n$ . Thus $b_n$ is an upper bound for all the left endpoints, so $x\leq b_n$ . Also $a_n\leq x$ , because $x$ is their supremum. Hence $a_n\leq x\leq b_n$ , and therefore $x\in I_n$ . This holds for every $n$ , proving existence.

For uniqueness, suppose that $x$ and $y$ both belong to every interval. Then for every $n$ ,

\lvert x-y\rvert\leq b_n-a_n=\lvert I_n\rvert.

Since $\lvert I_n\rvert\to 0$ , the nonnegative number $\lvert x-y\rvert$ is at most arbitrarily small positive numbers. It follows that $\lvert x-y\rvert=0$ , so $x=y$ . Thus the common point is unique.

Example: locating a point by repeated bisection

Start with $I_0=[0,1]$ and repeatedly keep the left half: $I_n=[0,2^{-n}]$ . These are nonempty closed nested intervals, and their lengths tend to zero. Their only common point is $0$ . More generally, bisection is a way to trap an unknown real number in intervals of increasing accuracy; completeness guarantees that the limiting target exists.

Takeaway

For nonempty closed nested intervals in $\mathbb R$ , nesting and completeness give a common point; lengths tending to zero make that point unique.