4.6 A Cauchy Sequence with No Rational Limit

Section 4.5 proved that every convergent sequence is Cauchy (Proposition 4.5.1). In $\mathbb{Q}$ the converse fails, and the failure sits exactly at the hole Chapter 2 found at $\sqrt 2$ : no rational squares to $2$ (Theorem 2.6.1). This section proves that the rational sequence of Chapter 2 that closes in on that hole (Example (A Rational Sequence Aimed at the Gap)) is Cauchy in $\mathbb{Q}$ and converges to no rational. Chapter 5 starts from this sequence and builds the number it is aiming at. The section ends by listing what the chapter has not proved, and why, in $\mathbb{Q}$ , it could not have.

Throughout this section the field is $F = \mathbb{Q}$ : every tolerance $\varepsilon$ is a positive rational, and “converges” means “converges in $\mathbb{Q}$ ” (Definition 4.3.2).

4.6.1. The sequence again

Recall the sequence of Example (A Rational Sequence Aimed at the Gap). For $s \in \mathbb{Q}_{>0}$ let $t(s) \mathrel{:=} (s^2 + 2)/(2s)$ , the average of $s$ and $2/s$ ; let $x_0 \mathrel{:=} 2$ and $x_{n+1} \mathrel{:=} t(x_n)$ , and let $e_n \mathrel{:=} x_n^2 - 2$ , the amount by which $x_n^2$ overshoots $2$ . The first terms are $x_0 = 2 , \quad x_1 = \frac{3}{2} , \quad x_2 = \frac{17}{12} , \quad x_3 = \frac{577}{408} ,$ with $e_0 = 2 , \quad e_1 = \frac{1}{4} , \quad e_2 = \frac{1}{144} , \quad e_3 = \frac{1}{166464} .$ Chapter 2 proved, for every $n \in \mathbb{N}$ , the following facts, and we cite them from Example (A Rational Sequence Aimed at the Gap) without proving them again: $\begin{aligned} &x_n \in \mathbb{Q}_{>0} , \qquad e_n > 0 \ \ (\text{so } x_n^2 > 2) , \\ &e_{n+1} = \frac{e_n^2}{4x_n^2} \le \frac{e_n^2}{8} , \qquad x_n - x_{n+1} = \frac{e_n}{2x_n} > 0 . \end{aligned}$ The second line says two things. The overshoot is roughly squared at each step, so it shrinks very fast; and the terms decrease. Section 4.5 asks for more than decrease: any two late terms must be close. The overshoot $e_n$ measures how close, because every later term lies between $2/x_n$ and $x_n$ , an interval of length $e_n/x_n$ .

For the proof we do not need the true speed of $e_n$ . A crude bound is enough, as long as it can be pushed below every rational tolerance: $e_1 = \frac{1}{4} , \quad e_2 = \frac{1}{144} \le \frac{1}{8} , \quad e_3 = \frac{1}{166464} \le \frac{1}{12} ;$ that is, $e_n \le 1/(4n)$ for $n = 1, 2, 3$ , and the theorem proves it for every $n \ge 1$ . Archimedes then turns $1/(4n)$ into anything below a given $\varepsilon$ .

4.6.2. The theorem

Theorem 4.6.1 (The Newton Sequence Is Cauchy with No Rational Limit)

Let $(x_n)_{n \in \mathbb{N}}$ and $e_n = x_n^2 - 2$ be as in Example (A Rational Sequence Aimed at the Gap). Then $x_n > 1$ for every $n \in \mathbb{N}$ , $x_m \le x_n$ whenever $m \ge n$ , and $e_n \le 1/(4n)$ for every $n \ge 1$ . The sequence $(x_n)$ is a Cauchy sequence in $\mathbb{Q}$ , and there is no $L \in \mathbb{Q}$ with $x_n \to L$ .

The first three clauses are part of the statement, rather than steps hidden in the proof, so that Chapter 5 can cite them.

Idea. Cauchy. For $m \ge n$ , the later term $x_m$ lies below $x_n$ , since the terms decrease, and above $2/x_n$ , since $x_m > 2/x_m \ge 2/x_n$ . So $0 \le x_n - x_m \le x_n - 2/x_n = e_n/x_n \le e_n$ . With $e_n \le 1/(4n)$ , every two terms beyond $N$ differ by at most $1/(4N)$ , and Archimedes makes $1/N$ smaller than any rational $\varepsilon$ .

No rational limit. Locate the missing limit: suppose $x_n \to L$ in $\mathbb{Q}$ and find out what $L$ would have to satisfy. The limit laws turn $x_n \to L$ into $x_n^2 \to L^2$ . But $x_n^2 = 2 + e_n \to 2$ , because $e_n$ is squeezed between $0$ and $1/(4n)$ . Limits are unique, so $L^2 = 2$ , and no rational satisfies that. Before reading on: which law turns $x_n \to L$ into $x_n^2 \to L^2$ , and applied to which two sequences?

Proof. We prove six facts, then the two claims. Induction is Logic and Proof, Axiom 4.2.1, read on $\mathbb{N} = \omega$ through Corollary 1.7.3 (b).

(i), (ii), (iv) in part: cited. By Example (A Rational Sequence Aimed at the Gap), for every $n \in \mathbb{N}$ : (i) $x_n \in \mathbb{Q}_{>0}$ , $e_n > 0$ and $x_n^2 > 2$ ; (ii) $e_{n+1} = e_n^2/(4x_n^2) \le e_n^2/8$ ; and $x_{n+1} < x_n$ .

(iii) $x_n > 1$ . Suppose $x_n \le 1$ . Since $x_n > 0$ by (i), either $x_n < 1$ , and then $x_n^2 < 1^2 = 1$ by Proposition 2.3.5 (g), or $x_n = 1$ and $x_n^2 = 1$ . Either way $x_n^2 \le 1 < 2$ , against $x_n^2 > 2$ and (O1). So $x_n > 1$ , by totality (Proposition 2.3.5 (i)).

(iv) $x_m \le x_n$ for $m \ge n$ . Fix $n$ . By induction on $k$ , $x_{n+k} \le x_n$ for every $k \in \mathbb{N}$ : the base $P(0)$ is $x_n \le x_n$ , and if $x_{n+k} \le x_n$ , then $x_{n+k+1} < x_{n+k} \le x_n$ . Every $m \ge n$ in $\mathbb{N}$ is $n + k$ for some $k \in \mathbb{N}$ (Proposition 1.6.3 (a)), so $x_m \le x_n$ .

(v) $e_n \le 1/(4n)$ for $n \ge 1$ . By induction on $k$ , for $P(k)$ : $e_{k+1} \le 1/(4(k + 1))$ . Base $P(0)$ : $e_1 = 1/4$ . Step: assume $P(k)$ , and let $n \mathrel{:=} k + 1 \ge 1$ , so $0 < e_n \le 1/(4n) \le 1/4$ (by (i), $P(k)$ , and Proposition 4.1.2 (c) with $4 \le 4n$ ). Then, by (ii) and Proposition 4.1.2 (d) (with the factors $0 \le e_n/8 \le e_n/8$ and $0 \le e_n \le 1/4$ , then $0 \le 1/32 \le 1/32$ and $0 \le e_n \le 1/(4n)$ ), $e_{n+1} \le \frac{e_n \cdot e_n}{8} \le \frac{e_n}{8} \cdot \frac{1}{4} = \frac{e_n}{32} \le \frac{1}{128 n} \le \frac{1}{4(n + 1)} ,$ where the last step is Proposition 4.1.2 (c), since $0 < 4(n + 1) = 4n + 4 \le 128 n$ for $n \ge 1$ (as $4 \le 124 n$ ). This is $P(k + 1)$ .

(vi) For $m \ge n \ge 1$ : $0 \le x_n - x_m \le 1/(4n)$ . By (iv), $x_m \le x_n$ , so $x_n - x_m \ge 0$ . By (i), $x_m^2 > 2$ ; multiplying by $1/x_m > 0$ (Proposition 2.5.2 (a), Proposition 2.3.5 (c)) gives $x_m > 2/x_m$ . From $0 < x_m \le x_n$ , Proposition 4.1.2 (c) gives $1/x_n \le 1/x_m$ , so $2/x_n \le 2/x_m < x_m$ (Proposition 4.1.2 (d), with $0 \le 2 \le 2$ ). Hence $x_n - x_m \le x_n - \frac{2}{x_n} = \frac{x_n^2 - 2}{x_n} = \frac{e_n}{x_n} \le e_n \le \frac{1}{4n} .$ Here $e_n/x_n \le e_n$ because $0 < 1 < x_n$ by (iii), so $1/x_n < 1$ (Proposition 2.5.2 (b)), and $e_n > 0$ ; the last step is (v).

Cauchy. Let $\varepsilon \in \mathbb{Q}_{>0}$ . By Corollary 2.5.4 there is $N \in \mathbb{Z}_{>0}$ with $1/N < \varepsilon$ ; it depends only on $\varepsilon$ . Let $m, n \ge N$ , and let $k \mathrel{:=} \min\{m, n\} \ge N \ge 1$ and $l \mathrel{:=} \max\{m, n\}$ . By (vi) with the pair $l \ge k$ , $\left| x_m - x_n \right| = x_k - x_l \le \frac{1}{4k} \le \frac{1}{4N} \le \frac{1}{N} < \varepsilon ,$ where $1/(4k) \le 1/(4N) \le 1/N$ is Proposition 4.1.2 (c) applied to $N \le 4N \le 4k$ . So $(x_n)$ is Cauchy in $\mathbb{Q}$ .

No rational limit. Suppose, for a contradiction, that $x_n \to L$ for some $L \in \mathbb{Q}$ . By the product law, Theorem 4.4.3 (c), applied with both sequences equal to $(x_n)$ , $x_n^2 \to L^2$ .

Next, $(e_n)$ is null. We use the squeeze, Proposition 4.4.4 (c), with $N_0 = 1$ , the lower sequence constantly $0$ (which tends to $0$ ) and the upper sequence $(1/(n + 1))_{n \in \mathbb{N}}$ . The upper sequence is defined for every $n \in \mathbb{N}$ , and it is null in $\mathbb{Q}$ by Proposition 4.2.3, as in Example (First Limits). For $n \ge 1$ we have $n + 1 \le 4n$ (as $1 \le 3n$ ), so by (i), (v) and Proposition 4.1.2 (c), $0 < e_n \le \frac{1}{4n} \le \frac{1}{n + 1} \qquad (n \ge 1) .$ (At $n = 0$ the middle term is undefined and $e_0 = 2$ ; the squeeze needs the inequalities only from $N_0 = 1$ on.) So $e_n \to 0$ .

Then $x_n^2 = 2 + e_n$ for every $n$ , and the sum law, Theorem 4.4.3 (a), with the constant sequence $2$ gives $x_n^2 \to 2 + 0 = 2$ . The sequence $(x_n^2)$ therefore tends to $L^2$ and to $2$ , and by Theorem 4.3.4, $L^2 = 2$ . This contradicts Theorem 2.6.1. Hence no $L \in \mathbb{Q}$ has $x_n \to L$ .

The answer to the prompt: the product law, Theorem 4.4.3 (c), applied to $a_n = b_n = x_n$ . It is the only step that uses the hypothesis $x_n \to L$ ; the rest of the second half is about $e_n$ , which we control without any limit, and then uniqueness compares the two limits of $(x_n^2)$ .

Archimedes is used twice, both times in $\mathbb{Q}$ , where Theorem 2.5.3 provides it: for the Cauchy threshold, through Corollary 2.5.4, and for the upper sequence $(1/(n + 1))$ of the squeeze, through Proposition 4.2.3.

Remark. The sequence is Cauchy and not null, since $\left| x_n \right| = x_n > 1$ for every $n$ , so Theorem 4.5.4 applies to it. Its proof, run with $\varepsilon = 1$ , gives $c = 1/2$ ; directly, $x_n \ge 1$ for every $n$ . Chapter 5 turns the class of $(x_n)$ into a positive real number whose square is $2$ .

Warning. “Cauchy” does not mean “convergent to a limit we have not named yet”. In $\mathbb{Q}$ there is nothing to name: by Theorem 4.6.1, the statement “every Cauchy sequence of rationals converges in $\mathbb{Q}$ ” is false, not merely unproved. A proof that says “ $(a_n)$ is Cauchy, so let $a$ be its limit” is wrong in $\mathbb{Q}$ , whatever it goes on to do.

Quick check. Give an upper bound and a positive lower bound for the terms $x_n$ in $\mathbb{Q}$ , with reasons.

Solution. Upper bound $2$ : $x_n \le x_0 = 2$ for every $n$ , by clause (iv) of the proof with $n = 0$ . Lower bound $1$ : $x_n > 1$ for every $n$ , by (iii). The upper bound is attained, at $x_0$ ; the lower bound $1$ is crude (every term also exceeds $2/x_1 = 4/3$ , by the argument of (vi), and $x_0 = 2 > 4/3$ ), but any positive lower bound answers the question.

4.6.3. What this chapter did not prove

Looking back over the chapter, three familiar tools of real analysis are absent, and their absence is checkable.

No result asserts convergence without naming the limit. Each result of the chapter that concludes $a_n \to a$ has $a$ in its hypotheses or in its statement: the examples of Section 4.3 (Example (First Limits)), the tail-change rules (Proposition 4.3.2), the limit laws (Theorem 4.4.3) and the squeeze (Proposition 4.4.4 (c)). The results of Section 4.5, about sequences whose limit is unknown, conclude “Cauchy”, “bounded”, or a sign, never “convergent”.
No supremum. No result uses the supremum of a subset of $F$ (Sets, Relations, and Cardinality, Definition 2.6.5), so nothing here rests on a least upper bound property.
No monotone convergence theorem, and no Bolzano–Weierstrass theorem. Neither is stated or used.

In $\mathbb{Q}$ each of the three would fail. A least upper bound property fails by Section 2.6: the set of rationals with square below $2$ is non-empty and bounded above, with no rational supremum. A monotone convergence theorem fails by the sequence of this section: $(x_n)$ is decreasing (clause (iv) of the proof), bounded (the Quick check above) and Cauchy, and it has no limit in $\mathbb{Q}$ . And so does Bolzano–Weierstrass, which would give the bounded sequence $(x_n)$ a subsequence converging in $\mathbb{Q}$ . Indeed, let $n_0 < n_1 < n_2 < \cdots$ be indices and suppose $x_{n_k} \to L \in \mathbb{Q}$ as $k \to \infty$ . By induction, $n_k \ge k$ for every $k$ (if $n_k \ge k$ , then $n_{k+1} > n_k \ge k$ , so $n_{k+1} \ge k + 1$ ). So for $k \ge 1$ , $0 < e_{n_k} \le 1/(4n_k) \le 1/(4k) \le 1/(k + 1)$ , and the argument of the proof, run on the sequence $(x_{n_k})_{k \in \mathbb{N}}$ , gives $L^2 = 2$ again.

The reader who knows real analysis will have met all three as theorems about $\mathbb{R}$ . They are true there because of an axiom about $\mathbb{R}$ , completeness, that no ordered field satisfies automatically, and this chapter never assumed it. Chapter 5 builds, from Cauchy sequences of rationals, a field in which every Cauchy sequence converges, and proves that in it every non-empty subset that is bounded above has a supremum: a complete ordered field. Chapter 6 proves that any two complete ordered fields are copies of each other, by exactly one order-preserving field isomorphism. Analysis on the Real Line, Chapter 1 takes the axioms of a complete ordered field as its starting point, and its Chapter 2 revisits this chapter’s sequences, now in $\mathbb{R}$ .

4.6.4. Exercises

A. Check your understanding

Exercise (A1)

These questions are about the proof of Theorem 4.6.1.

(a) Which result gives $x_n^2 \to L^2$ from $x_n \to L$ , applied to which two sequences?
(b) Why does the proof need the bound $e_n \le 1/(4n)$ , and not only “ $e_n > 0$ and $(e_n)$ is decreasing”?
(c) Where is the Archimedean property used?
(d) Check fact (vi) at $n = 2$ , $m = 3$ : compute $x_2 - x_3$ and compare it with $e_2/x_2$ , $e_2$ and $1/(4 \cdot 2)$ .
(e) State the idea of the proof that $(x_n)$ has no rational limit, in two sentences.

Solution.

(a) The product law, Theorem 4.4.3 (c), with $a_n = b_n = x_n$ and $a = b = L$ .
(b) The proof must show that $(e_n)$ is null, that is, below every rational $\varepsilon$ from some index on. A sequence can be positive and decreasing without being null: $1 + 1/(n + 1)$ decreases and stays above $1$ . The bound $1/(4n) \le 1/(n + 1)$ ties $e_n$ to a sequence known to be null, and the same bound gives the Cauchy threshold.
(c) Twice: for the Cauchy threshold, by Corollary 2.5.4 (an $N$ with $1/N < \varepsilon$ ); and for the upper sequence $(1/(n + 1))$ of the squeeze, null by Proposition 4.2.3.
(d) $x_2 - x_3 = 17/12 - 577/408 = (17 \cdot 34 - 577)/408 = (578 - 577)/408 = 1/408$ . Next, $e_2/x_2 = (1/144) \cdot (12/17) = 1/204$ . So $\frac{1}{408} \le \frac{1}{204} \le \frac{1}{144} \le \frac{1}{8} ,$ which is the chain $x_2 - x_3 \le e_2/x_2 \le e_2 \le 1/(4 \cdot 2)$ of (vi).
(e) A rational limit $L$ of $(x_n)$ would make $x_n^2$ tend to $L^2$ , by the product law. But $x_n^2 = 2 + e_n$ tends to $2$ , since $e_n$ is squeezed to $0$ , so uniqueness of limits gives $L^2 = 2$ , which no rational satisfies.

B. Practice

Exercise (B1)

With $(x_n)$ as in Theorem 4.6.1, prove that the sequence $(x_n - 2/x_n)$ is null in $\mathbb{Q}$ , that $(2/x_n)$ is Cauchy in $\mathbb{Q}$ , and that $(2/x_n)$ has no limit in $\mathbb{Q}$ .

Solution. Null. For every $n$ , $x_n - 2/x_n = (x_n^2 - 2)/x_n = e_n/x_n$ , and as in step (vi) of the proof, $0 < e_n/x_n \le e_n \le 1/(4n) \le 1/(n + 1)$ for $n \ge 1$ (using $x_n > 1$ and $e_n \le 1/(4n)$ from the theorem, and $e_n > 0$ from Example (A Rational Sequence Aimed at the Gap) (i)). By the squeeze (Proposition 4.4.4 (c)) with $N_0 = 1$ , lower sequence $0$ and upper sequence $(1/(n + 1))$ , null in $\mathbb{Q}$ (Example (First Limits)), $x_n - 2/x_n \to 0$ .

Cauchy. $2/x_n = x_n - (x_n - 2/x_n)$ is the difference of a Cauchy sequence (Theorem 4.6.1) and a null one, which is Cauchy by Theorem 4.5.3 (a); so it is Cauchy by Theorem 4.5.3 (b).

No rational limit. Suppose $2/x_n \to L \in \mathbb{Q}$ . Then $x_n = 2/x_n + (x_n - 2/x_n) \to L + 0 = L$ by the sum law (Theorem 4.4.3 (a)), against Theorem 4.6.1.

The terms $2/x_n$ approach the gap from below ( $2/x_n < x_m$ for all $m$ , and $(2/x_n)^2 = 4/x_n^2 < 2$ ), while the $x_n$ approach it from above; their differences are null, so in Chapter 5 the two sequences will represent the same real number.

Exercise (B2)

Let $(H_n)$ be the sequence of Example (Shrinking Steps, Terms That Do Not Settle): $H_0 = 0$ and $H_{n+1} = H_n + 1/(n + 1)$ in $\mathbb{Q}$ . Prove that $H_{2^k} \ge 1 + k/2$ for every $k \in \mathbb{N}$ , and hence that $(H_n)$ is not bounded.

Solution. The powers $2^k$ of the natural number $2$ are those of Section 1.6 (defined just before Proposition 1.6.4 by Theorem 1.5.1), with $2^0 = 1$ and $2^{k+1} = 2^k \cdot 2 = 2^k + 2^k$ .

We use Logic and Proof, Axiom 4.2.1 on $k$ . Base $P(0)$ : $H_{2^0} = H_1 = H_0 + 1/1 = 1 \ge 1 + 0/2$ . Step: assume $H_{2^k} \ge 1 + k/2$ . The example shows $H_{2n} - H_n \ge 1/2$ for every $n \ge 1$ ; with $n = 2^k \ge 1$ (by induction, $2^k \ge 1$ ) it gives $H_{2^{k+1}} \ge H_{2^k} + 1/2 \ge 1 + (k + 1)/2$ .

Not bounded. Let $M \in \mathbb{Q}_{>0}$ . By Theorem 2.5.3 there is $k \in \mathbb{N}$ with $2M < k$ . Then $H_{2^k} \ge 1 + k/2 > M$ , and $H_{2^k} > 0$ , so $\left| H_{2^k} \right| > M$ . No $M$ bounds the sequence.

So $(H_n)$ is not Cauchy for a second reason: a Cauchy sequence is bounded (Proposition 4.5.2).

C. Going deeper

Exercise (C1: Exit check: a Cauchy sequence with no rational limit)

Let $y_0 \mathrel{:=} 2$ and $y_{n+1} \mathrel{:=} (y_n^2 + 3)/(2y_n)$ , a sequence in $\mathbb{Q}_{>0}$ , and let $d_n \mathrel{:=} y_n^2 - 3$ .

(a) Prove that no rational number squares to $3$ .
(b) Prove that $(y_n)$ is a Cauchy sequence in $\mathbb{Q}$ and that it converges to no element of $\mathbb{Q}$ .

Solution (Hint 1). For (b), copy facts (i)–(vi) of the proof of Theorem 4.6.1 with $3$ in place of $2$ . Since only the case $2$ was proved in Chapter 2, prove the analogues of (i), (ii) and the decrease yourself, as Example (A Rational Sequence Aimed at the Gap) does for $2$ . For (a), run the descent of Theorem 2.6.1.

Solution (Hint 2). First verify the identities $d_{n+1} = d_n^2/(4y_n^2)$ and $y_n - y_{n+1} = d_n/(2y_n)$ by clearing denominators. In the descent for (a), from $p^2 = 3q^2$ show $q < p < 2q$ , and try $p' \mathrel{:=} 3q - p$ , $q' \mathrel{:=} p - q$ .

Solution.

(a) Suppose $x \in \mathbb{Q}$ with $x^2 = 3$ . Then $x \ne 0$ , and replacing $x$ by $-x$ if needed, $x > 0$ ; write $x = a/b$ with $a, b \in \mathbb{Z}_{>0}$ (Proposition 2.4.4 (b), Theorem 2.5.1 (a)), so $a^2 = 3b^2$ . The set of $q \in \mathbb{Z}_{>0}$ for which some $p \in \mathbb{Z}_{>0}$ has $p^2 = 3q^2$ contains $b$ and is bounded below by $0$ , so it has a least element $q$ (Proposition 2.3.6); fix such a $p$ .
$q < p$ : if $p \le q$ , then $p^2 \le q^2$ (Proposition 2.3.5 (g), or equality), so $3q^2 \le q^2$ and $2q^2 \le 0$ , against $2q^2 > 0$ (Proposition 2.3.5 (e), (O4)). $p < 2q$ : if $2q \le p$ , then $4q^2 \le p^2 = 3q^2$ , so $q^2 \le 0$ , against $q^2 > 0$ . By totality, $q < p < 2q$ .

Let $p' \mathrel{:=} 3q - p$ and $q' \mathrel{:=} p - q$ . Then $q' > 0$ since $q < p$ ; $q' < q$ since $p < 2q$ ; and $p' > 0$ since $p < 2q < 3q$ . Expanding, $\begin{aligned} p'^2 - 3q'^2 &= (9q^2 - 6pq + p^2) - (3p^2 - 6pq + 3q^2) \\ &= 6q^2 - 2p^2 = 2(3q^2 - p^2) = 0 . \end{aligned}$ So $q'$ is an admissible denominator smaller than $q$ , a contradiction. No rational squares to $3$ .
(b) Positivity and the two identities. For $s \in \mathbb{Q}_{>0}$ , $(s^2 + 3)/(2s) \in \mathbb{Q}_{>0}$ ( $s^2 + 3 > 0$ , $2s > 0$ , Proposition 2.5.2 (a), (O4)), so the recursion (Sets, Relations, and Cardinality, Theorem 2.3.1, read on $\omega$ through Corollary 1.7.3 (b)) defines $(y_n)$ in $\mathbb{Q}_{>0}$ . With $u(s) \mathrel{:=} (s^2 + 3)/(2s)$ , clearing the non-zero denominators $4s^2$ and $2s$ , $u(s)^2 - 3 = \frac{(s^2 + 3)^2 - 12 s^2}{4s^2} = \frac{(s^2 - 3)^2}{4s^2} , \qquad s - u(s) = \frac{s^2 - 3}{2s} .$ So $d_{n+1} = d_n^2/(4y_n^2)$ and $y_n - y_{n+1} = d_n/(2y_n)$ . By induction, $d_n > 0$ : $d_0 = 1$ , and $d_n > 0$ gives $d_n^2 > 0$ , so $d_{n+1} > 0$ . Hence $y_n^2 > 3$ , $4y_n^2 > 12$ , and $d_{n+1} \le d_n^2/12$ (Proposition 2.5.2 (b)). Also $y_n - y_{n+1} > 0$ .

Values. $y_1 = 7/4$ , $y_2 = 97/56$ ; $d_0 = 1$ , $d_1 = 49/16 - 3 = 1/16$ , $d_2 = 9409/3136 - 3 = 1/3136$ , and indeed $d_2 = (1/16)^2/(4 \cdot 49/16) = 1/3136$ .

Monotone, and $y_n > 1$ . As in (iii) and (iv): $y_n > 1$ , since $0 < y_n \le 1$ would give $y_n^2 \le 1 < 3$ ; and $y_m \le y_n$ for $m \ge n$ , by induction from $y_{n+1} < y_n$ .

A bound on $d_n$ . $d_n \le 1/(16n)$ for $n \ge 1$ , by induction: $d_1 = 1/16$ ; if $0 < d_n \le 1/(16n) \le 1/16$ , then $d_{n+1} \le d_n \cdot d_n/12 \le d_n/192 \le 1/(3072 n) \le 1/(16(n + 1))$ , since $16n + 16 \le 3072 n$ for $n \ge 1$ .

Close terms. For $m \ge n \ge 1$ : $y_m \le y_n$ , and $y_m > 3/y_m \ge 3/y_n$ , so $0 \le y_n - y_m \le y_n - \frac{3}{y_n} = \frac{d_n}{y_n} \le d_n \le \frac{1}{16 n} ,$ using $y_n > 1$ .

Cauchy. Given $\varepsilon \in \mathbb{Q}_{>0}$ , Corollary 2.5.4 gives $N \in \mathbb{Z}_{>0}$ with $1/N < \varepsilon$ . For $m, n \ge N$ , with $k \mathrel{:=} \min\{m, n\} \ge N$ , $\left| y_m - y_n \right| \le 1/(16k) \le 1/N < \varepsilon$ .

No rational limit. If $y_n \to L \in \mathbb{Q}$ , then $y_n^2 \to L^2$ (Theorem 4.4.3 (c)). For $n \ge 1$ , $0 < d_n \le 1/(16n) \le 1/(n + 1)$ , so $d_n \to 0$ by the squeeze (Proposition 4.4.4 (c), with $N_0 = 1$ and the null upper sequence $(1/(n + 1))$ ), and $y_n^2 = 3 + d_n \to 3$ (Theorem 4.4.3 (a)). By Theorem 4.3.4, $L^2 = 3$ , against (a).

Marking scheme. (10 points) - 2: (a), a descent with a least denominator (Proposition 2.3.6), with the inequalities $q < p < 2q$ and the positivity of $p'$ , $q'$ justified (another correct route, such as divisibility by $3$ with a least denominator, earns the same). - 1: positivity of $y_n$ and $d_n$ , and the recursion identity for $d_{n+1}$ . - 2: a comparison of $y_n$ and $y_m$ for $m \ge n$ : monotonicity together with $y_m \ge 3/y_n$ , or (factorization route, as in R4) $\left| y_n - y_m \right| = \left| d_n - d_m \right|/(y_n + y_m)$ with $y_n + y_m > 2$ , since $y_n > 1$ follows from $y_n^2 > 3$ . - 2: an explicit bound on $d_n$ (or on $y_n - y_m$ ) tending to $0$ , with Archimedes giving $N$ for each rational $\varepsilon$ . - 1: Cauchy concluded with the quantifiers in order. - 2: no rational limit, by the product law, uniqueness of limits and (a). Fatal errors (0 for the step): assuming that $\sqrt 3$ exists in $\mathbb{Q}$ or in a larger field and comparing with it; invoking a monotone convergence theorem. A route by factorization as in R4 earns the next 2 for showing $d_n \to 0$ (by an explicit bound with Archimedes, or by the squeeze), and the 1 for concluding that $(d_n)$ is Cauchy by Proposition 4.5.1 and transferring this to $(y_n)$ with the quantifiers in order. A route through the steps $y_n - y_{n+1}$ and a geometric bound earns the middle 2 + 1 only if the sum of the steps from $n$ to $m$ is bounded explicitly, independently of $m$ (the example at the end of Section 4.5 shows why).

Exercise (C2: Cauchy depends on the field)

In the ordered field $\mathbb{Q}(t)$ of Example (A Non-Archimedean Ordered Field), consider the sequence $a_n \mathrel{:=} 1/((n + 1) \cdot 1)$ , whose terms are the rationals $1/(n + 1)$ . Explain why $(a_n)$ is not a Cauchy sequence in $\mathbb{Q}(t)$ , although it is Cauchy in $\mathbb{Q}$ .

Solution. In $\mathbb{Q}$ , $(1/(n + 1))$ is Cauchy (Section 4.5, the examples after Definition 4.5.1).

In $\mathbb{Q}(t)$ , take the tolerance $\varepsilon \mathrel{:=} 1/t$ , which is positive (the example shows $0 < 1/t$ ). Let $N \in \mathbb{N}$ , and take $m \mathrel{:=} N$ , $n \mathrel{:=} N + 1$ . Then $\left| a_m - a_n \right| = \frac{1}{N + 1} - \frac{1}{N + 2} = \frac{1}{(N + 1)(N + 2)} ,$ by Lemma 4.1.1 (c), a positive rational. The natural number $k \mathrel{:=} (N + 1)(N + 2)$ satisfies $k \cdot 1 < t$ , because $t - k \cdot 1$ has leading coefficient $1 > 0$ (Example (A Non-Archimedean Ordered Field)). Since $0 < k \cdot 1 < t$ , Proposition 2.5.2 (b) gives $1/t < 1/(k \cdot 1) = \left| a_m - a_n \right|$ . So for the tolerance $1/t$ no threshold $N$ works, and $(a_n)$ is not Cauchy in $\mathbb{Q}(t)$ .

The terms are the same in both fields; what changed is the set of tolerances. $\mathbb{Q}(t)$ has the positive element $1/t$ , below every positive rational, and the rational differences $1/((N + 1)(N + 2))$ never get below it. Being Cauchy is a property of a sequence in a field, not of its terms alone. (The example $\mathbb{Q}(t)$ uses school polynomial algebra; nothing else in the book depends on this exercise.)

R. Review

Exercise (R1)

Let $\mathcal{C}$ be the set of Cauchy sequences in $\mathbb{Q}$ , and for $(a_n), (b_n) \in \mathcal{C}$ write $(a_n) \sim (b_n)$ if $(a_n - b_n)$ is null. Prove that $\sim$ is an equivalence relation on $\mathcal{C}$ , and that $[(a_n)] + [(b_n)] \mathrel{:=} [(a_n + b_n)]$ is a well-defined operation on the quotient set $\mathcal{C}/{\sim}$ .

Solution. The tool is Chapter 3’s quotient of a commutative ring by an ideal (Theorem 3.4.1). Let $\mathcal{N}$ be the set of null sequences in $\mathbb{Q}$ . We show that $\mathcal{C}$ is a commutative ring, that $\mathcal{N}$ is an ideal of it, and that $\sim$ is the relation $\sim_{\mathcal{N}}$ .

$\mathcal{C}$ is a commutative ring (Definition 2.3.1), with termwise $+$ and $\cdot$ . By Theorem 4.5.3, $\mathcal{C}$ contains the constant sequences $0$ and $1$ by (a), and it is closed under termwise sums and negatives by (b) and under termwise products by (c); so termwise $+$ and $\cdot$ are functions $\mathcal{C} \times \mathcal{C} \to \mathcal{C}$ . Each of (F1)–(F7) and (F9), with the constant $0$ as zero, the constant $1$ as one and $(-a_n)$ as the negative of $(a_n)$ , is an equation between sequences, and it holds at every index $n$ because it holds in $\mathbb{Q}$ (Theorem 2.5.1). Two sequences that agree at every index are equal, so each clause holds in $\mathcal{C}$ .

$\mathcal{N}$ is an ideal of $\mathcal{C}$ (Definition 3.4.1). First, $\mathcal{N} \subseteq \mathcal{C}$ by Theorem 4.5.3 (a). (I1): the constant sequence $0$ tends to $0$ (Example (First Limits) (a)). (I2): if $(y_n), (z_n) \in \mathcal{N}$ , then $y_n + z_n \to 0 + 0 = 0$ by Theorem 4.4.3 (a). (I3): let $(z_n) \in \mathcal{N}$ and $(r_n) \in \mathcal{C}$ . By Proposition 4.5.2 there is $M \in \mathbb{Q}_{>0}$ with $\left| r_n \right| \le M$ for every $n$ , so $(z_n r_n)$ is null by Proposition 4.4.1, and $r_n z_n = z_n r_n$ by (F6) in $\mathbb{Q}$ . So $(r_n z_n) \in \mathcal{N}$ .

The relation is $\sim_{\mathcal{N}}$ . The difference $(a_n) - (b_n)$ in $\mathcal{C}$ is the sequence $(a_n - b_n)$ , so $(a_n) \sim (b_n)$ holds exactly when $(a_n) - (b_n) \in \mathcal{N}$ . Thus $\sim$ is $\sim_{\mathcal{N}}$ and $\mathcal{C}/{\sim}$ is $\mathcal{C}/\mathcal{N}$ . By Theorem 3.4.1 (a), $\sim$ is an equivalence relation, and by (b), $[(a_n)] + [(b_n)] \mathrel{:=} [(a_n + b_n)]$ is well defined; so is the product $[(a_n)] \cdot [(b_n)] \mathrel{:=} [(a_n b_n)]$ , and by (c) $\mathcal{C}/\mathcal{N}$ is a commutative ring.

Chapter 3 proved (b) by Chapter 2’s lemma on operations on classes (Theorem 2.2.1), the method by which $\mathbb{Z}$ and $\mathbb{Q}$ were built; here it runs on sequences. Chapter 5 builds $\mathbb{R}$ as this quotient, and nothing in this exercise is used there.

Exercise (R2)

Let $F$ be an ordered field. Define $r_0 \mathrel{:=} 1$ and $r_{n+1} \mathrel{:=} r_n/2 + 1$ for $n \in \mathbb{N}$ . Prove that $1 \le r_n < 2$ and $r_n < r_{n+1}$ for every $n \in \mathbb{N}$ .

Solution. The tools are definition by recursion and proof by induction (Sets, Relations, and Cardinality, Theorem 2.3.1, Logic and Proof, Axiom 4.2.1), both read on $\mathbb{N} = \omega$ through Corollary 1.7.3 (b). Here $2 \mathrel{:=} 1 + 1 > 0$ (Proposition 4.1.2 (b)), so $2 \ne 0$ and $x/2$ is defined for every $x \in F$ . The recursion theorem with $X = F$ , starting value $1$ and rule $g(n, x) \mathrel{:=} x/2 + 1$ gives exactly one sequence $(r_n)$ in $F$ satisfying the two equations. Its first terms are $r_1 = 3/2$ and $r_2 = 7/4$ .

The bounds. We prove $P(n)$ : “ $1 \le r_n < 2$ ” by induction on $n$ . Base $P(0)$ : $r_0 = 1$ , and $1 = 2/2 < 2$ by Proposition 4.1.2 (b) with $\varepsilon = 2$ . Step: assume $1 \le r_n < 2$ . Then $r_n > 0$ , so $r_n/2 > 0$ (Proposition 2.5.2 (a), (O4)). Multiplying $r_n < 2$ by $1/2 > 0$ gives $r_n/2 < 2/2 = 1$ (Proposition 2.3.5 (c)). Adding $1$ (Proposition 2.3.5 (b)), $1 = 0 + 1 < \frac{r_n}{2} + 1 = r_{n+1} < 1 + 1 = 2 .$ So $1 \le r_{n+1} < 2$ , which is $P(n + 1)$ .

The increase. Let $n \in \mathbb{N}$ . By $P(n)$ , $r_n > 0$ , so $r_n = r_n/2 + r_n/2$ (Proposition 4.1.2 (b) with $\varepsilon = r_n$ ), and $r_n/2 < 1$ as in the step. Hence $r_{n+1} - r_n = \Bigl(\frac{r_n}{2} + 1\Bigr) - \Bigl(\frac{r_n}{2} + \frac{r_n}{2}\Bigr) = 1 - \frac{r_n}{2} > 0 ,$ and $r_n < r_{n+1}$ by Proposition 2.3.5 (a).

Exercise (R3)

Say that a sequence $(a_n)$ in an ordered field $F$ eventually keeps one sign if there are $c \in F_{>0}$ and $N \in \mathbb{N}$ such that either $a_n \ge c$ for every $n \ge N$ , or $a_n \le -c$ for every $n \ge N$ . Write this in symbols, and form its negation by moving $\neg$ inward one law at a time, naming each law. Then use the negation to show that $a_n \mathrel{:=} (-1)^n/(n + 1)$ in $\mathbb{Q}$ does not eventually keep one sign, and explain why this does not contradict the theorem that a Cauchy sequence that is not null eventually keeps one sign.

Solution. “ $(a_n)$ eventually keeps one sign” is $\exists c \in F_{>0} \ \exists N \in \mathbb{N} \ \Bigl( \forall n \in \mathbb{N} \ (n \ge N \to a_n \ge c) \ \vee \ \forall n \in \mathbb{N} \ (n \ge N \to a_n \le -c) \Bigr) .$ Negating, with the laws for bounded quantifiers (Logic and Proof, Proposition 6.2.3), De Morgan’s laws (Logic and Proof, Proposition 2.5.5) and negated implication (Logic and Proof, Proposition 6.2.2):

$\forall c \in F_{>0} \ \neg \exists N \in \mathbb{N} \ (\dots)$ , by (b) of the bounded law;
$\forall c \in F_{>0} \ \forall N \in \mathbb{N} \ \neg \bigl( \forall n \, (\dots) \vee \forall n \, (\dots) \bigr)$ , by (b) again;
$\forall c \in F_{>0} \ \forall N \in \mathbb{N} \ \bigl( \neg \forall n \, (\dots) \wedge \neg \forall n \, (\dots) \bigr)$ , by De Morgan (a) (and (b) for the converse);
$\forall c \in F_{>0} \ \forall N \in \mathbb{N} \ \bigl( \exists n \in \mathbb{N} \ \neg (n \ge N \to a_n \ge c) \wedge \exists n \in \mathbb{N} \ \neg (n \ge N \to a_n \le -c) \bigr)$ , by (a) of the bounded law, twice;
$\forall c \in F_{>0} \ \forall N \in \mathbb{N} \ \bigl( \exists n \in \mathbb{N} \ (n \ge N \wedge \neg (a_n \ge c)) \wedge \exists n \in \mathbb{N} \ (n \ge N \wedge \neg (a_n \le -c)) \bigr)$ , by Logic and Proof, Proposition 6.2.2, twice;
and $\neg (a_n \ge c)$ is $a_n < c$ , $\neg (a_n \le -c)$ is $a_n > -c$ , by totality (Proposition 4.1.2 (a)).

(The $\vdash$ directions of steps 4 and 5 use $\mathrm{RAA}$ , as Logic and Proof, Proposition 6.2.3 and Logic and Proof, Proposition 6.2.2 record.) So the negation says: for every $c \in F_{>0}$ and every $N \in \mathbb{N}$ , some $n \ge N$ has $a_n < c$ , and some $n \ge N$ has $a_n > -c$ .

The example. Here $(-1)^n$ is the power in $\mathbb{Q}$ (Definition 4.2.1), so $(-1)^{n+1} = -(-1)^n$ (Proposition 2.3.2 (c)), and by induction $(-1)^n$ is $1$ or $-1$ for every $n$ . Let $c \in \mathbb{Q}_{>0}$ and $N \in \mathbb{N}$ . Of $(-1)^N$ and $(-1)^{N+1} = -(-1)^N$ , one is $1$ and the other $-1$ ; call $p$ the index among $N, N + 1$ with $(-1)^p = 1$ , and $q$ the other. Both are $\ge N$ , and $1/(p + 1) > 0$ , $1/(q + 1) > 0$ (Proposition 2.5.2 (a)). So $a_q = -1/(q + 1) < 0 < c$ and $a_p = 1/(p + 1) > 0 > -c$ (Proposition 2.3.5 (a)). This is the negation, so $(a_n)$ does not eventually keep one sign.

No contradiction. $\left| a_n \right| = \left| (-1)^n \right| \cdot \left| 1/(n + 1) \right| = 1/(n + 1)$ (Proposition 4.1.3 (b)), and $(1/(n + 1))$ is null in $\mathbb{Q}$ (Example (First Limits) (b)). So for each $\varepsilon \in \mathbb{Q}_{>0}$ the threshold that serves $(1/(n + 1))$ gives $\left| a_n - 0 \right| < \varepsilon$ : the sequence $(a_n)$ is null. It is Cauchy (Theorem 4.5.3 (a)), but the theorem (Theorem 4.5.4) assumes “not null”, so it says nothing about $(a_n)$ . The example shows that this hypothesis cannot be dropped.

Exercise (R4)

Let $(a_n)$ be a sequence in $\mathbb{Q}$ with $a_n > 0$ for every $n$ and $a_n^2 \to 2$ in $\mathbb{Q}$ . Is $(a_n)$ a Cauchy sequence in $\mathbb{Q}$ ? Prove your answer.

Solution. Yes. The tool is the factorization $a_n^2 - a_m^2 = (a_n - a_m)(a_n + a_m)$ , which turns closeness of the squares into closeness of the terms once the factor $a_n + a_m$ is bounded below by a positive constant.

A lower bound. By Lemma 4.4.2 applied to $a_n^2 \to 2 > 0$ , there is $N_0$ with $a_n^2 > 2/2 = 1$ for every $n \ge N_0$ . For such $n$ , $a_n > 1$ : otherwise $0 < a_n \le 1$ would give $a_n^2 \le 1$ (Proposition 2.3.5 (g)). So $a_n + a_m > 2$ for $m, n \ge N_0$ , and $1/(a_n + a_m) < 1/2$ (Proposition 2.5.2 (b)).

The estimate. For $m, n \ge N_0$ , dividing the factorization by $a_n + a_m \ne 0$ , $\left| a_n - a_m \right| = \frac{\left| a_n^2 - a_m^2 \right|}{a_n + a_m} \le \frac{\left| a_n^2 - a_m^2 \right|}{2} .$ The sequence $(a_n^2)$ converges, so it is Cauchy (Proposition 4.5.1). Given $\varepsilon \in \mathbb{Q}_{>0}$ , choose $N_1$ with $\left| a_n^2 - a_m^2 \right| < 2\varepsilon$ for all $m, n \ge N_1$ , and let $N \mathrel{:=} \max\{N_0, N_1\}$ . For $m, n \ge N$ , $\left| a_n - a_m \right| < 2\varepsilon/2 = \varepsilon$ . So $(a_n)$ is Cauchy.

Why the look-alike tools fail. The limit laws would need a limit of $(a_n)$ , and there is none in $\mathbb{Q}$ : $a_n \to L$ would give $a_n^2 \to L^2$ , so $L^2 = 2$ , against Theorem 2.6.1. Theorem 4.5.4 and Proposition 4.5.6 presuppose that $(a_n)$ is Cauchy, which is what is asked. The Newton sequence of Theorem 4.6.1 is one such $(a_n)$ , so the question is not empty.