Least upper bound principle and continuous induction

The least upper bound principle is the key organizing principle for real analysis, the basis of many essential arguments. Continuous induction reveals it as a analytic induction principle.

The least-upper-bound principle

The subject of real analysis can be founded upon the least-upper-bound principle, a version of Dedekind completeness. Taking this as a core principle, one proceeds to prove all the familiar foundational theorems, such as the intermediate value theorem, the Heine-Borel theorem and many others. In a sense, the least-upper-bound principle is to real analysis what the induction principle is to number theory.

Please enjoy this free extended excerpt from Lectures on the Philosophy of Mathematics, published with MIT Press 2021, an introduction to the philosophy of mathematics with an approach often grounded in mathematics and motivated organically by mathematical inquiry and practice. This book was used as the basis of my lecture series on the philosophy of mathematics at Oxford University.

Lectures on the Philosophy of Mathematics, MIT Press 2021

Least-upper-bound principle. Every nonempty set of real numbers with an upper bound has a least upper bound.

An upper bound of a set A ⊆ ℝ is simply a real number r, such that every element of A is less than or equal to r. The number r is the least upper bound of A, also called the supremum of A and denoted sup(A), if r is an upper bound of A and r ⩽ s whenever s is an upper bound of A.

Consequences of completeness

Let us illustrate how this fundamental principle is used by sketching proofs of a few familiar elementary results in real analysis. Consider first the intermediate-value theorem, which asserts that if f is a continuous function on the real numbers and d is an intermediate value between f(a) and f(b), then there is a real number c between a and b, with f(c) = d. In short, it asserts that for continuous functions, every intermediate value is realized.

To prove this from the least-upper-bound principle, assume that a < b and f(a) < d < f(b), and consider the set A of all real numbers x in the interval [a,b] for which f(x) < d. This set is nonempty because a is in A, and it is bounded by b. By the least-upper-bound principle, therefore, it has a least upper bound c = sup(A). Consider the value of f(c). If f(c) is too small, meaning that f(c) < d, then by the continuity of f, the values of f(x) for x near c will all also be less than d. But this would mean that A has some elements above c, contrary to c = sup(A). Therefore, f(c) ⩾ d. Similarly, if f(c) is too large, meaning that f(c) > d, then again by the continuity of f, the values of f(x) for x in a small neighborhood of c will all be above d, contradicting c = sup(A), since there must be elements of A as close as desired to c, and those elements x must have f(x) < d by the definition of A. Therefore, it must be that f(c) = d, and we have found the desired point c realizing the intermediate value d.

Consider next the Heine-Borel theorem, which asserts that the unit interval [0,1] is compact. What this means is that whenever 𝒰 is a set of open intervals covering the closed unit interval in the real numbers [0,1], then there are finitely many open intervals of 𝒰 that already cover [0,1]. Huh? For someone new to real analysis, the importance of this open-cover conclusion may not be readily apparent; perhaps it may even seem a little bizarre. Why would it be important that every open cover of a closed interval admits a finite subcover? The answer is that this property is vitally important, and indeed, it is difficult to overstate the importance of the compactness concept, which is the key to thousands of mathematical arguments. The underlying ideas with which it engages grow ultimately into the subject of topology. Let us have a small taste of it.

To prove the Heine-Borel theorem, fix the open cover 𝒰, consisting of open intervals in the real numbers, such that every number x ∈ [0,1] is in some U ∈ 𝒰. Consider the set B consisting of all x ∈ [0,1], such that the interval [0,x] is covered by finitely many elements of 𝒰. Thus, 0 ∈ B, since [0,0] has just the point 0, which is covered by some open set in 𝒰. Let b be the least upper bound of B in [0,1]. If b = 1, then we can cover [0,1] with finitely many elements of 𝒰, and we're done. So assume that b < 1. Since 𝒰 covers the entire interval, there is some open interval U ∈ 𝒰 with b ∈ U. Since U contains a neighborhood of b, which is the supremum of B, there must be a point x ∈ B with x ∈ U. Therefore, we can cover [0,x] with finitely many open sets from 𝒰, and the set U itself covers the rest of the interval [x,b], and so we have covered the interval [0,b] with finitely many open intervals from 𝒰. But because the open interval must spill strictly beyond b, there must be elements of B strictly larger than b, which contradicts the assumption that b is the least upper bound of B. So we have proved the theorem.

Another application of the least-upper-bound principle is the fact that every nested descending sequence of closed intervals has a nonempty intersection. That is, if

\( [a_0,b_0]\supseteq [a_1,b_1]\supseteq [a_2,b_2]\supseteq\cdots, \)

then there is a real number z inside every interval z ∈ [a_n,b_n]. One can simply let z = sup_n a_n. More generally, using the Heine-Borel theorem, one can prove that every nested descending sequence of nonempty closed sets in a real number interval has a nonempty intersection. For if there were no such real number z, then the complements of those closed sets would form an open cover of the original interval, with no finite subcover, contrary to the Heine-Borel theorem.

Continuous induction

Earlier I made an analogy between the least-upper-bound principle in real analysis and the principle of mathematical induction in number theory. This analogy is quite strong in light of the principle of continuous induction, which is an induction-like formulation of the least-upper-bound principle that can be used to derive many fundamental results in real analysis.

Principle of continuous induction. If A is a set of nonnegative real numbers such that

• 0 ∈ A;

• If x ∈ A, then there is δ > 0 with [x,x + δ) ⊆ A;

• If x is a nonnegative real number and [0,x) ⊆ A, then x ∈ A.

Then A is the set of all nonnegative real numbers.

In plain language, the principle has the anchoring assumption that 0 is in the set A, and the inductive properties that whenever all the numbers up to a number x are in A, then x itself is in A; and whenever a number x is in A, then you can push it a little higher, and all the numbers between x and some x + δ are in A. The conclusion, just as in the principle of induction, is that any such set A must contain every number (in this case, every nonnegative real number).

Yuen Ren Chao (1919) describes a similar principle like this:

The theorem is a mathematical formulation of the familiar argument from “the thin end of the wedge,” or again, the argument from “the camel's nose.”

Hyp. 1. Let it be granted that the drinking of half a glass of beer be allowable.

Hyp. 2. If any quantity, x, of beer is allowable, there is no reason why x + δ is not allowable, so long as δ does not exceed an imperceptible amount δ.

Therefore any quantity is allowable.

The principle of continuous induction can be proved from the least-upper-bound principle, by considering the supremum r of the set of numbers a for which [0,a] ⊆ A. This supremum must be in A because [0,r) ⊆ A; but if r ∈ A, then it should be at least a little larger than it is, which is a contradiction. The converse implication also holds, as the reader will prove in question 2.16, and so we have three equivalent principles: continuous induction, least upper bounds, and Dedekind completeness.

Mathematicians are sometimes surprised by the principle of continuous induction — by the idea that there is a principle of induction on the real numbers using the real-number order — because there is a widely held view, or even an entrenched expectation, that induction is fundamentally discrete and sensible only with well-orders. Yet here we are with an induction principle on the real numbers based on the continuous order.

The principle of continuous induction is quite practical and can be used to establish much of the elementary theory of real analysis. Let us illustrate this by using the principle to give an alternative inductive proof of the Heine-Borel theorem. Suppose that 𝒰 is an open cover of [0,1]. We shall prove by continuous induction that every subinterval [0,x] with 0 ⩽ x ⩽ 1 is covered by finitely many elements of 𝒰. This is true of x = 0, since [0,0] has just one point. If [0,x] is covered by finitely many sets from 𝒰, then whichever open set contains x must also stick a bit beyond x, and so the same finite collection covers a nontrivial extension [0,x + δ]. And if every smaller interval [0,r] for r < x is finitely covered, then take an open set containing x, which must contain (r,x] for some r < x; by combining that one open set with a finite cover of [0,r], we achieve a finite cover of [0,x]. So by continuous induction, every [0,x] has a finite subcover from 𝒰. In particular, [0,1] itself is finitely covered, as desired.

Continue reading more about this topic in the book:

Lectures on the Philosophy of Mathematics, MIT Press 2021