Suprema, the Archimedean property and density

Lesson 2 introduced the completeness axiom. This lesson learns to use it. We develop a working characterization of the supremum in terms of \(\varepsilon\), prove the Archimedean property (there is no infinitely large real number), deduce that the rationals and the irrationals are both dense in the reals, and prove the nested interval property, which is a geometric form of completeness. Along the way we will practise the most common way of computing a supremum in a proof: guess it, show it is an upper bound, then show nothing smaller works.

The epsilon characterization of the supremum

Condition (ii) in the definition of the supremum, 'no smaller number is an upper bound', is awkward to use directly. The following lemma restates it in a form that fits the epsilon style of analysis.

Lemma (approximation property). Let \(S \subseteq \mathbb{R}\) be non-empty and let \(u\) be an upper bound of \(S\). Then \(u = \sup S\) if and only if for every \(\varepsilon > 0\) there is an \(s \in S\) with \(s > u - \varepsilon\).

Proof. Suppose \(u = \sup S\) and let \(\varepsilon > 0\). The number \(u - \varepsilon\) is less than \(u\), so it is not an upper bound of \(S\). Hence some \(s \in S\) satisfies \(s > u - \varepsilon\).

Conversely, suppose the epsilon condition holds, and let \(v\) be any upper bound of \(S\). If \(v < u\), take \(\varepsilon = u - v > 0\). Then some \(s \in S\) has \(s > u - \varepsilon = v\), contradicting that \(v\) is an upper bound. So \(v \ge u\), and \(u\) is the least upper bound. \(\blacksquare\)

In words: the supremum is an upper bound that the set gets arbitrarily close to. There are points of \(S\) in every interval \((u - \varepsilon, u]\).

The Archimedean property

Is the set of natural numbers bounded above in \(\mathbb{R}\)? It seems obvious that it is not, but 'obvious' is not a proof, and in fact there are ordered fields (called non-Archimedean fields) that contain elements larger than every natural number. In \(\mathbb{R}\) such elements do not exist, and completeness is the reason.

Theorem (Archimedean property). The set \(\mathbb{N}\) is not bounded above in \(\mathbb{R}\). Equivalently, for every real \(x\) there is a natural number \(n > x\).

Proof. Suppose for contradiction that \(\mathbb{N}\) is bounded above. It is non-empty, so by completeness it has a supremum \(u\). By the approximation property with \(\varepsilon = 1\), there is a natural number \(m > u - 1\). Then \(m + 1 > u\), and \(m + 1\) is a natural number, contradicting that \(u\) is an upper bound of \(\mathbb{N}\). \(\blacksquare\)

The property is named after Archimedes, who used it in the form 'given two magnitudes, some multiple of the smaller exceeds the larger'. Here are the forms we will use most.

Corollary. (a) For every \(\varepsilon > 0\) there is \(n \in \mathbb{N}\) with \(\frac{1}{n} < \varepsilon\). (b) For every \(x > 0\) and every real \(y\) there is \(n \in \mathbb{N}\) with \(nx > y\). (c) \(\inf \{\frac{1}{n} : n \in \mathbb{N}\} = 0\).

Proof. (a) Choose \(n > \frac{1}{\varepsilon}\). (b) Choose \(n > \frac{y}{x}\). (c) Zero is a lower bound, and by (a) every \(\varepsilon > 0\) is larger than some \(\frac{1}{n}\), so no positive number is a lower bound; negative numbers are lower bounds but smaller than 0. \(\blacksquare\)

Part (a) is the fact that justified every 'choose \(N > \frac{1}{\varepsilon}\)' in lesson 1. Another useful consequence is that every real number lies between two consecutive integers.

Lemma. For every real \(x\) there is a unique integer \(m\) with \(m \le x < m + 1\). This \(m\) is the floor of \(x\), written \(\lfloor x \rfloor\).

Proof. By the Archimedean property there are integers below \(x\) and above \(x\). The set of integers \(k\) with \(k > x\) is non-empty and bounded below by any integer below \(x\); by the well-ordering principle from MATH-228 (applied after shifting to natural numbers) it has a least element \(k_0\). Set \(m = k_0 - 1\). Then \(m \le x\), since \(m\) is not in the set, and \(x < m + 1 = k_0\). Uniqueness: two integers \(m < m'\) with this property would satisfy \(m + 1 \le m' \le x < m + 1\). \(\blacksquare\)

Density of the rationals

Between any two real numbers there is a rational number. This is the precise version of the statement that the rationals are 'everywhere' on the number line even though they have gaps.

Theorem (density of \(\mathbb{Q}\)). If \(a < b\) are real numbers, there is a rational \(r\) with \(a < r < b\).

Proof. The idea is to choose a denominator \(n\) so fine that the grid \(\frac{1}{n}\mathbb{Z}\) has a point between \(a\) and \(b\). By the Archimedean property choose \(n \in \mathbb{N}\) with \(\frac{1}{n} < b - a\), that is, \(nb - na > 1\). Let \(m = \lfloor na \rfloor + 1\). Then \(m - 1 \le na < m\), so \(na < m\). Also \(m \le na + 1 < nb\). So \(na < m < nb\), and dividing by \(n\) gives \(a < \frac{m}{n} < b\). \(\blacksquare\)

Corollary (density of the irrationals). If \(a < b\) there is an irrational number \(t\) with \(a < t < b\).

Proof. Apply density of \(\mathbb{Q}\) to \(\frac{a}{\sqrt{2}} < \frac{b}{\sqrt{2}}\) to get a rational \(r\) between them, and choose \(r \ne 0\) (if the rational found is 0, apply the theorem again to \((0, \frac{b}{\sqrt 2})\) or \((\frac{a}{\sqrt 2}, 0)\)). Then \(t = r\sqrt{2}\) lies between \(a\) and \(b\) and is irrational, since \(\sqrt{2} = \frac{t}{r}\) would otherwise be rational. \(\blacksquare\)

Density is surprising when combined with the counting results of MATH-228. The rationals are countable and the irrationals are uncountable, so in the sense of cardinality there are vastly more irrationals than rationals. Yet both are dense: every interval, however small, contains infinitely many of each.

from fractions import Fraction
import math

def rational_between(a, b):
    """Follow the density proof: pick n with 1/n < b - a, then m = floor(n a) + 1."""
    n = math.floor(1 / (b - a)) + 1
    m = math.floor(n * a) + 1
    return Fraction(m, n)

pairs = [(Fraction(1, 3), Fraction(1, 2)),
         (Fraction(314159, 100000), Fraction(314160, 100000)),
         (Fraction(-7, 5), Fraction(-139, 100))]
for a, b in pairs:
    r = rational_between(a, b)
    print(f"a = {float(a):.6f}  b = {float(b):.6f}  r = {r}  ({float(r):.7f})  a < r < b: {a < r < b}")

a = 0.333333  b = 0.500000  r = 3/7  (0.4285714)  a < r < b: True
a = 3.141590  b = 3.141600  r = 314163/100001  (3.1415986)  a < r < b: True
a = -1.400000  b = -1.390000  r = -141/101  (-1.3960396)  a < r < b: True

Suprema and arithmetic

Many problems ask for the supremum of a set built from other sets. A typical example is the sum set \(S + T = \{s + t : s \in S, t \in T\}\).

Theorem. If \(S\) and \(T\) are non-empty and bounded above, then \(\sup (S + T) = \sup S + \sup T\).

Proof. Let \(a = \sup S\) and \(b = \sup T\). For \(s \in S\), \(t \in T\) we have \(s + t \le a + b\), so \(a + b\) is an upper bound of \(S + T\). For the approximation property, let \(\varepsilon > 0\). There are \(s \in S\) with \(s > a - \frac{\varepsilon}{2}\) and \(t \in T\) with \(t > b - \frac{\varepsilon}{2}\). Then \(s + t > a + b - \varepsilon\), and \(s + t \in S + T\). By the lemma, \(\sup (S + T) = a + b\). \(\blacksquare\)

Products are more delicate. For non-negative sets the analogous result \(\sup (ST) = \sup S \cdot \sup T\) holds, but for sets containing negative numbers it fails: with \(S = T = \{-2, -1\}\), \(\sup S \cdot \sup T = 1\) while \(ST = \{1, 2, 4\}\) has supremum 4.

Nested intervals

Completeness can be expressed geometrically. A sequence of closed intervals \(I_n = [a_n, b_n]\) is nested if \(I_1 \supseteq I_2 \supseteq I_3 \supseteq \dots\), that is, \(a_1 \le a_2 \le \dots\) and \(b_1 \ge b_2 \ge \dots\), with \(a_n \le b_n\).

Theorem (nested interval property). If \(I_1 \supseteq I_2 \supseteq \dots\) are non-empty closed bounded intervals, then \(\bigcap_{n=1}^{\infty} I_n\) is non-empty. If moreover the lengths \(b_n - a_n\) have infimum 0, the intersection contains exactly one point.

Proof. Let \(A = \{a_n : n \in \mathbb{N}\}\). For any \(m\) and \(n\), \(a_n \le b_m\): if \(n \le m\) then \(a_n \le a_m \le b_m\), and if \(n > m\) then \(a_n \le b_n \le b_m\). So every \(b_m\) is an upper bound of \(A\). By completeness \(x = \sup A\) exists, and \(a_n \le x\) for all \(n\). Since \(x\) is the least upper bound and each \(b_m\) is an upper bound, \(x \le b_m\) for all \(m\). Hence \(a_n \le x \le b_n\) for every \(n\), so \(x \in \bigcap I_n\).

If \(y\) is another point of the intersection, then \(|x - y| \le b_n - a_n\) for every \(n\), so \(|x - y|\) is a lower bound of the lengths. If their infimum is 0, then \(|x - y| \le 0\) and \(y = x\). \(\blacksquare\)

Both hypotheses matter. Open intervals can be nested with empty intersection: \(\bigcap (0, \frac{1}{n}) = \emptyset\), since any \(x > 0\) fails to be in \((0, \frac{1}{n})\) once \(\frac{1}{n} < x\). Unbounded closed intervals can too: \(\bigcap [n, \infty) = \emptyset\). And in \(\mathbb{Q}\) the property fails: the rational intervals given by the decimal truncations of \(\sqrt{2}\), \([1, 2] \supseteq [1.4, 1.5] \supseteq [1.41, 1.42] \supseteq \dots\), have no rational point in common.

The nested interval property gives a second proof that \(\mathbb{R}\) is uncountable, independent of decimals. Given any sequence \(x_1, x_2, \dots\), choose a closed interval \(I_1\) missing \(x_1\), inside it a closed interval \(I_2\) missing \(x_2\), and so on. A point in \(\bigcap I_n\) differs from every \(x_n\). This was in fact Cantor's first proof of uncountability, in 1874, before the diagonal argument of 1891.

Why completeness is the right axiom

It is worth pausing to see how much of this lesson rests on the single completeness axiom. The Archimedean property, the floor function, density of the rationals and irrationals, and the nested interval property were all proved from it, together with the ordinary algebra of an ordered field. In fact several of these statements are equivalent to completeness once the Archimedean property is assumed. For example, an Archimedean ordered field in which every nested sequence of closed bounded intervals has a common point is necessarily complete. Analysts therefore sometimes take the nested interval property, or the monotone convergence theorem of lesson 5, or the Cauchy criterion of lesson 6, as the basic axiom instead of the least upper bound property. Each choice leads to the same real numbers.

The practical lesson is that whenever a proof in this course needs to produce a number that is not given by a formula, such as a limit, a maximum, or a point where a function crosses zero, completeness is being used somewhere, usually through a supremum. When you read a proof, try to find the step where completeness enters. If you cannot find one, either the result also holds over the rationals, or the proof has a gap.