5.6 The Real Numbers Form a Complete Ordered Field

Section 5.5 proved one form of completeness: in $\mathbb{R}$ every Cauchy sequence converges (Theorem 5.5.1). Analysis on the Real Line, Chapter 1 starts from another form, about sets rather than sequences: every non-empty set of real numbers that is bounded above has a least upper bound. In $\mathbb{Q}$ both fail, the first by Theorem 4.6.1 and the second by Theorem 2.6.2. This section names the second property for an arbitrary ordered field, proves that an ordered field that is Archimedean and Cauchy-complete has it, and concludes that the constructed $\mathbb{R}$ is a complete ordered field. The proof bisects intervals, and one line of it, which we shall point at, cannot do without Archimedes.

Throughout, $F$ is an ordered field (Definition 2.3.2). Its order $\le$ is a total order (Proposition 4.1.2 (a)), so the words “upper bound”, “bounded above” and “supremum” of Sets, Relations, and Cardinality, Section 2.6 apply to subsets of $F$ (Sets, Relations, and Cardinality, Definition 2.6.2, Sets, Relations, and Cardinality, Definition 2.6.5). When $F = \mathbb{R}$ , we keep the identification of Section 5.4, writing $q$ for $\kappa(q)$ .

5.6.1. Complete ordered fields

Section 2.6 found a gap in $\mathbb{Q}$ without any sequence: the set $A = \{ x \in \mathbb{Q} : x^2 < 2 \}$ is non-empty and bounded above in $\mathbb{Q}$ , and among its rational upper bounds there is no least one (Theorem 2.6.2). The upper bounds crowd down toward a place where $\mathbb{Q}$ has no element. A field without such gaps is one in which every set that could have a least upper bound does have one.

Every non-empty set that is bounded above has a least upper bound.

Definition 5.6.1 (Complete Ordered Field)

An ordered field $F$ is complete if every non-empty subset $A \subseteq F$ that is bounded above in $(F, \le)$ (Sets, Relations, and Cardinality, Definition 2.6.2) has a supremum in $F$ (Sets, Relations, and Cardinality, Definition 2.6.5). In symbols, writing $\mathrm{ub}(u)$ for $\forall a \in A \ \ a \le u$ , $\begin{aligned} &\forall A \subseteq F \ \ \bigl( (A \ne \emptyset \wedge \exists u \in F \ \mathrm{ub}(u)) \Rightarrow \\ &\qquad \exists s \in F \ \bigl( \mathrm{ub}(s) \wedge \forall u \in F \ (\mathrm{ub}(u) \Rightarrow s \le u) \bigr) \bigr) . \end{aligned}$ An ordered field in which every Cauchy sequence (Definition 4.5.1) converges is called Cauchy-complete.

In words: the hypothesis asks for a set with at least one element and at least one upper bound in $F$ ; the conclusion asks for an element $s$ of $F$ that is an upper bound, clause (S1), and lies below every upper bound, clause (S2). The supremum need not belong to $A$ .

Well-definedness. A set has at most one supremum: if $s$ and $s'$ both are, then (S2) for each, with the other as the upper bound, gives $s \le s'$ and $s' \le s$ , so $s = s'$ by antisymmetry. So “the supremum of $A$ ”, written $\sup A$ , names one element when it exists.

Examples.

The negative elements. In every ordered field, $A \mathrel{:=} \{ x \in F : x < 0 \}$ has supremum $0$ . It is non-empty ( $-1 \in A$ ). The element $0$ is an upper bound. If an upper bound $b$ had $b < 0$ , then $b < b/2 < 0$ (Proposition 4.1.2 (b)), so $b/2 \in A$ lies above $b$ , which is impossible. So every upper bound $b$ satisfies $b \ge 0$ , and $\sup A = 0 \notin A$ . No completeness was needed: some sets have suprema in every ordered field.

The rationals. $\mathbb{Q}$ is not complete: Theorem 2.6.2 exhibits a non-empty subset bounded above with no supremum in $\mathbb{Q}$ .

The constructed reals. $\mathbb{R}$ is complete; this is the main theorem of the section, proved at its end.

Second readingA degenerate case, and non-examples by minimal change

A singleton. $\sup \{a\} = a$ , in every ordered field. This degenerate case matters below: a set may be bounded above by its own element.

Drop “non-empty”: the empty set is bounded above by every element of $F$ , so its upper bounds are all of $F$ , and $F$ has no least element ( $x - 1 < x$ ). Drop “bounded above”: $F$ itself has no upper bound ( $x < x + 1$ ), so no supremum. With either clause removed, no ordered field at all would be complete.

Why this definition. It asks about suprema, not maxima: the set of negative elements has no greatest element in any ordered field, since $x < x/2 < 0$ for $x < 0$ , and asking for maxima would make no field complete. It asks about sets, not sequences, the form Analysis on the Real Line, Chapter 1 takes as its axiom. “Complete” alone always means this property; the sequence property of Section 5.5 is “Cauchy-complete”.

Warning. The supremum of a set is an upper bound not necessarily in the set, and “complete” is not “every non-empty bounded set has a largest element”: the set of negative elements above has supremum $0$ and no largest element. A proof that ends “so $\sup A \in A$ ” needs a reason, such as $A$ being finite.

So $\mathbb{Q}$ is neither complete nor Cauchy-complete. Section 5.5 removed the second gap for $\mathbb{R}$ ; this section removes the first.

5.6.2. Powers of two in an ordered field

The bisection below halves an interval at each step, so after $k$ steps its length is the first length divided by $2^k$ . We need $2^k$ to grow at least as fast as $k + 1$ , inside the field.

Lemma 5.6.1 (A Lower Bound for Powers of Two)

Let $F$ be an ordered field, and let $(2 \cdot 1_F)^k$ be the power in $F$ of Definition 4.2.1 (b). Then $(2 \cdot 1_F)^k \ge (k + 1) \cdot 1_F \qquad \text{for every } k \in \mathbb{N} .$ In particular $(2 \cdot 1_F)^k \ge 1_F > 0$ .

Idea. Induction on $k$ . Multiplying by $2$ doubles the right side, $(k + 1) + (k + 1)$ , and doubling gains at least $1$ , which is all the step needs.

Proof. We use Logic and Proof, Axiom 4.2.1, read on $\mathbb{N} = \omega$ through Corollary 1.7.3 (b), for $P(k)$ : $(2 \cdot 1_F)^k \ge (k + 1) \cdot 1_F$ .

Base $P(0)$ . $(2 \cdot 1_F)^0 = 1_F$ by Definition 4.2.1 (b), and $(0 + 1) \cdot 1_F = 1 \cdot 1_F = 0 \cdot 1_F + 1_F = 1_F$ by (a) of that definition, since $0 + 1 = 1$ (Definition 1.5.1 (c)). Equality holds.

Step. Assume $P(k)$ , and let $y \mathrel{:=} (k + 1) \cdot 1_F$ . By Definition 4.2.1 (a) and Definition 1.5.1 (c), $2 \cdot 1_F = 1 \cdot 1_F + 1_F = 1_F + 1_F$ , which is positive (Proposition 4.1.2 (b)). By Definition 4.2.1 (b), $P(k)$ , and Proposition 2.3.5 (c) (or equality, if $P(k)$ holds with equality), $(2 \cdot 1_F)^{k+1} = (2 \cdot 1_F)^k (2 \cdot 1_F) \ge y (1_F + 1_F) = y + y ,$ the last step by distributivity (F9) and (F7). Since $k + 1 \ge 1$ (Theorem 1.6.1 (d)), Proposition 4.2.1 (b) gives $y \ge 1_F$ , so $y + y \ge y + 1_F$ (Proposition 2.3.5 (b)). Finally $y + 1_F = ((k + 1) + 1) \cdot 1_F$ by Definition 4.2.1 (a). Hence $(2 \cdot 1_F)^{k+1} \ge ((k + 1) + 1) \cdot 1_F$ , which is $P(k + 1)$ .

The last sentence of the lemma follows, since $(k + 1) \cdot 1_F \ge 1_F > 0$ (Proposition 4.2.1 (b), as $k + 1 \ge 1$ ).

From here on, $2^k$ means $(2 \cdot 1_F)^k$ . By Proposition 4.2.1 (c) it equals $(2^k) \cdot 1_F$ , the multiple of $1_F$ by the natural number $2^k$ , so the two readings agree; the proofs below use only the power in $F$ and the lemma. Since $2^k > 0$ , the quotient $D/2^k$ is defined for every $D \in F$ .

5.6.3. From Cauchy-complete to complete

Theorem 5.6.2 (Archimedean and Cauchy-Complete Implies Complete)

Let $F$ be an ordered field that is Archimedean (Definition 4.2.2) and Cauchy-complete (Definition 5.6.1). Then $F$ is complete.

Idea. Given $A$ , we want a point $s$ that is an upper bound and below every upper bound. Trap it. Start with an interval $[l_0, u_0]$ whose right end is an upper bound of $A$ and whose left end is not. Halve it: if the midpoint is an upper bound, it becomes the new right end; if not, the new left end. Bisect and keep the invariant: right end an upper bound, left end not.

The right ends decrease and the left ends increase, and both stay within the current interval, whose length is $D/2^k$ . If that length goes to $0$ , the right ends form a Cauchy sequence, and Cauchy-completeness gives a limit $s$ . Then $s$ is an upper bound because every right end is, and it is the least one because left ends, which are not upper bounds, come arbitrarily close to it.

Step roadmap: ① the starting interval; ② the bisection, defined by a rule, and its invariants; ③ the lengths $D/2^k$ tend to $0$ ; ④ $(u_k)$ converges to some $s$ ; ⑤ $s$ is the supremum. Before reading on: which of these steps uses that $F$ is Archimedean?

Proof. Let $A \subseteq F$ be non-empty and bounded above.

Step 1: the starting interval. Fix $a_0 \in A$ [ $\mathrm{\exists E}$ ] and an upper bound $M$ of $A$ [ $\mathrm{\exists E}$ ]; each is one object, fixed once, and no choice is involved. Let $l_0 \mathrel{:=} a_0 - 1$ , $u_0 \mathrel{:=} M$ and $D \mathrel{:=} u_0 - l_0$ . Then $l_0 < a_0 \le M = u_0$ , so $D > 0$ ; $u_0$ is an upper bound of $A$ ; and $l_0$ is not, because $a_0 \in A$ and $a_0 > l_0$ .

Step 2: the bisection. Define $g \colon \mathbb{N} \times (F \times F) \to F \times F$ by $g\bigl(k, (l, u)\bigr) \mathrel{:=} \begin{cases} (l, c) & \text{if } c \text{ is an upper bound of } A , \\ (c, u) & \text{otherwise,} \end{cases} \qquad c \mathrel{:=} \frac{l + u}{2} .$ For each input exactly one case applies, so $g$ is a function, given by a rule. By Sets, Relations, and Cardinality, Theorem 2.3.1 (read on $\mathbb{N} = \omega$ through Corollary 1.7.3 (b)), with $X = F \times F$ and starting value $(l_0, u_0)$ , there is exactly one sequence $k \mapsto (l_k, u_k)$ with $(l_{k+1}, u_{k+1}) = g(k, (l_k, u_k))$ for every $k$ .

We prove by induction on $k$ that, for every $k \in \mathbb{N}$ :

(I1) $u_k$ is an upper bound of $A$ ;
(I2) $l_k$ is not an upper bound of $A$ ;
(I3) $u_k - l_k = D/2^k$ .

The base is Step 1, with $D/2^0 = D/1_F = D$ . Suppose (I1)–(I3) hold for $k$ , and let $c \mathrel{:=} (l_k + u_k)/2$ . Then $c - l_k = u_k - c = (u_k - l_k)/2 = D/(2^k \cdot 2) = D/2^{k+1}$ , by field arithmetic (Lemma 4.1.1 (b)) and Definition 4.2.1 (b). If $c$ is an upper bound, then $(l_{k+1}, u_{k+1}) = (l_k, c)$ : the right end $c$ is an upper bound, the left end $l_k$ is not, by (I2), and $c - l_k = D/2^{k+1}$ . Otherwise $(l_{k+1}, u_{k+1}) = (c, u_k)$ : the left end $c$ is not an upper bound, the right end $u_k$ is, by (I1), and $u_k - c = D/2^{k+1}$ . This proves (I1)–(I3) for $k + 1$ .

By (I3), $u_k - l_k = D/2^k > 0$ , so $l_k < c < u_k$ (Proposition 4.1.2 (b)); in either case $l_k \le l_{k+1}$ and $u_{k+1} \le u_k$ . By induction on $i$ , $l_k \le l_{k+i}$ and $u_{k+i} \le u_k$ for every $i \in \mathbb{N}$ , and every $j \ge k$ is $k + i$ for some $i$ (Proposition 1.6.3 (a)). So for $j \ge k$ , $l_k \le l_j < u_j \le u_k$ , and therefore

0 \le u_k - u_j \le u_k - l_k = \frac{D}{2^k} \qquad (j \ge k) .

(5.6.1)

Step 3: the lengths tend to $0$ . Let $\varepsilon \in F_{>0}$ . Since $F$ is Archimedean, there is $n \in \mathbb{N}$ with

\frac{D}{\varepsilon} < n \cdot 1_F .

(5.6.2)

Let $k \ge n$ . By Lemma 5.6.1 and Proposition 4.2.1 (b), $2^k \ge (k + 1) \cdot 1_F > k \cdot 1_F \ge n \cdot 1_F > D/\varepsilon > 0$ . By Proposition 2.5.2 (b), $1/2^k < (D/\varepsilon)^{-1} = \varepsilon/D$ (Lemma 4.1.1 (a)), and multiplying by $D > 0$ (Proposition 2.3.5 (c)) gives $D/2^k < \varepsilon$ . So $\left| D/2^k - 0 \right| < \varepsilon$ for every $k \ge n$ : the sequence $(D/2^k)_k$ is null.

Consequently $(u_k)$ is Cauchy in $F$ : for $\varepsilon$ and $n$ as above and $j, k \ge n$ , say $j \ge k$ (the other case is symmetric), Eq. 5.6.1 gives $\left| u_j - u_k \right| = \left| u_k - u_j \right| = u_k - u_j \le D/2^k < \varepsilon$ (Proposition 4.1.3 (b), Definition 4.1.1).

Steps 1–3 use only that $F$ is an Archimedean ordered field. Step 4 is the only one that uses Cauchy-completeness.

Step 4: the limit. Since $F$ is Cauchy-complete, $(u_k)$ converges; fix $s \in F$ with $u_k \to s$ [ $\mathrm{\exists E}$ ]. Since $l_k = u_k - D/2^k$ and $D/2^k \to 0$ , Theorem 4.4.3 (b) gives $l_k \to s - 0 = s$ .

Step 5: $s$ is the supremum. (S1): let $a \in A$ . By (I1), $a \le u_k$ for every $k$ , so $a \le s$ by Proposition 4.4.4 (b). So $s$ is an upper bound of $A$ .

(S2): let $b$ be an upper bound of $A$ , and suppose, for $\mathrm{\neg I}$ , that $b < s$ . Then $\varepsilon \mathrel{:=} s - b > 0$ , and since $l_k \to s$ there is $K$ with $\left| l_k - s \right| < \varepsilon$ for $k \ge K$ ; in particular $l_K > s - \varepsilon = b$ (Proposition 4.1.3 (d)). By (I2), $l_K$ is not an upper bound: some $a \in A$ has $a \not\le l_K$ (Logic and Proof, Proposition 6.2.3 (a)), that is, $a > l_K$ by totality (Proposition 4.1.2 (a)). Then $a > l_K > b$ , against $b$ being an upper bound. So $b < s$ is false, and $s \le b$ by (O1).

By (S1) and (S2), $s = \sup A$ (Sets, Relations, and Cardinality, Definition 2.6.5). Since $A$ was an arbitrary non-empty subset bounded above, $F$ is complete.

The answer to the prompt: Step 3, and only the line Eq. 5.6.2. The rest of Step 3 is algebra in $F$ and Lemma 5.6.1, which hold in every ordered field. Archimedes is what makes the halved lengths smaller than an arbitrary positive $\varepsilon$ ; without it, $D/2^k$ could stay above some positive element for every $k$ , and $(u_k)$ need not be Cauchy.

Each hypothesis has one job. Archimedes makes $(u_k)$ Cauchy (Step 3); Cauchy-completeness supplies the limit (Step 4); “non-empty” supplies a left end that is not an upper bound, and “bounded above” a right end that is one. The invariants (I1) and (I2) are spent in Step 5, one on each clause of the supremum.

Warning. A false conclusion: “every Cauchy-complete ordered field is complete”. Run the bisection without Archimedes. Steps 1, 2, 4 and 5 never mention it; the unjustified line is Eq. 5.6.2, “ $D/\varepsilon < n \cdot 1_F$ for some $n$ ”. In the non-Archimedean field $\mathbb{Q}(t)$ of Example (A Non-Archimedean Ordered Field) it fails for $D = 1$ and $\varepsilon = 1/t$ : every $2^k = (2^k) \cdot 1$ lies below $t$ , so $1/2^k > 1/t$ for every $k$ (Proposition 2.5.2 (b)), and the bisection lengths never get below the tolerance $1/t$ . (It shows only that the line fails, not that the conclusion does.)

Remark. Not proved here. There are ordered fields that are Cauchy-complete and not Archimedean, for instance a field of formal Laurent series in a positive infinitesimal $t$ . So the conclusion of the warning is false, and the Archimedean hypothesis of Theorem 5.6.2 cannot be dropped. This book does not prove that such a field exists, and nothing in it depends on one; Analysis on the Real Line, Chapter 11 returns to the question when it compares the forms of completeness.

5.6.4. The constructed reals

Theorem 5.6.3 (The Constructed Reals Form a Complete Ordered Field)

The set $\mathbb{R}$ of Definition 5.2.1, with the operations of Definition 5.2.2 and the order of Definition 5.3.2, is a complete ordered field. The map $\kappa \colon \mathbb{Q} \to \mathbb{R}$ of Definition 5.4.1 is injective, preserves $+$ , $\cdot$ and $<$ , and has dense image: between any two real numbers $x < y$ there is $\kappa(q)$ with $q \in \mathbb{Q}$ .

Proof. $\mathbb{R}$ is an ordered field by Theorem 5.3.3, Archimedean by Theorem 5.4.2, and Cauchy-complete by Theorem 5.5.1. By Theorem 5.6.2 it is complete. The statements about $\kappa$ are Theorem 5.4.1 (a), (b) (injectivity is part of (b)) and Theorem 5.4.3.

This ends the construction begun with the axioms of set theory in Chapter 1: $\mathbb{N}$ , then $\mathbb{Z}$ and $\mathbb{Q}$ as classes of pairs, now $\mathbb{R}$ as classes of Cauchy sequences. No property of $\mathbb{R}$ was assumed.

Quick check. Run the bisection of the proof of Theorem 5.6.2 in $\mathbb{R}$ on $A \mathrel{:=} \{ q \in \mathbb{Q} : q^2 < 2 \}$ , viewed as a subset of $\mathbb{R}$ , with $a_0 = 1$ and $M = 2$ . List $(l_k, u_k)$ for $k = 0, 1, 2, 3$ .

Solution. $l_0 = a_0 - 1 = 0$ and $u_0 = 2$ . Two tests decide the midpoints. An element $c > 0$ with $c^2 \ge 2$ is an upper bound of $A$ : if some $q \in A$ had $q > c$ , then $q^2 > c^2 \ge 2$ (Proposition 2.3.5 (g)), against $q^2 < 2$ . An element exceeded by some member of $A$ is not an upper bound; we use the member $7/5$ , which is in $A$ because $(7/5)^2 = 49/25 < 2$ .

$k = 0 \to 1$ : $c = 1$ ; $7/5 \in A$ and $7/5 > 1$ , so $1$ is not an upper bound: $(l_1, u_1) = (1, 2)$ .
$k = 1 \to 2$ : $c = 3/2$ ; $(3/2)^2 = 9/4 \ge 2$ , so $3/2$ is an upper bound: $(l_2, u_2) = (1, 3/2)$ .
$k = 2 \to 3$ : $c = 5/4$ ; $7/5 \in A$ and $7/5 > 5/4$ , so $5/4$ is not an upper bound: $(l_3, u_3) = (5/4, 3/2)$ .

So the pairs are $(0, 2)$ , $(1, 2)$ , $(1, 3/2)$ , $(5/4, 3/2)$ , and $u_3 - l_3 = 1/4 = D/2^3$ with $D = 2$ , as (I3) says.

5.6.5. What we built, and what comes next

The table collects what the chapter proved about $\mathbb{R}$ , beside the status of the same property in $\mathbb{Q}$ .

Property	In $\mathbb{R}$	In $\mathbb{Q}$
ordered field	yes: Theorem 5.3.3	yes: Theorem 2.5.1
Archimedean	yes: Theorem 5.4.2	yes: Theorem 2.5.3
an element whose square is $2$	yes: Example (The Class of the Newton Sequence)	no: Theorem 2.6.1
Cauchy-complete	yes: Theorem 5.5.1	no: Theorem 4.6.1
complete	yes: Theorem 5.6.3	no: Theorem 2.6.2

The first two rows are shared; the last three are what the construction was for.

Several chapters build on this one. Chapter 6 proves that any two complete ordered fields are isomorphic, by exactly one order-preserving field isomorphism; so “the” real numbers are well defined, and no theorem about them depends on how they were built. The optional Chapter 7 builds a complete ordered field from Dedekind cuts, sets of rationals instead of sequences, and by Chapter 6 it is a copy of this one. Analysis on the Real Line, Chapter 1 starts from the axioms of a complete ordered field; the theorem above gives those axioms a model, so they cannot contradict each other unless the set theory of Chapter 1, in which $\mathbb{Q}$ was built, already does. Algebraic Preliminaries, Chapter 1 builds the complex numbers on this $\mathbb{R}$ . And Metric and Topological Spaces, Chapter 2 runs the construction of this chapter for an arbitrary metric space, as its completion.

Second readingHistory

Charles Méray published a construction of the irrational numbers from convergent sequences of rationals in 1869. Georg Cantor gave an equivalent construction from fundamental sequences, our Cauchy sequences, in 1872, the year in which Richard Dedekind published his construction by cuts.

5.6.6. Exercises

A. Check your understanding

Exercise (A1)

These questions are about the proof of Theorem 5.6.2 and the definition of a complete ordered field.

(a) Where in the proof is the invariant “ $l_k$ is not an upper bound” used, and where “ $u_k$ is an upper bound”?
(b) Why does the proof start with $l_0 = a_0 - 1$ , and not with $l_0 = a_0$ ?
(c) State the idea of the proof in two sentences.
(d) Write “ $F$ is complete” in symbols, and form its negation.

Solution.

(a) “Not an upper bound”, (I2), is used in Step 5 for (S2): a left end $l_K$ above a supposed smaller upper bound $b$ yields an element of $A$ above $b$ . “Upper bound”, (I1), is used in Step 5 for (S1): every element of $A$ lies below every $u_k$ , hence below their limit. (Both are also carried through the induction of Step 2, which is what keeps them true.)
(b) The left end must not be an upper bound, and $a_0$ might be one: for $A = \{a_0\}$ , the element $a_0$ is an upper bound (even the supremum), and (I2) would fail at $k = 0$ . Moving one unit left gives $a_0 - 1 < a_0 \in A$ , which is never an upper bound.
(c) Halve an interval repeatedly by a rule that keeps its right end an upper bound of $A$ and its left end not one; Archimedes makes the lengths tend to $0$ , so the right ends are Cauchy and converge. Their limit is an upper bound because the right ends are, and it is the least one because the left ends, which are not upper bounds, converge to it too.
(d) With $\mathrm{ub}(u)$ for $\forall a \in A \ a \le u$ , “complete” is the display in Definition 5.6.1. Its negation (Logic and Proof, Proposition 6.2.1, Logic and Proof, Proposition 6.2.3, Logic and Proof, Proposition 6.2.2, Logic and Proof, Proposition 2.5.5 (d), and $\neg(x \le y)$ as $y < x$ by (O1)): $\begin{aligned} &\exists A \subseteq F \ \bigl( A \ne \emptyset \wedge \exists u \in F \ \mathrm{ub}(u) \wedge \forall s \in F \\ &\qquad \bigl( \exists a \in A \ s < a \ \vee \ \exists u \in F \ (\mathrm{ub}(u) \wedge u < s) \bigr) \bigr) . \end{aligned}$ Some non-empty set bounded above defeats every candidate $s$ , by an element above it or an upper bound below it.

B. Practice

Exercise (B1)

Prove that every non-empty subset $A \subseteq \mathbb{R}$ that is bounded below has an infimum in $\mathbb{R}$ (Sets, Relations, and Cardinality, Definition 2.6.5), and that $\inf A = -\sup(-A)$ , where $-A \mathrel{:=} \{ -a : a \in A \}$ .

Solution. Let $b$ be a lower bound of $A$ . The set $-A$ is non-empty, and $-b$ is an upper bound of it: for $a \in A$ , $b \le a$ gives $-a \le -b$ (Proposition 2.3.5 (a)). By Theorem 5.6.3, $s \mathrel{:=} \sup(-A)$ exists.

We show that $-s$ is the infimum of $A$ . Lower bound: for $a \in A$ , $-a \in -A$ , so $-a \le s$ and $-s \le a$ . Greatest: let $c$ be a lower bound of $A$ . As for $b$ , $-c$ is an upper bound of $-A$ , so $s \le -c$ by (S2), that is, $c \le -s$ . Hence $\inf A = -s = -\sup(-A)$ .

Exercise (B2)

Let $A \mathrel{:=} \{ 1 - 1/(n + 1) : n \in \mathbb{N} \} \subseteq \mathbb{R}$ . Prove that $\sup A = 1$ , and decide whether $1 \in A$ .

Solution. Upper bound. $1/(n + 1) > 0$ (Proposition 2.5.2 (a)), so $1 - 1/(n + 1) < 1$ for every $n$ .

Least. Let $b < 1$ . Then $1 - b \in \mathbb{R}_{>0}$ , and Corollary 5.4.4 (a) gives $N \in \mathbb{Z}_{>0}$ with $1/n < 1 - b$ for every $n \ge N$ . With $n \mathrel{:=} N$ , the element $1 - 1/(N + 1)$ of $A$ satisfies $1/(N + 1) < 1/N < 1 - b$ , so $1 - 1/(N + 1) > b$ , and $b$ is not an upper bound. By (O1), every upper bound $u$ satisfies $u \ge 1$ .

So $\sup A = 1$ , and $1 \notin A$ , since every element of $A$ is $< 1$ . The supremum exists here without Theorem 5.6.3: we exhibited it.

C. Going deeper

Exercise (C1: Exit check: completeness from Cauchy completeness)

Let $F$ be an ordered field that is Archimedean and Cauchy-complete. Prove that every non-empty subset of $F$ that is bounded above has a supremum in $F$ , and name the line of your proof that uses the Archimedean property.

Solution. Let $A \ne \emptyset$ be bounded above; fix $a_0 \in A$ and an upper bound $M$ . Put $l_0 \mathrel{:=} a_0 - 1$ (not an upper bound, since $a_0 > l_0$ ), $u_0 \mathrel{:=} M$ (an upper bound), $D \mathrel{:=} u_0 - l_0 > 0$ .

Bisection. By the recursion theorem, with the step “replace $u$ by $c = (l + u)/2$ if $c$ is an upper bound, else replace $l$ by $c$ ”, define $(l_k, u_k)$ . By induction: $u_k$ is an upper bound, $l_k$ is not, and $u_k - l_k = D/2^k$ . (Each case keeps both invariants and halves the length, as in Step 2 of the proof.) Hence $l_k$ is non-decreasing, $u_k$ is non-increasing, and $0 \le u_k - u_j \le D/2^k$ for $j \ge k$ .

Cauchy. Let $\varepsilon \in F_{>0}$ . Archimedes gives $n \in \mathbb{N}$ with $D/\varepsilon < n \cdot 1_F$ (this is the line). For $k \ge n$ , $2^k \ge (k + 1) \cdot 1_F > n \cdot 1_F > D/\varepsilon$ by Lemma 5.6.1, so $D/2^k < \varepsilon$ , and $\left| u_j - u_k \right| < \varepsilon$ for $j, k \ge n$ .

Limit. Cauchy-completeness gives $s$ with $u_k \to s$ ; and $l_k = u_k - D/2^k \to s$ , since $D/2^k \to 0$ .

Supremum. For $a \in A$ , $a \le u_k$ for all $k$ , so $a \le s$ (Proposition 4.4.4 (b)). If an upper bound $b$ had $b < s$ , some $l_K > b$ (as $l_k \to s$ , with tolerance $s - b$ ); $l_K$ is not an upper bound, so some $a \in A$ exceeds $l_K$ , hence exceeds $b$ : impossible. So $s \le b$ for every upper bound $b$ , and $s = \sup A$ .

Marking scheme. (10 points) - 2: a starting left end that is not an upper bound and a right end that is, each justified (in particular $a_0 - 1$ , not $a_0$ ). - 2: the bisection defined by a rule, with the invariants stated and proved by induction. - 2: $(u_k)$ Cauchy, with the Archimedean property named at the step where $D/2^k$ is made smaller than $\varepsilon$ . - 2: the limit $s$ is an upper bound, by the order-preservation of limits. - 2: $s$ is the least upper bound, through $l_k \to s$ and “ $l_k$ is not an upper bound”. Fatal errors (0 for the step): claiming $s \in A$ ; “ $1/2^k \to 0$ ” asserted in a general $F$ without Archimedes; midpoints or points of $A$ “chosen” at each step with no rule. A route through monotone convergence earns the Cauchy and limit points only if monotone convergence is first proved from Cauchy-completeness and Archimedes in $F$ . A dyadic-grid route ( $u_k \mathrel{:=} m_k/2^k$ , $m_k$ the least integer making it an upper bound) maps point for point, with $u_k - 1/2^k$ for $l_k$ and Archimedes also for the existence of $m_k$ .

Exercise (C2: The rationals are not complete, by bisection)

Run the bisection of the proof of Theorem 5.6.2 inside $F = \mathbb{Q}$ , on $A \mathrel{:=} \{ q \in \mathbb{Q} : q^2 < 2 \}$ with $a_0 = 1$ and $M = 2$ , so $l_0 = 0$ and $D = 2$ .

(a) Explain why Steps 1–3 of that proof apply in $\mathbb{Q}$ , so that $(u_k)$ is Cauchy in $\mathbb{Q}$ and $D/2^k \to 0$ in $\mathbb{Q}$ .
(b) Prove: if $A$ had a supremum $s$ in $\mathbb{Q}$ , then $u_k \to s$ in $\mathbb{Q}$ .
(c) Prove that $(u_k)$ has no limit in $\mathbb{Q}$ . (Show $l_k^2 < 2 \le u_k^2$ .)
(d) Conclude that $A$ has no supremum in $\mathbb{Q}$ . Why is “ $(u_k)$ is Cauchy with no rational limit” not enough on its own for this?
(e) In $\mathbb{R}$ , show that $u_k \to r$ , the real number of Example (The Class of the Newton Sequence).

Solution (Hint 1). For (b), compare $s$ with $u_k$ and with $l_k$ , using (I1), (I2) and (S2). For (c), the left ends are below some element of $A$ .

Solution (Hint 2). For $u_k^2 \ge 2$ in (c): suppose $u_k^2 < 2$ , and look for a rational $h$ with $0 < h \le 1$ and $(u_k + h)^2 < 2$ .

Solution.

(a) The proof states that Steps 1–3 use only that the field is an Archimedean ordered field, and $\mathbb{Q}$ is one (Theorem 2.5.1, Theorem 2.5.3). Lemma 5.6.1 holds in $\mathbb{Q}$ too. Step 1 applies: $1 \in A$ as $1^2 < 2$ , and $2$ bounds $A$ , as $q > 2 \ge 0$ gives $q^2 > 4$ (Proposition 2.3.5 (g)). So the invariants (I1)–(I3) hold, $(D/2^k)$ is null in $\mathbb{Q}$ , and $(u_k)$ is Cauchy in $\mathbb{Q}$ . Step 4 is where the proof would need Cauchy-completeness, which $\mathbb{Q}$ lacks.
(b) Suppose $s = \sup A$ in $\mathbb{Q}$ . Each $u_k$ is an upper bound (I1), so $s \le u_k$ by (S2). Each $l_k$ is not an upper bound (I2), so some $a \in A$ has $l_k < a \le s$ . Hence $0 \le u_k - s < u_k - l_k = D/2^k$ for every $k$ . By the squeeze, Proposition 4.4.4 (c), with lower sequence $0$ and the null upper sequence $(D/2^k)$ , $u_k - s \to 0$ , so $u_k \to s$ (Proposition 4.3.3).
(c) Left ends. $l_k \ge l_0 = 0$ , since the left ends are non-decreasing (Step 2). By (I2) some $a \in A$ has $a > l_k \ge 0$ , so $l_k^2 < a^2 < 2$ (Proposition 2.3.5 (g)).

Right ends. $u_k > l_k \ge 0$ . Suppose $u_k^2 < 2$ , and let $h \mathrel{:=} \min\{1, (2 - u_k^2)/(2(2u_k + 1))\}$ , a positive rational ( $2u_k + 1 > 0$ ). Since $h \le 1$ , $h^2 \le h$ , and $\begin{aligned} (u_k + h)^2 &= u_k^2 + 2u_k h + h^2 \le u_k^2 + (2u_k + 1) h \\ &\le u_k^2 + \frac{2 - u_k^2}{2} < 2 . \end{aligned}$ So $u_k + h \in A$ and $u_k + h > u_k$ , against (I1). Hence $u_k^2 \ge 2$ .

No limit. Suppose $u_k \to L \in \mathbb{Q}$ . Then $l_k = u_k - D/2^k \to L$ (Theorem 4.4.3 (b)), and by the product law (c), $u_k^2 \to L^2$ and $l_k^2 \to L^2$ . By Proposition 4.4.4 (b), $u_k^2 \ge 2$ gives $L^2 \ge 2$ , and $l_k^2 < 2$ gives $L^2 \le 2$ . So $L^2 = 2$ , against Theorem 2.6.1.
(d) By (b) and (c), a supremum $s \in \mathbb{Q}$ would be a rational limit of $(u_k)$ , and there is none. So $A$ has no supremum in $\mathbb{Q}$ : $\mathbb{Q}$ is not complete. A Cauchy sequence with no rational limit shows only that $\mathbb{Q}$ is not Cauchy-complete; part (b) is the link between the two properties, and it uses the invariants of the bisection. Section 2.6 proved the same conclusion (Theorem 2.6.2 (a)) directly, by improving each rational candidate; here a sequence finds the gap.
(e) Run the bisection in $\mathbb{R}$ on $A$ , viewed as a subset of $\mathbb{R}$ . A rational $c$ is an upper bound of $A$ in $\mathbb{Q}$ if and only if it is one in $\mathbb{R}$ ( $\kappa$ preserves and reflects order, Theorem 5.4.1 (b)), so the midpoint tests give the same answers, and the sequence $(l_k, u_k)$ is the same. By the proof of Theorem 5.6.2 in $\mathbb{R}$ (Steps 4 and 5), $u_k \to \sup A$ in $\mathbb{R}$ . It remains to see $\sup A = r$ . For $q \in \mathbb{Q}$ : if $q \ge r$ , then $q > 0$ and $q^2 \ge r^2 = 2$ (Proposition 2.3.5 (g) in $\mathbb{R}$ , with $r > 0$ ), so $q \notin A$ ; hence $r$ is an upper bound. If $t < r$ in $\mathbb{R}$ , Theorem 5.4.3 gives a rational $q$ with $\max\{t, 0\} < q < r$ ; then $0 < q < r$ gives $q^2 < 2$ , so $q \in A$ and $q > t$ : $t$ is not an upper bound. So $\sup A = r$ , and $u_k \to r$ .

Marking scheme. (10 points) - 2: (a), with the Archimedean property of $\mathbb{Q}$ cited and Cauchy-completeness located in Step 4. - 3: (b), the two invariants used to get $l_k < s \le u_k$ , and the squeeze. - 3: (c), both bounds $l_k^2 < 2 \le u_k^2$ justified (the second by a rational $h$ ), then the limit laws and Theorem 2.6.1. - 2: (d), the conclusion, with the difference between “not Cauchy-complete” and “not complete” stated. Part (e) is not marked. Fatal errors (0 for the step): using $\sqrt 2$ as a rational or as a real number in (b)–(d); concluding (d) from (c) alone.

R. Review

Exercise (R1)

Let $F$ be an ordered field, $(a_n)$ a sequence in $F$ , and $L \in F$ with $L > 0$ and $a_n \to L$ . Prove that $a_n \ge L/2$ for every sufficiently large $n$ .

Solution. By Definition 4.3.2 with $\varepsilon \mathrel{:=} L/2 \in F_{>0}$ (Proposition 4.1.2 (b)), there is $N$ with $\left| a_n - L \right| < L/2$ for every $n \ge N$ . For such $n$ , Proposition 4.1.3 (d) gives $-L/2 < a_n - L$ , so $a_n > L - L/2 = L/2$ ; in particular $a_n \ge L/2$ .

This is the second half of Lemma 4.4.2. It is also the shape of Theorem 4.5.4, in the case where the limit is known: a sequence with a positive limit is eventually above a fixed positive element, which is what “positive” meant for Cauchy sequences in Section 5.3.

Exercise (R2)

On $X \mathrel{:=} \mathbb{Z} \times \mathbb{Z}_{>0}$ , let $(p, q) \sim (p', q')$ mean $pq' = p'q$ . Show that the condition “ $p \ge q$ ” on a pair gives a well-defined property of classes: if $(p, q) \sim (p', q')$ , then $p \ge q$ if and only if $p' \ge q'$ . Then show that “ $p \ge 2$ ” does not give a well-defined property of classes.

Solution. These are the classes of Definition 2.4.1, and the move is representatives, then independence: a property stated on a representative is a property of the class only if equivalent representatives agree. By Theorem 2.2.1 (c), with $S \mathrel{:=} \{ (p, q) \in X : p \ge q \}$ , it suffices to check one direction (the relation is symmetric).

Let $pq' = p'q$ with $q, q' > 0$ , and suppose $p \ge q$ . Multiplying by $q' > 0$ (Proposition 2.3.5 (c), or equality), $pq' \ge qq'$ , that is, $p'q \ge q'q$ . If $p' < q'$ , then $p'q < q'q$ by Proposition 2.3.5 (c), since $q > 0$ , a contradiction by (O1). So $p' \ge q'$ . In $\mathbb{Q}$ , the property says $[(p, q)] \ge 1$ , by the comparison formula of Theorem 2.5.1 (a).

“ $p \ge 2$ ” is not well defined: $(1, 2) \sim (2, 4)$ , since $1 \cdot 4 = 2 \cdot 2$ , but $1 \not\ge 2$ while $2 \ge 2$ . One class, two verdicts: the hypothesis of Theorem 2.2.1 (c) fails. (The test “ $p \ge 1$ ” would pass, but only because for an integer it says $p > 0$ (Theorem 2.3.4 (c)), the positivity test of Definition 2.5.1.)

Exercise (R3)

Prove that $\mathbb{R}$ is uncountable. For $s \in \{0, 1\}^{\mathbb{N}}$ , consider the rationals $S_k(s) \mathrel{:=} \sum_{i=0}^{k} \frac{2 s_i}{3^{i+1}} \qquad (k \in \mathbb{N}) ,$ and show that $s \mapsto [(S_k(s))_k]$ is an injection $\{0, 1\}^{\mathbb{N}} \to \mathbb{R}$ .

Solution. (i) The sums. The powers $3^{i}$ are those of Definition 4.2.1 in $\mathbb{Q}$ , with $3^{i+1} = 3^i \cdot 3$ . The sum is defined by Sets, Relations, and Cardinality, Theorem 2.3.1 with $X = \mathbb{Q}$ : $S_0(s) \mathrel{:=} 2s_0/3$ and $S_{k+1}(s) \mathrel{:=} S_k(s) + 2s_{k+1}/3^{k+2}$ .

(ii) A tail bound. For $m \ge k$ ,

0 \le S_m(s) - S_k(s) \le \frac{1}{3^{k+1}} - \frac{1}{3^{m+1}} .

(5.6.3)

By Logic and Proof, Axiom 4.2.1 on $m - k$ (base $P(0)$ , $m = k$ : $0 \le 0 \le 0$ ): passing from $m$ to $m + 1$ adds $2s_{m+1}/3^{m+2}$ , which lies between $0$ and $2/3^{m+2}$ , and $-1/3^{m+1} + 2/3^{m+2} = -3/3^{m+2} + 2/3^{m+2} = -1/3^{m+2}$ .

So $\left| S_m(s) - S_k(s) \right| < 1/3^{k+1}$ for $m \ge k$ . Also $3^{k+1} \ge 2^{k+1} \ge (k + 2) \cdot 1$ : the first by induction ( $3^0 = 2^0$ , and $3^{i+1} = 3^i \cdot 3 \ge 2^i \cdot 2$ by Proposition 4.1.2 (d), with $2^i > 0$ ), the second by Lemma 5.6.1 with $F = \mathbb{Q}$ . So $1/3^{k+1} < 1/(k + 1)$ . Given $\varepsilon \in \mathbb{Q}_{>0}$ , Corollary 2.5.4 gives $N \in \mathbb{Z}_{>0}$ with $1/n < \varepsilon$ for $n \ge N$ ; for $m, k \ge N$ , say $m \ge k$ , $\left| S_m(s) - S_k(s) \right| < 1/(k + 1) < \varepsilon$ . So $(S_k(s))_k \in \mathcal{C}$ .

(iii) Different sequences give different classes. Let $s \ne t$ . The set $\{ i \in \mathbb{N} : s_i \ne t_i \}$ is non-empty and bounded below by $0$ , so it has a least element $j$ (Proposition 2.3.6). Say $s_j = 1$ and $t_j = 0$ . Since $s_i = t_i$ for $i < j$ , induction gives $S_{j-1}(s) = S_{j-1}(t)$ when $j \ge 1$ , so $S_j(s) - S_j(t) = 2/3^{j+1}$ (also when $j = 0$ ). For $k \ge j$ , by Eq. 5.6.3 applied to $s$ and to $t$ , $\begin{aligned} S_k(s) - S_k(t) &= \frac{2}{3^{j+1}} + \bigl( S_k(s) - S_j(s) \bigr) - \bigl( S_k(t) - S_j(t) \bigr) \\ &\ge \frac{2}{3^{j+1}} + 0 - \frac{1}{3^{j+1}} = \frac{1}{3^{j+1}} . \end{aligned}$ So $S(s) - S(t)$ is eventually $\ge \delta \mathrel{:=} 1/3^{j+1} \in \mathbb{Q}_{>0}$ : it is positive (Definition 5.3.1), so $[S(t)] < [S(s)]$ (Definition 5.3.2, Definition 5.2.2), and in particular $[S(s)] \ne [S(t)]$ . The map $\Phi \colon s \mapsto [(S_k(s))_k]$ is injective.

(iv) Uncountable. If $\mathbb{R}$ were countable, there would be an injection $g \colon \mathbb{R} \to \mathbb{N}$ (Sets, Relations, and Cardinality, Theorem 3.2.2, (i) $\Rightarrow$ (ii)). Then $g \circ \Phi \colon \{0, 1\}^{\mathbb{N}} \to \mathbb{N}$ would be injective (Sets, Relations, and Cardinality, Theorem 1.4.4 (a)), so $\{0, 1\}^{\mathbb{N}}$ would be countable ((ii) $\Rightarrow$ (i)), against Sets, Relations, and Cardinality, Theorem 3.4.1.

The method is that of Sets, Relations, and Cardinality, Chapter 3: an injection from a set known to be uncountable. (The route through Sets, Relations, and Cardinality, Proposition 3.5.2 is not taken: its ( $\Leftarrow$ ) direction uses choice.)

Exercise (R4)

Let $x \in \mathbb{R}$ . Prove that there is a strictly increasing sequence $(q_k)$ of rationals with $q_k \to x$ in $\mathbb{R}$ .

Solution. The tool is Sets, Relations, and Cardinality, Theorem 2.3.1 with a step given by a rule, on the set $X \mathrel{:=} \{ q \in \mathbb{Q} : q < x \}$ . Integer parts (Proposition 4.2.4 with $F = \mathbb{R}$ , Archimedean by Theorem 5.4.2; unique) supply the rule.

Start. Let $p$ be the integer part of $x$ , and $q_0 \mathrel{:=} p - 1$ . Then $q_0 < p \le x$ , so $q_0 \in X$ .

Step. For $k \in \mathbb{N}$ and $q \in X$ , let $L \mathrel{:=} \max\{q, x - 1/(k + 1)\}$ , a real number with $L < x$ . Let $n$ be the integer part of $2/(x - L)$ , plus $1$ : a positive integer with $n > 2/(x - L)$ , so $2/n < x - L$ (Proposition 2.5.2 (b)). Let $m$ be the integer part of $n x$ , and put $g(k, q) \mathrel{:=} (m - 1)/n$ . From $m \le nx < m + 1$ , dividing by $n$ , $L < x - \frac{2}{n} < \frac{m - 1}{n} \le x - \frac{1}{n} < x .$ So $g(k, q) \in X$ , and $g \colon \mathbb{N} \times X \to X$ is a function: each step is a formula, made unambiguous by the uniqueness of integer parts. By Sets, Relations, and Cardinality, Theorem 2.3.1 there is exactly one sequence with $q_{k+1} = g(k, q_k)$ .

Properties. By the display, $q_{k+1} > L \ge q_k$ , so the sequence is strictly increasing; and $x - 1/(k + 1) \le L < q_{k+1} < x$ , so $\left| q_{k+1} - x \right| < 1/(k + 1)$ . Given $\varepsilon \in \mathbb{R}_{>0}$ , Corollary 5.4.4 (a) gives $N$ with $1/j < \varepsilon$ for $j \ge N$ ; for $k \ge N + 1$ , $\left| q_k - x \right| < 1/k < \varepsilon$ . So $q_k \to x$ .

Why the look-alikes fail. The terms of a representative of $x$ converge to $x$ (Theorem 5.4.5) but need not increase. The approximants $m_k/(k + 1)$ of Section 5.5 are $\le x$ but not always strictly increasing (for $x = 0$ they are all $0$ ). The rational between two reals from the proof of Theorem 5.4.3 is a midpoint of terms of representatives at thresholds fixed by $\exists$ E: it is not given by a rule in the data $(k, q)$ , so it cannot serve as a recursion step. And “at each step take some rational between $L$ and $x$ ” makes one pick for each $k$ with no rule, an unflagged use of Sets, Relations, and Cardinality, Axiom 3.3.1 (compare Example (Picking Representatives Is a Use of Choice)).