Nested intervals

4 members of a sequence of nested intervals

In mathematics, a sequence of nested intervals can be intuitively understood as an ordered collection of intervals $I_{n}$ on the real number line with natural numbers $n=1,2,3,\dots$ as an index. Furthermore two conditions have to be met:

1. Every Interval is contained in the previous one ($I_{n+1}$ is always a subset of $I_{n}$).
2. The length of the intervals get arbitrarily small (meaning the length falls below every possible threshold $\varepsilon$ after a certain index $N$).

In other words, the left bound of the interval $I_{n}$ can only increase ($a_{n+1}\geq a_{n}$) and the right bound can only decrease ($b_{n+1}\leq b_{n}$).

Historically - long before anyone defined nested intervals in a textbook - people implicitly constructed such nestings for concrete calculation purposes. For example the ancient Babylonians discovered a method for computing square roots of numbers. In contrast, the famed Archimedes constructed sequences of polygons, that inscribed and surcumscribed a unit circle, in order to get a lower and upper bound for the circles circumference - which is the circle number Pi ($\pi$).

The central question to be posed, is the nature of the intersection over all the natural numbers; or put differently, the set of numbers, that are found in every Interval $I_{n}$ (thus for all $n\in \mathbb {N}$). In modern mathematics, nested intervals are used as a construction method for the real numbers (in order to complete the field of rational numbers).

Historic Motivation

As stated in the introduction, historic users of mathematics discovered the nesting of intervals and closely related algorithms as methods for specific calculations. Some variations and modern interpretations of these ancient techniques will be introduced here:

Computation of Square Roots

One intuitive algorithm is so easy to understand, that it could well be found by engaged highschool students. When trying to find the square root of a number $x>1$, we can be certain, that $1\leq {\sqrt {x}}\leq x$, which gives us the first interval $I_{1}=[1,x]$, in which $x$ has to be found. If we know the next higher perfect square $k^{2}>x$, we get an even better candidate for the fist interval: $I_{1}=[1,k]$.

We now define the other intervals $I_{n}=[a_{n},b_{n}],n\in \mathbb {N}$ recursively by looking at the sequence of midpoints $m_{n}={\frac {a_{n}+b_{n}}{2}}$. Given the interval $I_{n}$ is already known (starting at $I_{1}$), we define

$I_{n+1}:=\left\{{\begin{matrix}\left[m_{n},b_{n}\right]&&{\text{if}}\;\;m_{n}^{2}\leq x\\\left[a_{n},m_{n}\right]&&{\text{if}}\;\;m_{n}^{2}>x\end{matrix}}\right.$

Put into words, we look, whether the midpoint of $I_{n}$is smaller (or bigger) than ${\sqrt {x}}$ and set it als the lower (or upper) bound of our next interval $I_{n+1}$. This guarantees, that ${\sqrt {x}}\in I_{n+1}$. With this construction the intervals are nested and their length $|I_{n}|$ get halved in every step of the recursion. Therefore it is possible to get lower and upper bounds for ${\sqrt {x}}$ with arbitrarily good precision (given enough computational time).

It should be noted here, that we can also compute ${\sqrt {y}}$, when $0<y<1$. In this case $1/y>1$ and the algorithm can be used by setting $x:=1/y$ and calculating the reciprocal, after the desired level of precision has been acquired.

Herons Method

The Babylonian method used an even better algorithm, that yields accurate approximations of $x$ even faster. The modern description using nested intervals is similar to the algorithm above, but instead of the sequence of midpoints we look at a sequence $(c_{n})_{n\in \mathbb {N} }$ given by

$c_{n+1}:={\frac {1}{2}}\cdot \left(c_{n}+{\frac {x}{c_{n}}}\right)$.

Then the sequence of intervals given by $I_{n+1}:=\left[{\frac {x}{c_{n}}},c_{n}\right]$ and $I_{1}=[0,k]$, where $k^{2}>x$, will provide accurate upper and lower bounds for ${\sqrt {x}}$ very fast. In practice, only $c_{n}$ has to be considered, which converges to ${\sqrt {x}}$. This algorithm is a special case of Newton's method.

Archimedes' circle measurement

π can be estimated by computing the perimeters of circumscribed and inscribed polygons.

Main article: Pi: Polygon approximation era

As shown in the image, lower and upper bounds for the circumference of a circle can be obtained with inscribed and circumscribed regular polygons. When examining a circle with diameter $1$, the circumference is (by definition of Pi) the circle number $\pi$.

Around 250 BCE Archimedes of Syracuse started with regular hexagons, whose side lengths (and therefore circumference) can be directly calculated from the circle diameter. Furthermore a way to compute the side length of a regular $2n$-gon from the previous $n$-gon can be found, starting at the regular hexagon ($6$-gon). By successively doubling the number of edges until reaching 96-sided polygons, Archimedes reached an interval with ${\tfrac {223}{71}}<\pi <{\tfrac {22}{7}}$. The upper bound $22/7\approx 3.143$ is still often used as a rough, but pragmatic approximation of $\pi$.

Around the year 1600 CE, Archimedes' method was still the gold standard for calculating Pi and was used by Dutch mathematician Ludolph van Ceulen, to compute more than thirty digits of $\pi$, which took him decades. Soon after, more powerful methods for the computation were found.

Other implementations

Early uses of what we recognize as a sequence of nested intervals today (or what we can describe as such with modern mathematics), can be found in the predecessors of Calculus (differentiation and integration).

Formal discussion

In Mathematical analysis, nested intervals provide one method of axiomatically introducing the real numbers as the completion of the rational numbers, beeing a necessity for discussing the concepts of continuity and differentiability.

Definition

Let $(I_{n})_{n\in \mathbb {N} }$ be a sequence of closed intervals of the type $I_{n}=[a_{n},b_{n}]$, where $|I_{n}|:=b_{n}-a_{n}$ denotes the length of such an interval. We call $(I_{n})_{n\in \mathbb {N} }$ a sequence of nested intervals, if

1. $\quad \forall n\in \mathbb {N} :\;\;I_{n+1}\subseteq I_{n}$
2. $\quad \forall \varepsilon >0\;\exists N\in \mathbb {N} :\;\;|I_{N}|<\varepsilon$.

Put into words, property 1 tells us, that the intervals are nested according to their index. The second property formalizes the notion, that interval sizes get arbitrarily small; meaning, that for an arbitrary constant $\varepsilon >0$ we can always find an interval (with index $N$) with a length strictly smaller than that number $\varepsilon$. We also note, that property 1 immediately implies, that every interval with an index $n\geq N$ also must have a length $|I_{n}|<\varepsilon$.

Axiom of completeness

If $(I_{n})_{n\in \mathbb {N} }$ is a sequence of nested intervals, there always exists a real number, that is contained in every inverval $I_{n}$. In formal notation this axiom guarantees, that

$\exists x\in \mathbb {R} :\;x\in \bigcap _{n\in \mathbb {N} }I_{n}$.

Theorem

Each sequence $(I_{n})_{n\in \mathbb {N} }$ of nested intervals contains exactly one real number $x$.

Proof: This statement can easily be verified by contradiction. Assume, that there exist two different numbers $x,y\in \cap _{n\in \mathbb {N} }I_{n}$. From $x\neq y$ it follows, that they differ by $|x-y|>0.$ Since both numbers have to be contained in every interval, we get, that $|I_{n}|\geq |x-y|$ for all $n\in \mathbb {N}$. This contradicts property 2 from the definition of nested intervals, therefore the intersection can contain at most one number $x$. The completeness axiom guarantees, that such a real number $x$ exists. $\;\square$

Important Notes

• This axiom is fundamental in the sense, that a sequence of nested intervals does not necessarily contain a rational number - meaning that $\cap _{n\in \mathbb {N} }I_{n}$ could yield $\emptyset$, if only considering the rationals.
• The axiom is equivalent to the existence of the infimum and supremum, the convergence of Cauchy sequences and the Bolzano-Weierstrass theorem. This means, that one of the four has to be introduced axiomatically, while the other three can be successively proven.
• The existence of the supremum (or analogously for the infimum) of an above-bounded subset $M\subset \mathbb {R}$ as a direct consequence of this axiom (and vice versa) can be easily proven.

Direct consequences of the Axiom

Existence of Roots

By generalizing the algorithm shown above for square roots, we can prove, that in the real numbers, the equation $x=y^{j},\;j\in \mathbb {N}$ can always be solved for $y={\sqrt[{j}]{x}}=x^{1/j}$; meaning there exists a unique real number $y>0$, such that $x=y^{k}$. Comparing to the section above, we achieve a sequence of nested intervals for the $k$-th root of $x$, namely $y$, by looking at whether the midpoint $m_{n}$ of the $n$-th interval is lower or equal or greater than $m_{n}^{k}$.

Existence of Infimum and Supremum in bounded Sets

Definition

If $A\subset \mathbb {R}$ has an upper bound, i.e. there exists a number $b$, such that $x\leq b$ for all $x\in A$, we call the number $s=\sup(A)$ the supremum of $A$, if

1. the number $s$ is an upper bound of $A$, i.e. $\forall x\in A:\;x\leq s$
2. $s$ is the least upper bound of $A$, i.e. $\forall \sigma <s:\;\exists x\in A:\;x>\sigma$

Only one such number $s$ can exist. Analogously we can define the infimum ($\inf(B)\subset \mathbb {R}$) of a set $B$, that is bounded from below, as the greatest lower bound of that set.

Theorem

Each set $A\subset \mathbb {R}$ has a supremum (infimum), if it is bounded from above (below).

Proof: Without loss of generality we look at a set $A\subset \mathbb {R}$, that has an upper bound. We now construct a sequence $(I_{n})_{n\in \mathbb {N} }$ of nested intervals $I_{n}=[a_{n},b_{n}]$, that has the following two properties:

1. $b_{n}$ is an upper bound of $A$ for all $n\in \mathbb {N}$
2. $a_{n}$ is never an upper bound of $A$ for any $n\in \mathbb {N}$.

The construction follows a recursion by starting with any number $a_{1}$, that is not an upper bound (e.g. $a_{1}=c-1$, where $c\in A$ and an arbitrary upper bound $b_{1}$ of $A$). Given $I_{n}=[a_{n},b_{n}]$ for some $n\in \mathbb {N}$ we compute the midpoint $m_{n}:={\frac {a_{n}+b_{n}}{2}}$ and define

$I_{n+1}:=\left\{{\begin{matrix}\left[a_{n},m_{n}\right]&&{\text{if}}\;m_{n}\;{\text{is an upper bound of}}\;A\\\left[m_{n},b_{n}\right]&&{\text{if}}\;m_{n}\;{\text{is not an upper bound}}\end{matrix}}\right.$

Let $s$ be the number in every interval (whose existence as guaranteed by the axiom). $s$ is an upper bound of $A$, otherwise there exists a number $x\in A$, such that $x>s$. Furthermore this would impy the existence of an interval $I_{m}=[a_{m},b_{m}]$ with $b_{m}-a_{m}<x-s$, from which $b_{n}-s<x-s$ follows, due to $s$ also being an element of $I_{m}$. But this is a contradiction to property 1 of the supremum (meaning $b_{m}<s$ for all $m\in \mathbb {N}$). Therefore $s$ is in fact an upper bound of $A$.

Assume, that there exists a lower upper bound $\sigma <s$ of $A$. Since $(I_{n})_{n\in \mathbb {N} }$ is a sequence of nested intervals, the interval lengths get arbitrarily small; in particular, there exists an interval with a length smaller than $s-\sigma$. But from $s\in I_{n}$ we get $s-a_{n}<s-\sigma$ and therefore $a_{n}>\sigma$. Following the rules of our construction, $a_{n}$ would have to be an upper bound of $A$, contradicting property 2 of all sequences of nested intervals.

In two steps, we have shown, that $s$ is an upper bound of $A$ and that a lower upper bound cannot exist. Therefore $s$ is the supremum of $A$ by definition. $\square$

Remark

As was seen, the existence of suprema and infima of bounded sets is a counsequence of the completeness of $\mathbb {R}$. In effect the two are actually equivalent, meaning that either of the two can be introduced axiomatically.

Proof: Let $(I_{n})_{n\in \mathbb {N} }$ with $I_{n}=[a_{n},b_{n}]$ be a sequence of nested intervals. Then the set $A:=\{a_{1},a_{2},\dots \}$ is bounded from above, where every $b_{n}$ is an upper bound. This implies, that the least upper bound $s=\sup(A)$ fulfills $a_{n}\leq s\leq b_{n}$ for all $n\in \mathbb {N}$. Therefore $s\in I_{n}$ for all $n\in \mathbb {N}$, respectively $x\in \cap _{n\in \mathbb {N} }I_{n}$. $\square$

Further consequences

After formally defining the convergence of sequences and accumulation points of sequences, one can also prove the Bolzano–Weierstrass theorem using nested intervals. In a follow-up, the fact, that Cauchy sequences are convergent (and that all convergent sequences are Cauchy sequences) can be proven. This in turn allows for a proof of the completeness property above, showing their equivalence.

Further Discussion of related Aspects

Without any specifying, what we mean by interval, all that can be said about the intersection $\cap _{n\in \mathbb {N} }I_{n}$ over all the naturals (i.e. the set of all points common to each interval) is, that it is either the empty set $\emptyset$, a point on the number line (called a singleton $\{x\}$), or some interval.

The possibility of an empty intersection can be illustrated by looking at a sequence of open intervals $I_{n}=\left(0,{\frac {1}{n}}\right)=\left\{x\in \mathbb {R} :0<x<{\frac {1}{n}}\right\}$.

In this case, the empty set $\emptyset$ results from the intersection $\cap _{n\in \mathbb {N} }I_{n}$. We get this result, because for any number $x>0$ we can find some value of $n\in \mathbb {N}$ (namely any $n>1/x$), such that $1/n<x$. This is given by the Archimedean property of the real numbers. Therefore, no matter how small $x>0$, we can always find intervals $I_{n}$ in the sequence, such that $x\notin I_{n},$ implying that the intersection has to be empty.

The situation is different for closed intervals. If we change the situation above by looking at closed intervals of the type $I_{n}=\left[0,{\frac {1}{n}}\right]=\left\{x\in \mathbb {R} :0\leq x\leq {\frac {1}{n}}\right\}$, we can see this very clearly. Now for each $x>0$ we still can always find intervals not containig said $x$, but for $x=0$ the property $0\leq x\leq 1/n$ holds true for any $n\in \mathbb {N}$. We conclude, that in this case $\cap _{n\in \mathbb {N} }I_{n}=\{0\}$.

One can also consider the complement of each interval, written as $(-\infty ,a_{n})\cup (b_{n},\infty )$ - which, in our last example, is $(-\infty ,0)\cup (1/n,\infty )$. By De Morgan's laws, the complement of the intersection is a union of two disjoint open sets. By the connectedness of the real line there must be something between them. This shows that the intersection of (even an uncountable number of) nested, closed, and bounded intervals is nonempty.

Higher dimensions

In two dimensions there is a similar result: nested closed disks in the plane must have a common intersection. This result was shown by Hermann Weyl to classify the singular behaviour of certain differential equations.

See also

• Bisection
• Cantor's intersection theorem

References

• Fridy, J. A. (2000), "3.3 The Nested Intervals Theorem", Introductory Analysis: The Theory of Calculus, Academic Press, p. 29, ISBN 9780122676550.
• Shilov, Georgi E. (2012), "1.8 The Principle of Nested Intervals", Elementary Real and Complex Analysis, Dover Books on Mathematics, Courier Dover Publications, pp. 21–22, ISBN 9780486135007.
• Sohrab, Houshang H. (2003), "Theorem 2.1.5 (Nested Intervals Theorem)", Basic Real Analysis, Springer, p. 45, ISBN 9780817642112.
• Königsberger, Konrad (2003), "2.3 Die Vollständigkeit von R (the completeness of the real numbers)", Analysis 1, 6. Auflage (6th edition), Springer, p. 10-15, ISBN 9783642184901