5.5 Every Cauchy Sequence of Reals Converges

We built $\mathbb{R}$ to fill the holes in $\mathbb{Q}$ : the Newton sequence is Cauchy in $\mathbb{Q}$ and has no rational limit (Theorem 4.6.1), and in $\mathbb{R}$ it converges to the class it represents (Theorem 5.4.5, Example (The Class of the Newton Sequence)). Could $\mathbb{R}$ have holes of its own, Cauchy sequences of real numbers crowding around nothing? If so, the construction would have to be repeated, with Cauchy sequences of reals in place of Cauchy sequences of rationals, and perhaps again after that. This section proves that it need not be: every Cauchy sequence in $\mathbb{R}$ converges in $\mathbb{R}$ . The proof builds the limit from rationals, by a rule, and so uses no axiom of choice.

Throughout, $F = \mathbb{R}$ whenever a result of Chapter 4 is applied, which is legitimate because $\mathbb{R}$ is an ordered field (Theorem 5.3.3). We use the identification of Section 5.4: a rational $q$ also denotes the real number $\kappa(q)$ (Definition 5.4.1). Where an inequality is carried from $\mathbb{R}$ back to $\mathbb{Q}$ , we write $\kappa$ out, because that step is where the proof must cite Theorem 5.4.1.

5.5.1. The question

A sequence $(x_k)_{k \in \mathbb{N}}$ in $\mathbb{R}$ is Cauchy in $\mathbb{R}$ (Definition 4.5.1 with $F = \mathbb{R}$ ) if for every $\varepsilon \in \mathbb{R}_{>0}$ there is $K \in \mathbb{N}$ with $\left| x_j - x_k \right| < \varepsilon$ for all $j, k \ge K$ . By Corollary 5.4.4 (b), it is enough to test the tolerances $1/n$ with $n \in \mathbb{Z}_{>0}$ , and the same holds for convergence. So the tolerances may as well be rational; the terms $x_k$ , however, are real numbers, that is, classes of Cauchy sequences of rationals (Definition 5.2.1).

We want a real number $x$ with $x_k \to x$ . A real number is a class $[a]$ with $a \in \mathcal{C}$ (Definition 5.1.1), so we need a Cauchy sequence of rationals that “is” the limit. Where would its terms come from? The data are the classes $x_0, x_1, x_2, \dots$ , each of them an infinite set of sequences.

5.5.2. The theorem

Theorem 5.5.1 (The Constructed Reals Are Cauchy-Complete)

Every Cauchy sequence $(x_k)_{k \in \mathbb{N}}$ in $\mathbb{R}$ (Definition 4.5.1, $F = \mathbb{R}$ ) converges in $\mathbb{R}$ (Definition 4.3.2, $F = \mathbb{R}$ ).

Try it first (ten minutes): given a Cauchy sequence of reals, which Cauchy sequence of rationals would you build, and why would its class be the limit?

Idea. The obvious candidate is a diagonal. Each $x_k$ has representatives; take one, $a^{(k)} \in \mathcal{C}$ with $[a^{(k)}] = x_k$ , for each $k$ , and use the diagonal terms $a^{(k)}_k$ . This attempt meets two separate obstacles.

No control. A representative may begin with any finite list of rationals and still represent $x_k$ (Example (Finite Changes and Shifts)). Its $k$ -th term may be far from $x_k$ , and the diagonal terms need not settle down at all. Exercise C2 below turns this into a counterexample.
No rule. “Take one representative for each $k$ ” picks one element from each of infinitely many sets, with no rule saying which. That is an instance of the axiom of choice (Sets, Relations, and Cardinality, Axiom 3.3.1), which the construction of $\mathbb{R}$ has not used so far.

One device removes both: replace $x_k$ by a single rational $q_k$ within $1/(k + 1)$ of it, named by a formula. The plan has three steps.

① The $q_k$ form a member of $\mathcal{C}$ . Compare $q_j$ with $q_k$ through the reals $x_j$ and $x_k$ : $\left| q_j - q_k \right| \le \left| q_j - x_j \right| + \left| x_j - x_k \right| + \left| x_k - q_k \right|$ . The outer two are small once $j, k$ are large, by the choice of the approximant; the middle one is small because $(x_k)$ is Cauchy. Give each a third of $\varepsilon$ .

② Its class is a candidate. Let $x \mathrel{:=} [(q_k)_k]$ . A term approximates its class (Theorem 5.4.5), so $q_k \to x$ in $\mathbb{R}$ .

③ The candidate is the limit. $x_k$ is near $q_k$ , which is near $x$ : give each half of the tolerance.

The tolerance in ① must be rational, since membership of $\mathcal{C}$ is tested with $\varepsilon \in \mathbb{Q}_{>0}$ (Definition 5.1.1); the triangle inequality, however, is used in $\mathbb{R}$ , where the $x_k$ live. Step 1 of the proof ends by carrying the inequality back to $\mathbb{Q}$ through $\kappa$ (Theorem 5.4.1). The formula: $q_k \mathrel{:=} m_k/(k + 1)$ , where $m_k$ is the integer part of $(k + 1) x_k$ in the Archimedean field $\mathbb{R}$ . Before reading on: why must $m_k$ be the integer part, and not just some integer with $m_k \le (k + 1) x_k < m_k + 1$ ?

Proof. Let $(x_k)$ be a Cauchy sequence in $\mathbb{R}$ .

Step 0: the approximants. For $k \in \mathbb{N}$ , let $m_k \in \mathbb{Z}$ be the integer part of $(k + 1) x_k$ in $\mathbb{R}$ (Proposition 4.2.4 with $F = \mathbb{R}$ , which is Archimedean by Theorem 5.4.2; there $\iota_{\mathbb{R}} = \kappa$ by Theorem 5.4.1 (d)), and let $q_k \mathrel{:=} m_k/(k + 1) \in \mathbb{Q}$ . Since the integer part is unique, $k \mapsto q_k$ is a function $\mathbb{N} \to \mathbb{Q}$ (Sets, Relations, and Cardinality, Definition 1.4.1); no use of Sets, Relations, and Cardinality, Axiom 3.3.1 is made. Multiplying $m_k \le (k + 1) x_k < m_k + 1$ by the positive element $1/(k + 1)$ (Proposition 2.5.2 (a), Proposition 2.3.5 (c)), and using $\kappa(m_k)\kappa(k + 1)^{-1} = \kappa(q_k)$ (Theorem 5.4.1 (a), (c)), we get

0 \le x_k - \kappa(q_k) < \kappa\Bigl(\frac{1}{k + 1}\Bigr) \qquad \text{for every } k \in \mathbb{N} .

(5.5.1)

Step 1: $(q_k) \in \mathcal{C}$ . Let $\varepsilon \in \mathbb{Q}_{>0}$ . By Corollary 2.5.4 there is $K_1 \in \mathbb{Z}_{>0}$ with $1/m < \varepsilon/3$ for every integer $m \ge K_1$ ; for $k \ge K_1$ , the integer $k + 1$ is $\ge K_1$ , so $1/(k + 1) < \varepsilon/3$ . Next, $\kappa(\varepsilon/3) \in \mathbb{R}_{>0}$ by Theorem 5.4.1 (b), since $\varepsilon/3 > 0$ and $\kappa(0) = 0$ . As $(x_k)$ is Cauchy in $\mathbb{R}$ , there is $K_2 \in \mathbb{N}$ with $\left| x_j - x_k \right| < \kappa(\varepsilon/3)$ for all $j, k \ge K_2$ ; fix one such $K_2$ [ $\mathrm{\exists E}$ ], one object for this one $\varepsilon$ . Let $K \mathrel{:=} \max\{K_1, K_2\}$ ; it depends on $\varepsilon$ (and on the sequence) only.

Let $j, k \ge K$ . By Eq. 5.5.1 and Theorem 5.4.1 (b), $\left| x_j - \kappa(q_j) \right| < \kappa(1/(j + 1)) < \kappa(\varepsilon/3)$ , and likewise for $k$ . The triangle inequality in $\mathbb{R}$ (Proposition 4.1.3 (e), applied twice, with $\left| -y \right| = \left| y \right|$ from (b)) and Proposition 2.3.5 (b) give $\begin{aligned} \left| \kappa(q_j) - \kappa(q_k) \right| &\le \left| \kappa(q_j) - x_j \right| + \left| x_j - x_k \right| + \left| x_k - \kappa(q_k) \right| \\ &< \kappa(\varepsilon/3) + \kappa(\varepsilon/3) + \kappa(\varepsilon/3) = \kappa(\varepsilon) , \end{aligned}$ where the last equality is Theorem 5.4.1 (a). By Theorem 5.4.1 (a) and (c), $\left| \kappa(q_j) - \kappa(q_k) \right| = \left| \kappa(q_j - q_k) \right| = \kappa(\left| q_j - q_k \right|)$ . So $\kappa(\left| q_j - q_k \right|) < \kappa(\varepsilon)$ , and Theorem 5.4.1 (b) gives $\left| q_j - q_k \right| < \varepsilon$ in $\mathbb{Q}$ . Hence $(q_k)$ is Cauchy in $\mathbb{Q}$ : $(q_k) \in \mathcal{C}$ .

Step 2: the candidate. Let $x \mathrel{:=} [(q_k)_k] \in \mathbb{R}$ (Definition 5.2.1). By Theorem 5.4.5, $\kappa(q_k) \to x$ in $\mathbb{R}$ .

Step 3: $x_k \to x$ . By Corollary 5.4.4 (b) it suffices to find, for each $n \in \mathbb{Z}_{>0}$ , a $K \in \mathbb{N}$ with $\left| x_k - x \right| < \kappa(1/n)$ for every $k \ge K$ . Let $n \in \mathbb{Z}_{>0}$ . The tolerance $\kappa(1/(2n))$ is in $\mathbb{R}_{>0}$ , so Step 2 gives $K_3 \in \mathbb{N}$ with $\left| \kappa(q_k) - x \right| < \kappa(1/(2n))$ for every $k \ge K_3$ . For $k \ge 2n$ we have $k + 1 > 2n$ , so $1/(k + 1) < 1/(2n)$ (Proposition 2.5.2 (b)), and Eq. 5.5.1 with Theorem 5.4.1 (b) gives $\left| x_k - \kappa(q_k) \right| < \kappa(1/(2n))$ . Let $K \mathrel{:=} \max\{K_3, 2n\}$ ; it depends on $n$ only. For $k \ge K$ , $\begin{aligned} \left| x_k - x \right| &\le \left| x_k - \kappa(q_k) \right| + \left| \kappa(q_k) - x \right| \\ &< \kappa\Bigl(\frac{1}{2n}\Bigr) + \kappa\Bigl(\frac{1}{2n}\Bigr) = \kappa\Bigl(\frac{1}{n}\Bigr) , \end{aligned}$ by Proposition 4.1.3 (e) and Theorem 5.4.1 (a). So $x_k \to x$ in $\mathbb{R}$ . This proves the theorem.

The answer to the prompt about $m_k$ : existence alone would give, for each $k$ , a non-empty set of admissible integers, and taking one from each of these infinitely many sets, with no rule, is again a use of choice. Uniqueness makes each of these sets a singleton, so “the integer part of $(k + 1) x_k$ ” names one integer for each $k$ , and Step 0 defines a function outright. Existence of an integer part would not be enough; the proof needs the uniqueness half of Proposition 4.2.4.

Where is each hypothesis used? The Cauchy property of $(x_k)$ is used once, for $K_2$ in Step 1; Step 3 uses only the approximants and Step 2. The Archimedean property of $\mathbb{R}$ is used in Step 0, through the integer part, and in Steps 2 and 3, through Corollary 5.4.4 (b) (cited in Step 3 and in the proof of Theorem 5.4.5); the Archimedean property of $\mathbb{Q}$ is used in Step 1, for $K_1$ . Without the Cauchy hypothesis the conclusion fails: the sequence $x_k = k$ has approximants $q_k = k$ , which do not form a member of $\mathcal{C}$ , and it converges to nothing in $\mathbb{R}$ , being unbounded (Proposition 4.3.5, with Theorem 5.4.2 for the unboundedness).

Real numbers have no holes of their own. Together with Proposition 4.5.1 (with $F = \mathbb{R}$ ), the theorem says that a sequence in $\mathbb{R}$ converges in $\mathbb{R}$ if and only if it is Cauchy in $\mathbb{R}$ . In $\mathbb{Q}$ the “only if” half holds (Proposition 4.5.1, $F = \mathbb{Q}$ ), and the “if” half fails (Theorem 4.6.1). A second round of the construction, starting from Cauchy sequences of reals, would find every such sequence already convergent: there is no hole left for it to fill.

5.5.3. The approximant, by a rule

Step 0 is the heart of the proof, so we look at it again. By Theorem 5.4.2, $\mathbb{R}$ is an Archimedean ordered field. So Proposition 4.2.4 applies with $F = \mathbb{R}$ , with $\kappa$ in the role of $\iota_{\mathbb{R}}$ (Theorem 5.4.1 (d)): for every $y \in \mathbb{R}$ there is exactly one $m \in \mathbb{Z}$ with $m \le y < m + 1$ , the integer part of $y$ .

For a real number $x_k$ and the positive integer $k + 1$ , Step 0 applies this to $y = (k + 1) x_k$ and divides by $k + 1$ : $\frac{m_k}{k + 1} \le x_k < \frac{m_k}{k + 1} + \frac{1}{k + 1} .$ The rational $q_k \mathrel{:=} m_k/(k + 1)$ is the largest multiple of $1/(k + 1)$ that does not exceed $x_k$ , and it is within $1/(k + 1)$ of $x_k$ . Picture the multiples of $1/(k + 1)$ as a ladder of rungs; $q_k$ is the rung at or just below $x_k$ , and the ladder gets finer as $k$ grows.

The word that matters is exactly. For each $k$ the set of integers $m$ with $m \le (k + 1) x_k < m + 1$ has one element, so the relation “ $q_k = m/(k + 1)$ for the $m$ with $m \le (k + 1) x_k < m + 1$ ” assigns exactly one rational to each $k \in \mathbb{N}$ : it is a function $\mathbb{N} \to \mathbb{Q}$ (Sets, Relations, and Cardinality, Definition 1.4.1), given by a rule. Nothing is picked.

Quick check. Let $r$ be the real number of Example (The Class of the Newton Sequence), so $r > 0$ and $r^2 = 2$ , and let $x_k \mathrel{:=} r + 1/(k + 1)$ . Compute $q_0$ , $q_1$ and $q_2$ .

Solution. First locate $r$ : $(7/5)^2 = 49/25 < 2 < 9/4 = (3/2)^2$ . If $r < 7/5$ , then $r^2 < 49/25 < 2$ , and if $r \ge 3/2$ , then $r^2 \ge 9/4 > 2$ (Proposition 2.3.5 (g), with $r > 0$ ); both contradict $r^2 = 2$ , so $7/5 \le r < 3/2$ .

Next, $(k + 1) x_k = (k + 1) r + 1$ . For $k = 0$ : $12/5 \le r + 1 < 5/2$ , and $2 \le 12/5$ , $5/2 < 3$ , so $m_0 = 2$ . For $k = 1$ : $19/5 \le 2r + 1 < 4$ , and $3 \le 19/5$ , so $m_1 = 3$ . For $k = 2$ : $26/5 \le 3r + 1 < 11/2$ , and $5 \le 26/5$ , $11/2 < 6$ , so $m_2 = 5$ . Hence $q_0 = 2 , \qquad q_1 = \frac{3}{2} , \qquad q_2 = \frac{5}{3} .$ Each $q_k$ is within $1/(k + 1)$ below $x_k$ ; for instance $x_2 = r + 1/3 \in [26/15, 11/6)$ and $q_2 = 5/3 = 25/15$ .

5.5.4. Choice, and why it was not needed

The proof used $\exists$ E many times: to fix $K_1$ , $K_2$ , $K_3$ . Each of those fixes one object, for one given $\varepsilon$ or $n$ , and is ordinary logic. The axiom of choice is something else: one pick from each of infinitely many sets at once, with no rule. The next example shows exactly where it would have entered.

Example (Picking Representatives Is a Use of Choice)

Let $(x_k)$ be a sequence in $\mathbb{R}$ . A proof that says “for each $k$ , pick a representative $a^{(k)} \in x_k$ ” asks for what? And does the proof of Theorem 5.5.1 ask for it?

Solution. Each $x_k$ is a class, a non-empty subset of $\mathcal{C}$ (Sets, Relations, and Cardinality, Definition 2.5.2). The family $(x_k)_{k \in \mathbb{N}}$ is a family of non-empty sets indexed by $\mathbb{N}$ , and “pick $a^{(k)} \in x_k$ for each $k$ ” asks for a function $c \colon \mathbb{N} \to \mathcal{C}$ with $c(k) \in x_k$ for every $k$ : a choice function for the family. Its existence, with no rule given, is what Sets, Relations, and Cardinality, Axiom 3.3.1 provides. A single $\exists$ E would give one representative of one $x_k$ ; it cannot give infinitely many in one step.

The proof of Theorem 5.5.1 never picks a representative of any $x_k$ . It uses each $x_k$ only as an element of the ordered field $\mathbb{R}$ (its arithmetic and order, in Steps 0, 1 and 3), never through a representative; the Cauchy condition on $(x_k)$ enters only in Step 1. The only sequence it builds, $(q_k)$ , is given by a rule. So Sets, Relations, and Cardinality, Axiom 3.3.1 is not used.

In fact the theorem produces a rule for representatives as a by-product. Run its construction on the constant sequence $x_k = y$ for a fixed $y \in \mathbb{R}$ , which is Cauchy in $\mathbb{R}$ (Theorem 4.5.3 (a)). Step 1 shows that the approximants $q_k = m_k/(k + 1)$ , with $m_k$ the integer part of $(k + 1) y$ , form a member of $\mathcal{C}$ , and Step 3 that the constant sequence $y$ converges to $[(q_k)]$ . It also converges to $y$ (Example (First Limits) (a)), so $[(q_k)] = y$ by Theorem 4.3.4. Thus $(q_k)$ is a representative of $y$ , named by a formula in $y$ . Choice is not needed for representatives at all; what goes wrong is picking them without saying how.

Warning. The uncontrolled diagonal. Even with representatives in hand, the diagonal term $a^{(k)}_k$ need not be near $x_k$ . A representative of $x_k$ may start with any finite list of rationals (Example (Finite Changes and Shifts)): for $x_k = 0$ for every $k$ , the sequence equal to $k$ at the indices $n \le k$ and to $0$ afterwards represents $0$ , and its $k$ -th term is $k$ . Approximating $x_k$ needs a bound, such as $\left| x_k - q_k \right| < 1/(k + 1)$ , and a term of an arbitrary representative carries none.

5.5.5. Exercises

A. Check your understanding

Exercise (A1)

These questions are about the proof of Theorem 5.5.1.

(a) Why $\varepsilon/3$ in Step 1? Which three distances does it bound, and in which field is each of them measured?
(b) Why $1/(2n)$ in Step 3, for each of the two distances there?
(c) Where is the Cauchy property of $(x_k)$ used? Is it used in Step 3?
(d) Run the construction on the constant sequence $x_k = r$ (the real number of Example (The Class of the Newton Sequence)). Which class is $x$ ?
(e) Write “ $(x_k)$ converges in $\mathbb{R}$ ” in symbols, and its negation.

Solution.

(a) Step 1 bounds $\left| q_j - q_k \right|$ through $x_j$ and $x_k$ : the three distances are $\left| \kappa(q_j) - x_j \right|$ and $\left| x_k - \kappa(q_k) \right|$ , each below $\kappa(1/(j + 1))$ or $\kappa(1/(k + 1))$ by the choice of approximant, and $\left| x_j - x_k \right|$ , small because $(x_k)$ is Cauchy. All three are measured in $\mathbb{R}$ ; only the conclusion $\left| q_j - q_k \right| < \varepsilon$ is carried back to $\mathbb{Q}$ . Three thirds make one $\varepsilon$ .
(b) Two distances are added: $\left| x_k - \kappa(q_k) \right| < \kappa(1/(2n))$ for $k \ge 2n$ , from the approximant bound, and $\left| \kappa(q_k) - x \right| < \kappa(1/(2n))$ for $k \ge K_3$ , from Theorem 5.4.5. Two halves make $1/n$ .
(c) Only in Step 1, for the threshold $K_2$ . Step 3 uses the approximant bound and Step 2, not the Cauchy property directly: by then it has been spent on making $(q_k)$ a member of $\mathcal{C}$ .
(d) The approximants are $q_k = m_k/(k + 1)$ , with $m_k$ the integer part of $(k + 1) r$ , and $x \mathrel{:=} [(q_k)]$ . By the theorem’s proof, $x_k \to x$ ; the constant sequence $r$ also tends to $r$ , so $x = r$ by Theorem 4.3.4. Concretely, $q_0 = 1$ , $q_1 = 1$ (since $2 \le 2r < 3$ ), $q_2 = 4/3$ (since $4 \le 3r < 5$ ): a third sequence of rationals, besides the Newton sequence of Example (A Rational Sequence Aimed at the Gap) and the truncations $(d_k)$ , both in the class $r$ by Example (The Class of the Newton Sequence).
(e) Converges: $\exists x \in \mathbb{R} \ \forall \varepsilon \in \mathbb{R}_{>0} \ \exists K \in \mathbb{N} \ \forall k \in \mathbb{N} \ (k \ge K \Rightarrow \left| x_k - x \right| < \varepsilon)$ . Negation (Logic and Proof, Proposition 6.2.1, Logic and Proof, Proposition 6.2.3, Logic and Proof, Proposition 6.2.2, and $\neg(y < \varepsilon)$ read as $y \ge \varepsilon$ by (O1)): $\forall x \in \mathbb{R} \ \ \exists \varepsilon \in \mathbb{R}_{>0} \ \ \forall K \in \mathbb{N} \ \ \exists k \in \mathbb{N} \ \ \bigl( k \ge K \wedge \left| x_k - x \right| \ge \varepsilon \bigr) .$ Every candidate is beaten by some tolerance beyond every threshold.

B. Practice

Exercise (B1)

Which results of Chapter 4, applied with $F = \mathbb{R}$ , show that in $\mathbb{R}$ every convergent sequence is Cauchy and has only one limit? Why may they be applied? Deduce that a sequence in $\mathbb{R}$ converges if and only if it is Cauchy.

Solution. Proposition 4.5.1 (convergent sequences are Cauchy) and Theorem 4.3.4 (uniqueness of limits). Both are proved in Chapter 4 for an arbitrary ordered field $F$ , and $\mathbb{R}$ is an ordered field by Theorem 5.3.3, so they apply with $F = \mathbb{R}$ and tolerances in $\mathbb{R}_{>0}$ .

If $(x_k)$ converges in $\mathbb{R}$ , it is Cauchy in $\mathbb{R}$ by the first; if it is Cauchy in $\mathbb{R}$ , it converges by Theorem 5.5.1. So the two properties coincide in $\mathbb{R}$ , and the limit is unique by the second.

Exercise (B2)

Let $(p_k)$ be a sequence of rationals such that $(\kappa(p_k))_k$ converges in $\mathbb{R}$ to some $x$ . Prove that $(p_k) \in \mathcal{C}$ and that $x = [(p_k)]$ .

Hint: a convergent sequence is Cauchy.

Solution. By Proposition 4.5.1 with $F = \mathbb{R}$ , $(\kappa(p_k))$ is Cauchy in $\mathbb{R}$ . Let $\varepsilon \in \mathbb{Q}_{>0}$ . Then $\kappa(\varepsilon) \in \mathbb{R}_{>0}$ (Theorem 5.4.1 (b)), so there is $K$ with $\left| \kappa(p_j) - \kappa(p_k) \right| < \kappa(\varepsilon)$ for $j, k \ge K$ . As in Step 1 of the proof of Theorem 5.5.1, the left side is $\kappa(\left| p_j - p_k \right|)$ (Theorem 5.4.1 (a), (c)), and Theorem 5.4.1 (b) gives $\left| p_j - p_k \right| < \varepsilon$ . So $(p_k)$ is Cauchy in $\mathbb{Q}$ , that is, $(p_k) \in \mathcal{C}$ .

By Theorem 5.4.5, $\kappa(p_k) \to [(p_k)]$ . Also $\kappa(p_k) \to x$ . By Theorem 4.3.4 with $F = \mathbb{R}$ , $x = [(p_k)]$ .

So the real numbers that are limits of sequences of rationals in $\mathbb{R}$ are exactly the classes of those sequences; with Theorem 5.4.5, every real number is one.

C. Going deeper

Exercise (C1: Exit check: Cauchy completeness)

Prove that every Cauchy sequence in $\mathbb{R}$ converges in $\mathbb{R}$ . Say where the axiom of choice could have entered your proof, and why it does not.

Solution. Let $(x_k)$ be Cauchy in $\mathbb{R}$ .

Approximants by a rule. For $k \in \mathbb{N}$ let $m_k$ be the integer part of $(k + 1) x_k$ , unique by Proposition 4.2.4 ( $\mathbb{R}$ is Archimedean, Theorem 5.4.2), and $q_k \mathrel{:=} m_k/(k + 1)$ . Then $0 \le x_k - q_k < 1/(k + 1)$ , and $k \mapsto q_k$ is a function because the integer part is unique. This is where choice could have entered: “for each $k$ take some rational within $1/(k + 1)$ of $x_k$ ”, or “take a representative of each $x_k$ ”, makes infinitely many picks with no rule, a use of Sets, Relations, and Cardinality, Axiom 3.3.1. The integer part names one rational for each $k$ , so no choice is made.

Cauchy in $\mathbb{Q}$ . Let $\varepsilon \in \mathbb{Q}_{>0}$ . Fix $K_1$ with $1/(k + 1) < \varepsilon/3$ for $k \ge K_1$ (Corollary 2.5.4) and $K_2$ with $\left| x_j - x_k \right| < \varepsilon/3$ for $j, k \ge K_2$ (the Cauchy property, at the positive real $\kappa(\varepsilon/3)$ ). For $j, k \ge \max\{K_1, K_2\}$ , the triangle inequality in $\mathbb{R}$ gives $\left| q_j - q_k \right| < \varepsilon/3 + \varepsilon/3 + \varepsilon/3 = \varepsilon$ in $\mathbb{R}$ ; since $\kappa$ preserves sums, absolute values and order and reflects order (Theorem 5.4.1 (a)–(c)), the same inequality holds in $\mathbb{Q}$ . So $(q_k) \in \mathcal{C}$ .

The limit. Let $x \mathrel{:=} [(q_k)]$ . By Theorem 5.4.5, $q_k \to x$ in $\mathbb{R}$ . Let $\varepsilon \in \mathbb{R}_{>0}$ . By Corollary 5.4.4 (a) there is $n \in \mathbb{Z}_{>0}$ with $1/n < \varepsilon$ . Fix $K_3$ with $\left| q_k - x \right| < 1/(2n)$ for $k \ge K_3$ . For $k \ge \max\{K_3, 2n\}$ , $\left| x_k - x \right| \le \left| x_k - q_k \right| + \left| q_k - x \right| < 1/(2n) + 1/(2n) = 1/n < \varepsilon$ . So $x_k \to x$ .

Marking scheme. (10 points) - 2: an approximant $q_k \in \mathbb{Q}$ defined by a rule (unique integer part, or another explicit formula), with an explicit bound on $\left| x_k - q_k \right|$ tending to $0$ . - 3: $(q_k) \in \mathcal{C}$ by an $\varepsilon/3$ (or equivalent) estimate, with rational $\varepsilon$ and the passage from $\mathbb{R}$ back to $\mathbb{Q}$ through $\kappa$ justified. - 1: the candidate $x = [(q_k)]$ named. - 2: $q_k \to x$ in $\mathbb{R}$ , by Theorem 5.4.5, or directly as in its proof: $\left| x - \kappa(q_k) \right| = [(\left| q_m - q_k \right|)_m]$ (Proposition 5.3.5), bounded through Lemma 5.3.4, which gives only $\le$ . Either route earns both points. - 2: $x_k \to x$ , with the threshold chosen after the tolerance and depending on it only. Fatal errors (0 for the step): approximants or representatives “chosen” with no rule and no mention of choice; a real $\varepsilon$ used to test membership of $\mathcal{C}$ ; “ $q_k \to x$ because $x$ is the limit of $(q_k)$ ” (circular: that is what Theorem 5.4.5 proves). A proof that uses choice openly (representatives, with a threshold for each) and says so proves the theorem, but earns at most 1 of the 2 points of the first step, since the question asks for a construction that avoids it.

Exercise (C2: Find the error)

Here is an argument for Theorem 5.5.1. Is its conclusion true? Does the argument prove it? If not, name the first line that fails and why.

Let $(x_k)$ be a Cauchy sequence in $\mathbb{R}$ .

For each $k \in \mathbb{N}$ , pick a representative $a^{(k)} \in \mathcal{C}$ of $x_k$ .

Let $q_k \mathrel{:=} a^{(k)}_k$ , the $k$ -th term of the $k$ -th representative.

The sequence $(q_k)$ is Cauchy in $\mathbb{Q}$ , and $\left| x_k - \kappa(q_k) \right| \to 0$ in $\mathbb{R}$ , since each $a^{(k)}$ is Cauchy and $(x_k)$ is Cauchy.

Let $x \mathrel{:=} [(q_k)]$ . Then $x_k \to x$ , by an $\varepsilon/2$ argument through the terms $q_k$ .

Solution (Hint 1). Ask whether $a^{(k)}_k$ has to be close to $x_k$ at all.

Solution (Hint 2). Try the constant sequence $x_k = 0$ for every $k$ , and representatives that are not $0$ at their first few terms.

Solution. The conclusion is true: it is Theorem 5.5.1.

The failing line is (4). Each $a^{(k)}$ being Cauchy says that the terms of one representative settle down eventually, past a threshold that depends on $k$ ; nothing ties the $k$ -th term of $a^{(k)}$ to $x_k$ , and nothing ties different representatives to each other at index $k$ . The Cauchy property of $(x_k)$ is about the classes, and the line uses it as if it were about the diagonal terms.

Counterexample to the step. Let $x_k = 0$ for every $k$ , a Cauchy sequence in $\mathbb{R}$ . For each $k$ , let $a^{(k)}_n \mathrel{:=} k$ for $n \le k$ and $a^{(k)}_n \mathrel{:=} 0$ for $n > k$ . Each $a^{(k)}$ is eventually equal to the zero sequence, so it is in $\mathcal{C}$ and represents $0$ (Example (Finite Changes and Shifts)). Then $q_k = a^{(k)}_k = k$ , and $(k)$ is not Cauchy in $\mathbb{Q}$ : consecutive terms satisfy $\left| q_{k+1} - q_k \right| = 1$ , so the Cauchy condition fails for $\varepsilon = 1$ . Nor does $\left| x_k - \kappa(q_k) \right| = \kappa(k)$ tend to $0$ : it is $\ge 1$ for every $k \ge 1$ . The premises of (4) hold and both parts of its conclusion fail.

A second, separate defect: line (2). “For each $k$ , pick” makes one pick from each of infinitely many classes with no rule: an unflagged use of Sets, Relations, and Cardinality, Axiom 3.3.1 (Example (Picking Representatives Is a Use of Choice)). Even if (4) were repaired, the argument would use choice without saying so. Line (5) is correct given (4): $\kappa(q_k) \to x$ in $\mathbb{R}$ by Theorem 5.4.5, and $\left| x_k - x \right| \le \left| x_k - \kappa(q_k) \right| + \left| \kappa(q_k) - x \right|$ . The bound on $\left| x_k - \kappa(q_k) \right|$ is needed: knowing only that $(q_k)$ is Cauchy would not do (with $a^{(k)}_n = 1$ for $n \le k$ and $0$ after, $q_k = 1$ for every $k$ , yet $x_k = 0$ does not tend to $[(1)] = 1$ ).

Repair. Either keep representatives and control the diagonal (for each $k$ , go far enough out in $a^{(k)}$ that its terms are within $1/(k + 1)$ of $x_k$ , which Theorem 5.4.5 makes possible, and use that term in place of $a^{(k)}_k$ ), at the price of a choice of representatives and of thresholds, flagged; or, better, drop representatives and use the integer-part approximant $q_k = m_k/(k + 1)$ of the text, which needs no choice at all.

Marking scheme. (10 points) - 2: says the conclusion is true, and cites the theorem. - 3: identifies line (4) as the failing line, and says why: nothing ties $a^{(k)}_k$ to $a^{(j)}_j$ for $j \ne k$ , or to $x_k$ . - 3: a counterexample to the step, with every representative checked to lie in its class. - 2: names the use of choice in line (2), and a repair that replaces $q_k$ by a rational with a bound on $\left| x_k - \kappa(q_k) \right|$ tending to $0$ (a later term of $a^{(k)}$ , or the integer-part approximant). Fatal errors (0 for the step): calling the conclusion false; a “counterexample” in which the sequence $(x_k)$ is not Cauchy.