5.1 Sequences That Should Converge

Chapter 4 ended with a rational sequence that is Cauchy in $\mathbb{Q}$ and converges to no rational (Theorem 4.6.1). Its terms crowd around a place where $\mathbb{Q}$ has a hole. This chapter builds the number that belongs in the hole, and the first step is to notice that many different sequences crowd around the same hole. This section sets up the raw material, the set $\mathcal{C}$ of Cauchy sequences of rationals, and the relation that will decide when two of them aim at the same number: their difference dies out. Nothing about real numbers is assumed. Every tolerance, bound and threshold in this section is a rational number.

5.1.1. Two sequences aimed at one hole

The first sequence is the Newton sequence of Chapter 2 (Example (A Rational Sequence Aimed at the Gap)): $x_0 \mathrel{:=} 2$ and $x_{n+1} \mathrel{:=} \frac{x_n^2 + 2}{2 x_n} = \frac{x_n}{2} + \frac{1}{x_n} \qquad (n \in \mathbb{N}) ,$ with error $e_n \mathrel{:=} x_n^2 - 2$ . Its first terms are $2, 3/2, 17/12, 577/408$ . We shall use the following facts, each proved earlier, for every $n \in \mathbb{N}$ :

(NS1) $x_n \in \mathbb{Q}_{>0}$ , and $e_n > 0$ , that is, $x_n^2 > 2$ (Example (A Rational Sequence Aimed at the Gap));
(NS2) $x_n > 1$ , and $e_n \le 1/(4n)$ when $n \ge 1$ (the first clauses of the statement of Theorem 4.6.1);
(NS3) $(x_n)$ is a Cauchy sequence in $\mathbb{Q}$ , and there is no $L \in \mathbb{Q}$ with $x_n \to L$ (Theorem 4.6.1).

From (NS1) and (NS2), $0 < x_n^2 - 2 \le 1/(4n)$ for every $n \ge 1$ . At $n = 0$ the expression $1/(4n)$ is not defined, and indeed $x_0^2 - 2 = 2$ is not small.

The second sequence approaches the hole from below, by decimal truncation. To define it inside $\mathbb{Q}$ , without the school decimals, we need powers of ten.

Powers of ten. For $k \in \mathbb{N}$ , $10^k$ is the power in the ordered field $\mathbb{Q}$ of Definition 4.2.1 (b): $10^0 = 1$ and $10^{k+1} = 10^k \cdot 10$ . (Here $10 = 10 \cdot 1_{\mathbb{Q}}$ , by the identification $\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q}$ of Chapter 2 and Proposition 4.2.1 (d).) Two facts about it are used below, both by induction (Logic and Proof, Axiom 4.2.1, read on $\mathbb{N} = \omega$ through Corollary 1.7.3 (b)) with base $P(0)$ .

$10^k \in \mathbb{Z}$ . Base: $10^0 = 1 \in \mathbb{Z}$ . Step: if $10^k \in \mathbb{Z}$ , then $10^{k+1} = 10^k \cdot 10$ is a product of two integers, and products of integers computed in $\mathbb{Q}$ are integers (Proposition 2.4.4: $j(m) j(n) = j(mn)$ ).
$10^k \ge k + 1$ . Base: $10^0 = 1 = 0 + 1$ . Step: suppose $10^k \ge y$ , where $y \mathrel{:=} k + 1$ . Then $y \ge 1$ (Proposition 4.2.1 (b)), and multiplying by $10 > 0$ gives $10^{k+1} = 10^k \cdot 10 \ge 10y$ (by Proposition 2.3.5 (c) if $10^k > y$ ; trivially if $10^k = y$ ). Moreover $10y - (y + 1) = 9y - 1 \ge 9 - 1 > 0$ . So $10^{k+1} > y + 1 = k + 2$ , where $(k + 1) + 1 = k + 2$ is arithmetic in $\mathbb{N}$ (Theorem 1.5.3), carried into $\mathbb{Q}$ by the sum law of Proposition 4.2.1 (a).

In particular $10^k \ge 1 > 0$ , so $1/10^k > 0$ (Proposition 2.5.2 (a)), and Proposition 4.1.2 (c), applied to $0 < k + 1 \le 10^k$ , gives $1/10^k \le 1/(k + 1)$ . Together,

0 < \frac{1}{10^k} \le \frac{1}{k + 1} \qquad (k \in \mathbb{N}) .

(5.1.1)

The inequality is not strict at $k = 0$ , where both sides are $1$ . We write $1/10^k$ throughout; negative powers have not been defined.

The truncations. For $k \in \mathbb{N}$ , let $m_k$ be the largest natural number $m$ with $m^2 \le 2 \cdot (10^k)^2 ,$ and let $d_k \mathrel{:=} m_k / 10^k$ . In school terms, $d_k$ is $\sqrt 2$ cut off after $k$ decimal places; but the definition mentions only integers and the rational $10^k$ .

That such a largest $m$ exists, and is unique, is a fact about sets of integers. Let $S_k \mathrel{:=} \{ m \in \mathbb{Z} : m \ge 0 \text{ and } m^2 > 2 \cdot (10^k)^2 \} .$ It is bounded below by $0$ , and it is non-empty: $2 \cdot 10^k$ is a non-negative integer, and $(2 \cdot 10^k)^2 = 4 (10^k)^2 > 2 (10^k)^2$ because $(10^k)^2 > 0$ . By Proposition 2.3.6, $S_k$ has a least element $m^\ast$ . Since $0^2 = 0 \le 2 (10^k)^2$ , $0 \notin S_k$ , so $m^\ast \ge 1$ by discreteness (Theorem 2.3.4 (c)), hence $m_k \mathrel{:=} m^\ast - 1 \ge 0$ is a natural number (Theorem 2.3.4 (b)). It is not in $S_k$ , being smaller than the least element, so $m_k^2 \le 2 (10^k)^2$ . Every natural number $m > m_k$ satisfies $m \ge m^\ast$ (discreteness again), so $m^2 \ge (m^\ast)^2 > 2 (10^k)^2$ (by Proposition 2.3.5 (g) if $m > m^\ast$ ; trivially if $m = m^\ast$ ). So $m_k$ is the largest natural number with $m^2 \le 2 (10^k)^2$ , and there is exactly one. Because the description singles out one number for each $k$ , the rule $k \mapsto d_k$ is a function $\mathbb{N} \to \mathbb{Q}$ (Sets, Relations, and Cardinality, Definition 1.4.1), with no choices made.

The first values are: $\begin{array}{c|ccccccc} k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline m_k & 1 & 14 & 141 & 1414 & 14142 & 141421 & 1414213 \end{array}$ For instance $m_1 = 14$ , because $14^2 = 196 \le 200 = 2 \cdot 10^2$ and $15^2 = 225 > 200$ . So $d_0 = 1$ , $d_1 = 7/5$ , $d_2 = 141/100$ , $d_3 = 707/500$ .

Different sequences, one intended number. The two sequences never meet: $x_k^2 > 2 \ge d_k^2$ for every $k$ , so $x_k \ne d_k$ . They approach from opposite sides, and their differences $x_1 - d_1 = 1/10$ , $x_2 - d_2 = 1/150$ , $x_3 - d_3 = 11/51000$ shrink fast. Both “should” converge to the same number, and $\mathbb{Q}$ has no such number. The plan of the chapter is to make the sequences themselves into the numbers, and for that we must first say when two sequences count as one.

5.1.2. Cauchy sequences of rationals

The raw material is every sequence that behaves as if it had a limit.

Definition 5.1.1 (Cauchy Sequences of Rationals)

$\mathcal{C}$ is the set of all sequences $a \colon \mathbb{N} \to \mathbb{Q}$ (Definition 4.3.1, $F = \mathbb{Q}$ ) that are Cauchy sequences in $\mathbb{Q}$ (Definition 4.5.1): for every $\varepsilon \in \mathbb{Q}_{>0}$ there is $N \in \mathbb{N}$ with $\left| a_m - a_n \right| < \varepsilon$ for all $m, n \ge N$ . In symbols, $a \in \mathcal{C}$ means $\begin{aligned} &\forall \varepsilon \in \mathbb{Q}_{>0} \ \ \exists N \in \mathbb{N} \ \ \forall m \in \mathbb{N} \ \ \forall n \in \mathbb{N} \\ &\qquad \bigl( (m \ge N \wedge n \ge N) \Rightarrow \left| a_m - a_n \right| < \varepsilon \bigr) . \end{aligned}$ A sequence $a$ of rationals is null if $a_n \to 0$ in $\mathbb{Q}$ (Definition 4.3.3, $F = \mathbb{Q}$ ).

We write a sequence as a single letter, $a = (a_n)_{n \in \mathbb{N}}$ , and do arithmetic on sequences termwise: $a + b \mathrel{:=} (a_n + b_n)_n$ , $ab \mathrel{:=} (a_n b_n)_n$ , $-a \mathrel{:=} (-a_n)_n$ and $a - b \mathrel{:=} (a_n - b_n)_n$ . For $q \in \mathbb{Q}$ , $(q)_n$ is the constant sequence with every term $q$ .

Nothing is new here except the name: this is Chapter 4’s definition with $F = \mathbb{Q}$ , so every tolerance $\varepsilon$ is rational. That is the point. The definition can be read by someone who knows only $\mathbb{Q}$ , and it will be used to build a larger field without assuming anything about it.

Examples. Every constant sequence $(q)_n$ is in $\mathcal{C}$ , with $N = 0$ for every $\varepsilon$ . The sequence $(1/(n + 1))_n$ is null (Example (First Limits) (b)), so it is in $\mathcal{C}$ (Theorem 4.5.3 (a)). The Newton sequence $(x_n)$ is in $\mathcal{C}$ , by (NS3), and is not null, since $x_n > 1$ for every $n$ . The sequence $(n)_n$ is not in $\mathcal{C}$ : a Cauchy sequence is bounded (Proposition 4.5.2), and for every $M \in \mathbb{Q}_{>0}$ some $n \in \mathbb{N}$ has $n > M$ (Theorem 2.5.3).

The toolkit from Chapter 4, with $F = \mathbb{Q}$ . This chapter uses the following facts so often that we list them once. Each was proved in Chapter 4 for an arbitrary ordered field; here $F = \mathbb{Q}$ .

Constant sequences and null sequences are in $\mathcal{C}$ , and $\mathcal{C}$ is closed under $+$ , $-$ , $\cdot$ and negatives (Theorem 4.5.3).
Sums, negatives and constant multiples of null sequences are null (Theorem 4.4.3 (a), (b)).
A null sequence times a bounded sequence is null (Proposition 4.4.1).
Every member of $\mathcal{C}$ is bounded (Proposition 4.5.2).
Changing finitely many terms changes no limit, and so no nullity (Proposition 4.3.2 (a)).
A sequence squeezed, from some index on, between two sequences with the same limit has that limit too (Proposition 4.4.4 (c)); in particular one squeezed between $(0)_n$ , or $(-u_n)_n$ , and a null $(u_n)_n$ is null.

5.1.3. When two sequences name the same number

The Newton sequence and the truncations should name one number, yet they share no term. “Eventually equal” is therefore too strict a test. What the two sequences do share is visible in the differences above: $x_k - d_k$ shrinks to nothing. In $\mathbb{Q}$ we cannot compare the two sequences through a common limit, since there is none; but their difference is again a sequence of rationals, and whether it tends to $0$ is a question $\mathbb{Q}$ can answer.

Two Cauchy sequences are equivalent when their difference dies out.

Definition 5.1.2 (Equivalent Cauchy Sequences)

For $a, b \in \mathcal{C}$ , we write $a \sim b$ , and say that $a$ is equivalent to $b$ , if the sequence $a - b = (a_n - b_n)_n$ is null. In symbols, $a \sim b$ means $\forall \varepsilon \in \mathbb{Q}_{>0} \ \ \exists N \in \mathbb{N} \ \ \forall n \in \mathbb{N} \ \ \bigl( n \ge N \Rightarrow \left| a_n - b_n \right| < \varepsilon \bigr) .$

In words: whatever rational tolerance is named, from some index on, the two sequences agree to within it at the same index. The threshold $N$ comes after $\varepsilon$ , so it may depend on $\varepsilon$ . The comparison is always between $a_n$ and $b_n$ with the same $n$ ; nothing is said about $a_m$ against $b_n$ . The relation is defined only on $\mathcal{C}$ : both sequences must be Cauchy before we ask whether they are equivalent.

Examples.

Constant sequences (the degenerate case). For $p, q \in \mathbb{Q}$ , $(p)_n \sim (q)_n$ if and only if $p = q$ . The difference is the constant $(p - q)_n$ , which converges to $p - q$ (Example (First Limits) (a)); by uniqueness of limits (Theorem 4.3.4) it is null exactly when $p - q = 0$ . So on constant sequences $\sim$ is plain equality, as it must be if $(q)_n$ is to stand for $q$ .
A null sequence and zero. $(1/(n + 1))_n \sim (0)_n$ : the difference is $(1/(n + 1))_n$ , null by Example (First Limits) (b). No term of the first sequence is $0$ .
The truncations and the Newton sequence. $(d_k) \sim (x_k)$ ; this is Example (The Truncations and the Newton Sequence Are Equivalent) below.

Non-example by a minimal change. Shift the null sequence of the second example up by one: $b_n \mathrel{:=} 1 + 1/(n + 1)$ . It is still in $\mathcal{C}$ (a constant plus a null sequence, Theorem 4.5.3 (a), (b)), and $b - (1)_n = (1/(n + 1))_n$ is still null, so $b \sim (1)_n$ . But $b \not\sim (0)_n$ : the clause that fails is “for every $\varepsilon$ ”. With $\varepsilon = 1$ , every $n$ has $\left| b_n - 0 \right| = 1 + 1/(n + 1) \ge 1$ , so no threshold exists.

Why this definition.

Why “null”, and not “same limit”. Two sequences with a common limit in $\mathbb{Q}$ have null difference (Theorem 4.4.3 (b)). Conversely, if $a \to L$ and $b \to L'$ with $a - b$ null, then $a - b$ tends to both $L - L'$ and $0$ , so $L = L'$ (Theorem 4.3.4). So for convergent sequences the new relation says exactly “same limit”. But it is stated without mentioning any limit, so it applies equally to $(x_k)$ and $(d_k)$ , which have none in $\mathbb{Q}$ .
Why not “eventually equal”. Then $(x_k)$ and $(d_k)$ would name different numbers, and so would $(1/(n + 1))_n$ and $(0)_n$ . Sequences that agree ever more closely, without ever agreeing exactly, would never be identified.
Why only on $\mathcal{C}$ . On all sequences of rationals the same relation would not respect products, and Section 5.2 needs it to. For instance $(1/(n + 1))_n$ and $(0)_n$ have null difference, but multiplying both termwise by $(n + 1)_n$ , which is not Cauchy, gives $(1)_n$ and $(0)_n$ , whose difference is not null. Inside $\mathcal{C}$ every multiplier is bounded, and that is what saves the product.

It must be checked that $\sim$ really sorts sequences into groups, that is, that it is an equivalence relation in the sense of Sets, Relations, and Cardinality, Section 2.5.

Proposition 5.1.1 (Equivalence of Cauchy Sequences Is an Equivalence Relation)

The relation $\sim$ of Definition 5.1.2 is an equivalence relation on $\mathcal{C}$ (Sets, Relations, and Cardinality, Definition 2.5.1).

Idea. Each of the three clauses becomes a statement about one difference sequence. Reflexivity looks at $a - a$ , the zero sequence. Symmetry looks at $b - a$ , the negative of $a - b$ . Transitivity writes $a - c$ as the sum $(a - b) + (b - c)$ of two null sequences. Before reading on: which fact from Chapter 4 does transitivity use, and where is the triangle inequality hiding?

Proof. Let $a, b, c \in \mathcal{C}$ .

(Eq1) $a - a = (0)_n$ , which is null (Example (First Limits) (a)). So $a \sim a$ .

(Eq2) Suppose $a \sim b$ . For every $n$ , $b_n - a_n = -(a_n - b_n)$ (since $(a_n - b_n) + (b_n - a_n) = 0$ by (F1)–(F4), and negatives are unique, Proposition 2.3.2 (a)), so $b - a = -(a - b)$ , which is null by Theorem 4.4.3 (b) ( $-0 = 0$ ). So $b \sim a$ .

(Eq3) Suppose $a \sim b$ and $b \sim c$ . For every $n$ , $a_n - c_n = (a_n - b_n) + (b_n - c_n) ,$ so $a - c = (a - b) + (b - c)$ , a sum of two null sequences. By the sum rule Theorem 4.4.3 (a), it is null ( $0 + 0 = 0$ ). So $a \sim c$ .

This proves that $\sim$ is an equivalence relation on $\mathcal{C}$ .

The answer to the prompt: transitivity uses the sum rule of the limit laws, Theorem 4.4.3 (a), and the triangle inequality is inside its proof, where $\left| (a_n - b_n) + (b_n - c_n) \right| \le \left| a_n - b_n \right| + \left| b_n - c_n \right|$ splits the tolerance into two halves. Written out directly: given $\varepsilon$ , take thresholds for $a - b$ and $b - c$ with tolerance $\varepsilon/2$ , and their maximum serves $a - c$ .

By Sets, Relations, and Cardinality, Theorem 2.5.1, $\mathcal{C}$ now falls apart into disjoint classes, and two Cauchy sequences lie in the same class exactly when their difference is null. Section 5.2 takes these classes as the real numbers.

5.1.4. The truncations and the Newton sequence

The two sequences of the hook are the first test of the definition.

Example (The Truncations and the Newton Sequence Are Equivalent)

Show that $(d_k)$ is non-decreasing, that $(d_k) \in \mathcal{C}$ , and that $(d_k) \sim (x_k)$ .

Solution. Step 1: $(d_k)$ is non-decreasing. Let $k \in \mathbb{N}$ . By the choice of $m_k$ and the defining equation $10^{k+1} = 10^k \cdot 10$ , $(10 m_k)^2 = 100 \, m_k^2 \le 200 \, (10^k)^2 = 2 \, (10^k \cdot 10)^2 = 2 \, (10^{k+1})^2 .$ So $10 m_k$ is a natural number whose square is at most $2 (10^{k+1})^2$ , and $m_{k+1}$ is the largest such: $10 m_k \le m_{k+1}$ . Dividing by $10^{k+1} > 0$ (Proposition 2.5.2 (a), and Proposition 2.3.5 (c) if $10 m_k < m_{k+1}$ ; trivially if they are equal), $d_{k+1} = \frac{m_{k+1}}{10^{k+1}} \ge \frac{10 m_k}{10^k \cdot 10} = \frac{m_k}{10^k} = d_k .$ By Logic and Proof, Axiom 4.2.1 on $i$ , with base $P(0)$ ( $d_k \le d_k$ ) and the step just proved, $d_k \le d_{k+i}$ for every $i \in \mathbb{N}$ . Every $j \ge k$ is $k + i$ for some $i \in \mathbb{N}$ (Proposition 1.6.3 (a)), so $d_k \le d_j$ whenever $j \ge k$ . In particular $d_k \ge d_0 = 1$ for every $k$ ( $m_0 = 1$ , since $1^2 \le 2 < 2^2$ ). No law of exponents was used, only the defining equation of $10^{k+1}$ .

Step 2: $d_k \le d_j < d_k + 1/10^k$ for $j \ge k$ , and $(d_k) \in \mathcal{C}$ . The lower bound is Step 1. For the upper bound, $m_j^2 \le 2 (10^j)^2$ gives $d_j^2 \le 2$ . Since $m_k + 1 > m_k$ , the maximality of $m_k$ gives $(m_k + 1)^2 > 2 (10^k)^2$ , that is, $\Bigl( d_k + \frac{1}{10^k} \Bigr)^2 = \frac{(m_k + 1)^2}{(10^k)^2} > 2 .$ If we had $d_j \ge d_k + 1/10^k$ , then, both sides being non-negative, $d_j^2 \ge (d_k + 1/10^k)^2 > 2$ (Proposition 2.3.5 (g)), against $d_j^2 \le 2$ . By trichotomy, $d_j < d_k + 1/10^k$ . With Eq. 5.1.1,

0 \le d_j - d_k < \frac{1}{10^k} \le \frac{1}{k + 1} \qquad (j \ge k) .

(5.1.2)

Now let $\varepsilon \in \mathbb{Q}_{>0}$ . By Corollary 2.5.4 there is $n_\varepsilon \in \mathbb{Z}_{>0}$ with $1/m < \varepsilon$ for every integer $m \ge n_\varepsilon$ . Let $N \mathrel{:=} n_\varepsilon$ , which depends on $\varepsilon$ only. For $j, k \ge N$ , say with $j \ge k$ (the other case is symmetric, as $\left| d_j - d_k \right| = \left| d_k - d_j \right|$ ), Eq. 5.1.2 gives $\left| d_j - d_k \right| < 1/(k + 1) < \varepsilon$ , since $k + 1 > N$ . So $(d_k) \in \mathcal{C}$ .

Step 3: $0 \le 2 - d_k^2 < 5/10^k$ . The first inequality is $d_k^2 \le 2$ . For the second, expand the display of Step 2 (Proposition 2.3.2 (d)): $2 < d_k^2 + \frac{2 d_k}{10^k} + \frac{1}{10^k} \cdot \frac{1}{10^k} .$ Here $d_k < 2$ , since $0 \le d_k$ and $d_k^2 \le 2 < 4 = 2^2$ (Proposition 2.3.5 (g)); and $(1/10^k)(1/10^k) \le 1/10^k$ , since $0 < 1/10^k \le 1$ by Eq. 5.1.1. Multiplying $d_k < 2$ by $2/10^k > 0$ (Proposition 2.3.5 (c)) and adding the two bounds (Proposition 2.3.5 (b)), $2 - d_k^2 < 4/10^k + 1/10^k = 5/10^k$ .

Step 4: $(d_k) \sim (x_k)$ . Let $k \ge 1$ . By (NS2), $x_k > 1$ , and $d_k \ge 1$ by Step 1, so $x_k + d_k \ge 1$ . Since $\left| x_k - d_k \right| \ge 0$ , Proposition 4.1.2 (d) gives $\begin{aligned} \left| x_k - d_k \right| &\le \left| x_k - d_k \right| (x_k + d_k) = \left| x_k^2 - d_k^2 \right| \\ &\le \left| x_k^2 - 2 \right| + \left| 2 - d_k^2 \right| \le \frac{1}{4k} + \frac{5}{10^k} , \end{aligned}$ by Proposition 4.1.3 (b) and (e), the bound $0 < x_k^2 - 2 \le 1/(4k)$ from (NS1)–(NS2), and Step 3. Since $4k - (k + 1) = 3k - 1 > 0$ , $1/(4k) \le 1/(k + 1)$ (Proposition 4.1.2 (c)). Define, for every $k \in \mathbb{N}$ , $u_k \mathrel{:=} \frac{1}{k + 1} + \frac{5}{10^k} .$ Then $-u_k \le x_k - d_k \le u_k$ for every $k \ge 1$ (Proposition 4.1.3 (d)). The sequence $(u_k)$ is null: $(1/(k + 1))$ is null (Example (First Limits) (b)); $(1/10^k)$ is null by the squeeze Proposition 4.4.4 (c) between $(0)_k$ and $(1/(k + 1))$ , using Eq. 5.1.1; $(5/10^k)$ is null by Theorem 4.4.3 (b) with $c = 5$ ; and the sum of two null sequences is null (Theorem 4.4.3 (a)). So $(-u_k)$ is null too, by (b) with $c = -1$ . The squeeze Proposition 4.4.4 (c), with $N_0 = 1$ , lower sequence $(-u_k)$ and upper sequence $(u_k)$ , shows that $(x_k - d_k)$ is null. Both sequences are in $\mathcal{C}$ (by (NS3) and Step 2), so $(x_k) \sim (d_k)$ , and $(d_k) \sim (x_k)$ by symmetry.

The bound of Step 4 is crude but honest: at $k = 1$ it gives $\left| x_1 - d_1 \right| \le 1/4 + 5/10 = 3/4$ , while in fact $x_1 - d_1 = 3/2 - 7/5 = 1/10$ .

The upper sequence $(u_k)$ is defined for every $k$ , including $k = 0$ , where $1/(4k)$ is not; the squeeze only needs the inequality from $N_0 = 1$ on. One consequence is worth recording at once: $(d_k)$ has no limit in $\mathbb{Q}$ either. If $d_k \to L \in \mathbb{Q}$ , then $x_k = d_k + (x_k - d_k) \to L + 0 = L$ by the sum rule, against (NS3). So the truncations, like the Newton sequence, are Cauchy and aim at nothing in $\mathbb{Q}$ , and Example (The Truncations and the Newton Sequence Are Equivalent) says they aim at the same nothing.

5.1.5. Finite changes, and shifts

A class will contain far more than the two sequences of the hook. The next example shows how loose the relation is at the start of a sequence.

Example (Finite Changes and Shifts)

(a) Let $a \in \mathcal{C}$ , let $b \colon \mathbb{N} \to \mathbb{Q}$ , and suppose there is $N_0 \in \mathbb{N}$ with $a_n = b_n$ for every $n \ge N_0$ . Show that $b \in \mathcal{C}$ and $a \sim b$ .
(b) Let $a \in \mathcal{C}$ , and let $s \mathrel{:=} (a_{n+1})_{n \in \mathbb{N}}$ be the shifted sequence. Show that $s \in \mathcal{C}$ and $s \sim a$ .

Solution.

(a) $b \in \mathcal{C}$ by the tail-change remark after Definition 4.5.1 (Section 4.5). For $n \ge N_0$ , $a_n - b_n = 0$ . So $a - b$ agrees with the null sequence $(0)_n$ from $N_0$ on, and is null by Proposition 4.3.2 (a). Hence $a \sim b$ .
(b) Let $\varepsilon \in \mathbb{Q}_{>0}$ , and let $N$ be a threshold for $a$ with tolerance $\varepsilon$ (Definition 5.1.1). For $m, n \ge N$ , also $m + 1, n + 1 \ge N$ , so $\left| s_m - s_n \right| = \left| a_{m+1} - a_{n+1} \right| < \varepsilon$ : $s \in \mathcal{C}$ , with the same thresholds. For $n \ge N$ , apply the Cauchy condition to the pair $(n + 1, n)$ , both indices $\ge N$ : $\left| s_n - a_n \right| = \left| a_{n+1} - a_n \right| < \varepsilon .$ So $s - a$ is null, and $s \sim a$ .

By (a), a representative of a class may begin with any finite list of rationals: $(5, -3, 7, 1/4, 1/5, 1/6, \dots)$ , which is $1/(n + 1)$ from $n = 3$ on, is equivalent to $(1/(n + 1))_n$ , and so to $(0)_n$ . Part (b) uses the Cauchy condition with the two indices $n + 1$ and $n$ ; a sequence of rationals that is not Cauchy can fail it (for $((-1)^n)_n$ , every $\left| a_{n+1} - a_n \right|$ is $2$ ).

Warning. Equivalent is not “eventually equal”, and not “close at the start”. $(1/(n + 1))_n \sim (0)_n$ , though no term of the first sequence is $0$ . And $(0)_n$ and $(1 - 1/(n + 1))_n$ have the same first term, $0$ , but are not equivalent: their difference $(0)_n - (1 - 1/(n + 1))_n$ converges to $-1$ (Theorem 4.4.3 (a), (b) with Example (First Limits) (a), (b)), so it is not null, by uniqueness of limits (Theorem 4.3.4). Only the behavior far out counts, and it counts at every tolerance.

Quick check. Let $a \mathrel{:=} (1, 0, 1, 0, \dots)$ , with $a_n = 1$ for even $n$ and $a_n = 0$ for odd $n$ ; and let $b \mathrel{:=} (1, 0, 1/2, 0, 1/3, 0, \dots)$ , with $b_{2k} = 1/(k + 1)$ and $b_{2k+1} = 0$ . Which of them lies in $\mathcal{C}$ ? For the one that does, find a constant sequence equivalent to it.

Solution. $a \notin \mathcal{C}$ . The negation of the Cauchy condition (moving $\neg$ inward as in Logic and Proof, Proposition 6.2.3) reads $\exists \varepsilon \in \mathbb{Q}_{>0} \ \ \forall N \in \mathbb{N} \ \ \exists m, n \ge N \ \ \left| a_m - a_n \right| \ge \varepsilon ,$ and it holds with $\varepsilon = 1/2$ : for any $N$ , the indices $m = N$ and $n = N + 1$ have one even and one odd (Proposition 1.6.4 (d)), so $\left| a_m - a_n \right| = 1 \ge 1/2$ .

$b \in \mathcal{C}$ , and $b \sim (0)_n$ . Indeed $b$ is null: given $\varepsilon \in \mathbb{Q}_{>0}$ , Corollary 2.5.4 gives $K \in \mathbb{Z}_{>0}$ with $1/m < \varepsilon$ for every integer $m \ge K$ . For $n \ge 2K$ , $n$ is odd or of the form $2k$ (Proposition 1.6.4 (d)), and in the second case $k \ge K$ . So either $n$ is odd and $b_n = 0 < \varepsilon$ , or $n = 2k$ with $k \ge K$ and $b_n = 1/(k + 1) < \varepsilon$ . So $b$ is null, hence in $\mathcal{C}$ (Theorem 4.5.3 (a)), and $b - (0)_n = b$ is null. The pattern “a non-zero term every other index” is the same in $a$ and $b$ ; what differs is whether those terms die out.

The relation is in place, and it is an equivalence relation. The next section takes its classes as the real numbers and gives them an arithmetic.

5.1.6. Exercises

A. Check your understanding

Exercise (A1)

(a) For each sequence of rationals, decide whether it lies in $\mathcal{C}$ and whether it is null, with a one-line reason: $((-1)^n/(n + 1))_n$ ; $(n)_n$ ; $(1 + 1/(n + 1))_n$ ; $(d_k)_k$ ; $((-1)^n)_n$ .
(b) Write “ $a \not\sim b$ ”, for $a, b \in \mathcal{C}$ , in symbols, with no $\neg$ in front of a quantifier.
(c) True or false: if $a \sim b$ , then $a_n = b_n$ for at least one $n$ . Give a reason.

Solution.

(a)
- $((-1)^n/(n + 1))$ : in $\mathcal{C}$ and null. Its absolute value is $1/(n + 1)$ (Proposition 4.1.3 (b), $\left| (-1)^n \right| = 1$ ), which is below any $\varepsilon \in \mathbb{Q}_{>0}$ from some index on (Example (First Limits) (b)); null sequences are in $\mathcal{C}$ (Theorem 4.5.3 (a)).
- $(n)$ : neither. It is not bounded (Theorem 2.5.3), so it is not Cauchy (Proposition 4.5.2), and not null (a null sequence is convergent, hence bounded, Proposition 4.3.5).
- $(1 + 1/(n + 1))$ : in $\mathcal{C}$ , not null. It converges to $1$ (Theorem 4.4.3 (a)), so it is Cauchy (Proposition 4.5.1), and its limit is not $0$ (Theorem 4.3.4).
- $(d_k)$ : in $\mathcal{C}$ (Example (The Truncations and the Newton Sequence Are Equivalent)), not null: $d_k \ge 1$ for every $k$ , so the tolerance $\varepsilon = 1$ has no threshold.
- $((-1)^n)$ : neither. Consecutive terms differ by $2$ , so $\varepsilon = 1$ has no Cauchy threshold; and it is not null, since every term has absolute value $1$ .
(b) By Logic and Proof, Proposition 6.2.3 and Logic and Proof, Proposition 6.2.2, reading $\neg(x < \varepsilon)$ as $x \ge \varepsilon$ : $\exists \varepsilon \in \mathbb{Q}_{>0} \ \ \forall N \in \mathbb{N} \ \ \exists n \in \mathbb{N} \ \ \bigl( n \ge N \wedge \left| a_n - b_n \right| \ge \varepsilon \bigr) .$ One rational tolerance is beaten at indices beyond every threshold.
(c) False. $(1/(n + 1))_n \sim (0)_n$ , and $1/(n + 1) \ne 0$ for every $n$ .

B. Practice

Exercise (B1: Equivalent or not)

(a) Show that $(1/(n + 1))_n \sim (1/(n + 2))_n$ and that both are equivalent to $(0)_n$ .
(b) Determine which constant sequences $(c)_n$ , $c \in \mathbb{Q}$ , are equivalent to $(3 + 1/(n + 1))_n$ . Justify your answer.

Solution.

(a) Both sequences are null: the first by Example (First Limits) (b); the second is the first shifted by one, $(a_{n+1})_n$ with $a_n = 1/(n + 1)$ , so it is null by Proposition 4.3.2 (b). Null sequences lie in $\mathcal{C}$ (Theorem 4.5.3 (a)), and a null sequence $a$ satisfies $a \sim (0)_n$ , since $a - (0)_n = a$ . By symmetry and transitivity (Proposition 5.1.1), $(1/(n + 1)) \sim (0)_n \sim (1/(n + 2))$ gives $(1/(n + 1)) \sim (1/(n + 2))$ .
(b) Only $c = 3$ . The difference $(3 + 1/(n + 1)) - (c)_n = (3 - c) + 1/(n + 1)$ converges to $3 - c$ , by the sum rule (Theorem 4.4.3 (a)) with the constant $3 - c$ and the null $(1/(n + 1))$ . By uniqueness of limits (Theorem 4.3.4) it is null if and only if $3 - c = 0$ . Hence $(3 + 1/(n + 1)) \sim (c)_n$ exactly when $c = 3$ ; this is consistent with the degenerate example after Definition 5.1.2, since two constants equivalent to one sequence are equivalent to each other, hence equal.

Exercise (B2: Null differences preserve Cauchy)

(a) Let $a \in \mathcal{C}$ , and let $b \colon \mathbb{N} \to \mathbb{Q}$ be a sequence such that $a - b$ is null. Prove that $b \in \mathcal{C}$ and $b \sim a$ .
(b) Hence show that $(2/x_n)_n \in \mathcal{C}$ and $(2/x_n)_n \sim (x_n)_n$ , where $(x_n)$ is the Newton sequence.

Solution.

(a) For every $n$ , $b_n = a_n - (a_n - b_n)$ , so $b = a - (a - b)$ . Here $a \in \mathcal{C}$ , and $a - b$ is null, hence in $\mathcal{C}$ (Theorem 4.5.3 (a)); the difference of two members of $\mathcal{C}$ is in $\mathcal{C}$ (Theorem 4.5.3 (b)). So $b \in \mathcal{C}$ . Then $a \sim b$ by definition, and $b \sim a$ by symmetry.
(b) By (NS1), $x_n > 0$ , so $2/x_n$ is defined. For every $n$ , $x_n - \frac{2}{x_n} = \frac{x_n^2 - 2}{x_n} = \frac{e_n}{x_n} .$ By (NS1) and (NS2), $e_n > 0$ and $x_n > 1$ , so $0 < 1/x_n < 1$ (Proposition 2.5.2) and $0 < e_n/x_n < e_n$ (Proposition 2.3.5 (c)). For $n \ge 1$ , $e_n \le 1/(4n) \le 1/(n + 1)$ . So $0 \le x_n - 2/x_n \le 1/(n + 1)$ for every $n \ge 1$ , and the squeeze Proposition 4.4.4 (c), with $N_0 = 1$ and the null sequence $(1/(n + 1))$ (Example (First Limits) (b)), shows that $(x_n - 2/x_n)$ is null. Part (a), with $a = (x_n) \in \mathcal{C}$ (NS3) and $b = (2/x_n)$ , gives the claim. The terms $2/x_n$ satisfy $(2/x_n)^2 = 4/x_n^2 < 2$ , so this sequence approaches the hole from below, as the truncations do.

Exercise (B3: Every other Newton term)

Show that $(x_{2n})_n \sim (x_n)_n$ for the Newton sequence. Hint: imitate Example (Finite Changes and Shifts) (b).

Solution. First, $(x_{2n})_n \in \mathcal{C}$ . Let $\varepsilon \in \mathbb{Q}_{>0}$ , and let $N$ be a threshold for $(x_n)$ with tolerance $\varepsilon$ (NS3). For $m, n \ge N$ , also $2m \ge m \ge N$ and $2n \ge N$ , so $\left| x_{2m} - x_{2n} \right| < \varepsilon$ .

Second, the difference is null. For $n \ge N$ , the two indices $2n$ and $n$ are both $\ge N$ , so $\left| x_{2n} - x_n \right| < \varepsilon$ . So $(x_{2n} - x_n)_n$ is null, with the same thresholds as $(x_n)$ , and $(x_{2n}) \sim (x_n)$ .

The Cauchy condition was used with two indices that are far apart ( $2n$ and $n$ ). This is exactly where “every pair of indices beyond $N$ ” is needed, and not only neighbors.

C. Going deeper

Exercise (C1: Subsequences)

Let $a \in \mathcal{C}$ , and let $k \mapsto n_k$ be a function $\mathbb{N} \to \mathbb{N}$ with $n_k < n_{k+1}$ for every $k \in \mathbb{N}$ (for instance $n_k = 2k$ , or any sequence of indices defined by Sets, Relations, and Cardinality, Theorem 2.3.1 with this property).

(a) Prove that $n_k \ge k$ for every $k$ , that $(a_{n_k})_{k \in \mathbb{N}} \in \mathcal{C}$ , and that $(a_{n_k})_k \sim a$ .
(b) Deduce: if $a, b \in \mathcal{C}$ and $a_{n_k} = b_{n_k}$ for every $k$ , then $a \sim b$ . Compare with the warning after Example (Finite Changes and Shifts): why does this not say that sequences which are “close at the start” are equivalent?

Solution (Hint 1). For (a), the indices $n_k$ run ahead of $k$ . Once you know $n_k \ge k$ , the Cauchy condition applies to the pair $(n_k, k)$ .

Solution (Hint 2). For (a), prove $n_k \ge k$ by Logic and Proof, Axiom 4.2.1 on $k$ ; the step uses $n_{k+1} > n_k \ge k$ .

Solution.

(a) $n_k \ge k$ . By Logic and Proof, Axiom 4.2.1 on $k$ , base $P(0)$ : $n_0 \ge 0$ (Theorem 1.6.1 (d)). Step: if $n_k \ge k$ , then $n_{k+1} > n_k \ge k$ , so $k < n_{k+1}$ ; by Theorem 1.6.1 (b), $n_{k+1} < k + 1$ would give $n_{k+1} \le k$ , so by trichotomy $n_{k+1} \ge k + 1$ .
In $\mathcal{C}$ . Let $\varepsilon \in \mathbb{Q}_{>0}$ , and let $N$ be a threshold for $a$ with tolerance $\varepsilon$ . For $j, k \ge N$ , $n_j \ge j \ge N$ and $n_k \ge k \ge N$ , so $\left| a_{n_j} - a_{n_k} \right| < \varepsilon$ .

Equivalent to $a$ . For $k \ge N$ , both $n_k \ge N$ and $k \ge N$ , so $\left| a_{n_k} - a_k \right| < \varepsilon$ . So $(a_{n_k} - a_k)_k$ is null, with the same thresholds, and $(a_{n_k})_k \sim a$ .
(b) By (a), $(a_{n_k})_k \sim a$ and $(b_{n_k})_k \sim b$ . The two subsequences are the same sequence, since $a_{n_k} = b_{n_k}$ for every $k$ . So $a \sim (a_{n_k})_k = (b_{n_k})_k \sim b$ , using symmetry for the first step, and transitivity (Proposition 5.1.1) gives $a \sim b$ .

The hypothesis of (b) is that the sequences agree at infinitely many indices, $n_0 < n_1 < \cdots$ , arbitrarily far out. In the warning, $(0)_n$ and $(1 - 1/(n + 1))_n$ agree only at $n = 0$ . Agreement far out, along a whole subsequence, forces equivalence for Cauchy sequences; agreement at finitely many places says nothing. (For sequences that are not Cauchy, (b) fails: $(1, 0, 1, 0, \dots)$ and $(1)_n$ agree at every even index, and their difference is not null.)

Marking scheme. (10 points)

2: proves $n_k \ge k$ for every $k$ , justifying the passage from $n_{k+1} > n_k \ge k$ (or, by a least counterexample, from $n_k > n_{k-1} \ge k - 1$ ) to the next whole number.
3: shows $(a_{n_k}) \in \mathcal{C}$ , with one threshold that serves all $j, k \ge N$ and with $n_j, n_k \ge N$ justified from $n_k \ge k$ .
3: shows $(a_{n_k} - a_k)_k$ is null by applying the Cauchy condition to the pair $(n_k, k)$ .
2: deduces (b) by symmetry and transitivity of $\sim$ .

Fatal errors (0 for the step): using a limit of $a$ in $\mathbb{Q}$ ; a threshold that depends on $k$ .