Nested intervals
In mathematics, a sequence of nested intervals can be intuitively understood as an ordered collection of intervals formula_1 on the real number line with natural numbers formula_2 as an index. In order for a sequence of intervals to be considered nested intervals, two conditions have to be met: In other words, the left bound of the interval formula_1 can only increase (formula_8), and the right bound can only decrease (formula_9). 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 (formula_10). 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 formula_1 (thus, for all formula_12). 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 formula_13, one can be certain that formula_14, which gives the first interval formula_15, in which formula_16 has to be found. If one knows the next higher perfect square formula_17, one  can get an even better candidate for the first interval: formula_18. The other intervals formula_19 can now be defined recursively by looking at the sequence of midpoints formula_20. Given the interval formula_1 is already known (starting at formula_22), one can define To put this into words, one can compare the midpoint of formula_24 to formula_25 in order to determine whether the midpoint is smaller or larger than formula_25. If the midpoint is smaller, one can set it as the lower bound of the next interval formula_27, and if the midpoint is larger, one can set it as the upper bound  of the next interval. This guarantees that formula_28. With this construction the intervals are nested and their length formula_29 get halved in every step of the recursion. Therefore, it is possible to get lower and upper bounds for formula_30 with arbitrarily good precision (given enough computational time). One can also compute formula_31, when formula_32. In this case formula_33, and the algorithm can be used by setting formula_34 and calculating the reciprocal after the desired level of precision has been acquired. Example. To demonstrate this algorithm, here is an example of how it can be used to find the value of  formula_35. Note that sinceformula_36, the first interval for the algorithm can be defined asformula_37, since formula_35 must certainly found within this interval. Thus, using this interval, one can continue to the next step of the algorithm by calculating the midpoint of the interval, determining whether the square of the midpoint is greater than or less than 19, and setting the boundaries of the next interval accordingly before repeating the process: Herons method. The Babylonian method uses an even more efficient algorithm that yields accurate approximations of formula_44 even faster. The modern description using nested intervals is similar to the algorithm  above, but instead of using a sequence of midpoints, one uses a sequence formula_45 given by This results in a sequence of intervals given by formula_47 and formula_48, where formula_49, will provide accurate upper and lower bounds for formula_25 very fast. In practice, only formula_51 has to be considered, which converges to formula_25. This algorithm is a special case of Newton's method. Archimedes' circle measurement. 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 formula_53, the circumference is  (by definition of Pi) the circle number formula_10. 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 formula_55-gon from the previous formula_56-gon can be found, starting at the regular hexagon (formula_57-gon). By successively doubling the number of edges until reaching 96-sided polygons, Archimedes reached an interval with formula_58. The upper bound formula_59 is still often used as a rough, but pragmatic approximation of formula_10. 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 formula_10, which took him decades. Soon after, more powerful methods for the computation were found. Other implementations. Early uses of sequences of nested intervals (or can be described as such with modern mathematics), can be found in the predecessors of calculus (differentiation and integration). In computer science, sequences of nested intervals is used in algorithms for numerical computation. I.e. the Bisection method can be used for calculating the roots of continuous functions. In contrast to  mathematically infinite sequences, an applied computational algorithm terminates at some point, when the desired zero has been found or sufficiently well approximated. The construction of the real numbers. In mathematical analysis, nested intervals provide one method of axiomatically introducing the real numbers as the completion of the rational numbers, being a necessity for discussing the concepts of continuity and differentiability. Historically, Isaac Newton's and Gottfried Wilhelm Leibniz's discovery of differential and integral calculus from the late 1600s has posed a huge challenge for mathematicians trying to prove their methods rigorously; despite their success in physics, engineering and other  sciences. The axiomatic description of nested intervals (or an equivalent axiom) has become an important foundation for the modern understanding of calculus. In the context of this article, formula_62 in conjunction with formula_63 and formula_64 is an Archimedean ordered field, meaning the axioms of order and the Archimedean property hold. Definition. Let formula_65 be a sequence of closed intervals of the type formula_66, where formula_67 denotes the length of such an interval. One can call formula_65 a sequence of nested intervals, if Put into words, property 1 means, 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 formula_71 one can always find an interval (with index formula_6) with a length strictly smaller than that number formula_5. It is also worth noting that property 1 immediately implies that every interval with an index formula_74 must also have a length formula_75. Remark. Note that some authors refer to such interval-sequences, satisfying both properties above, as "shrinking nested intervals". In this case a sequence of nested intervals refers to a sequence that only satisfies property 1. Axiom of completeness. If formula_65 is a sequence  of nested intervals, there always exists a real number, that is contained in every interval formula_1. In formal notation this axiom guarantees, that Theorem. Each sequence formula_65 of nested intervals contains exactly one real number formula_44. "Proof:" This statement can easily be verified by contradiction. Assume that there exist two different numbers formula_81. From formula_82 it follows, that they differ by formula_83 Since both numbers have to be contained in every interval, it follows that formula_84 for all formula_12. This contradicts property 2 from the definition of nested intervals; therefore, the intersection can contain at most one number formula_44. The  completeness axiom guarantees, that such a real number formula_44 exists. formula_88 Direct consequences of the axiom. Existence of roots. By generalizing the algorithm shown above for square roots, one can prove that in the real numbers, the equation formula_91 can always be solved for formula_92. This means there exists a unique real number formula_93, such that formula_94. Comparing to the section above, one achieves a sequence of nested intervals for the formula_95-th root of formula_44, namely formula_97, by looking at whether the midpoint formula_98 of the formula_56-th interval is lower or equal or greater than formula_100. Existence of  infimum and supremum in bounded Sets. Definition. If formula_101 has an upper bound, i.e. there exists a number formula_102, such that formula_103 for all formula_104, one can call the number formula_105 the supremum of formula_106, if Only one such number formula_107 can exist. Analogously one can define the infimum (formula_114) of a set formula_115, that is bounded from below, as the greatest lower bound of that set. Theorem. Each set formula_101 has a supremum (infimum), if it is bounded from above (below). "Proof:" Without loss of generality one can look at a set formula_101 that has an upper bound. One  can now construct a sequence formula_65 of nested intervals formula_66, that has the following two properties: The construction follows a recursion by starting with any number formula_126, that is not an upper bound (e.g. formula_127, where formula_128 and an arbitrary upper bound formula_129 of formula_106). Given formula_66 for some formula_12 one can compute the midpoint formula_133 and define Note that this interval sequence is well defined and obviously a sequence of nested intervals by construction. Now let formula_135 be the number in every interval (whose existence is guaranteed by the axiom). formula_107 is an upper bound of formula_106, otherwise there  exists a number formula_104, such that formula_139. Furthermore, this would imply the existence of an interval formula_140 with formula_141, from which formula_142 follows, due to formula_143 also being an element of formula_144. But this is a contradiction to property 1 of the supremum (meaning formula_145). Therefore formula_107 is in fact an upper bound of formula_106. Assume that there exists a lower upper bound formula_148 of formula_106. Since formula_65 is a sequence of nested intervals, the interval lengths get arbitrarily small; in particular, there exists an interval with a length smaller than formula_151. But from formula_152 one gets formula_153. Following the  rules of this construction, formula_123 would have to be an upper bound of formula_106, contradicting property 2 of all sequences of nested intervals. In two steps, it has been shown that formula_107 is an upper bound of formula_106 and that a lower upper bound cannot exist. Therefore formula_107 is the supremum of formula_106 by definition. Remark. As was seen, the existence of suprema and infima of bounded sets is a counsequence of the completeness of formula_62. In effect the two are actually equivalent, meaning that either of the two can be introduced axiomatically. "Proof:" Let formula_65 with formula_66 be  a sequence of nested intervals. Then the set formula_163 is bounded from above, where every formula_120 is an upper bound. This implies, that the least upper bound formula_105 fulfills formula_166 for all formula_12. Therefore formula_152 for all formula_12, respectively formula_170. 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 is meant by interval, all that can be said about the intersection formula_171 over all the naturals (i.e. the set of all points common to each interval) is that it is either the empty set formula_90, a point on the number line (called a singleton formula_173), or some interval. The possibility of an empty intersection can be illustrated by looking at a sequence of open intervals formula_174. In this case, the empty set formula_90 results from the intersection formula_171. This result comes from the fact that, for any number  formula_177 there exists some value of formula_12 (namely any formula_179), such that formula_180. This is given by the Archimedean property of the real numbers. Therefore, no matter how small formula_181, one can always find intervals formula_182 in the sequence, such that formula_183 implying that the intersection has to be empty. The situation is different for closed intervals. If one changes the situation above by looking at closed intervals of the type formula_184, one can see this very clearly. Now for each formula_177 one still can always find intervals not containing said formula_44, but for formula_187, the property formula_188 holds true  for any formula_12. One can conclude that, in this case, formula_190. One can also consider the complement of each interval, written as formula_191 - which, in our last example, is formula_192. 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.