Monotone Sequences, Bolzano-Weierstrass, and Cauchy Completeness: Examples and Counterexamples

Let $(x_k)_{k \ge 1}$ be given by

$x_1 = 2, \qquad x_{k+1} = \frac{1}{2}\Big(x_k + \frac{2}{x_k}\Big) \qquad (k \ge 1).$

Then $(x_k)$ is strictly decreasing, every term satisfies $x_k > \sqrt 2$, and

$\lim_{k} x_k = \sqrt 2 .$

This is the Babylonian, or Heron, iteration for the square root, and it is the standard illustration of A nondecreasing sequence bounded above converges to the supremum of its range, and a nonincreasing sequence bounded below to the infimum: monotone plus bounded delivers a limit, and the recursion then identifies the limit, because the limit must be a fixed point of the map that produced the sequence.

Indexing. Sequences in this library are functions on $\mathbb{N}$, which starts at $0$ (Sequences of reals: bounded, eventually, frequently, tails, subsequences). The family above, indexed from $1$, is realised as $x_k := g_{k-1}$ for the sequence $(g_j)_{j \in \mathbb{N}}$ with $g_0 = 2$ and $g_{j+1} = (g_j + 2/g_j)/2$, and the verification below works with $(g_j)$. The shift changes nothing: convergence and monotonicity read the same under it (Convergence depends only on the tail).

• The identification of the limit is the interesting half. Monotone convergence produces $L$ but says only that it is the infimum of the range, which is not a usable description. Passing to the limit in the recursion turns the description into an equation, $L = (L + 2/L)/2$, and that equation has exactly one nonnegative solution. The step that makes this legitimate is Convergence depends only on the tail: the shifted sequence $(g_{j+1})$ has the same limit as $(g_j)$, so the two sides of the recursion may be compared in the limit.

• The hypothesis $L \ne 0$ is not free. The quotient case of Algebra of limits: sums, scalar multiples, products and quotients requires it, and it is supplied by step 4.1, not assumed. Had the sequence been allowed to approach $0$ the argument would break exactly there, and this is the usual place where a proof of this example is incomplete.

• Convergence is very fast, though nothing above uses that. The identity in step 1.2 also gives $g_{j+1} - \sqrt 2 = (g_j - \sqrt 2)^2/(2 g_j)$, so the error is squared at each step: the iteration is Newton's method applied to $u^2 - 2$. The contractive estimate of Every contractive sequence is Cauchy, hence converges, with error bound $|x - x_k| \le c^{k-1}|x_2 - x_1|/(1-c)$ for $k \ge 1$ would give only geometric decay, so it is a weaker tool here, and the monotone route is both shorter and sharper.

• Nothing in the argument is special to $2$. The same proof with $2$ replaced by any $a > 0$, starting from any $x_1 > 0$ with $x_1^2 > a$, converges to $\sqrt a$. The starting value $2$ is chosen because $2^2 = 4 > 2$ makes the base case of step 1.2 immediate.

Let $(x_k)_{k \ge 1}$ be given by

$x_1 = 1, \qquad x_{k+1} = \sqrt{2 + x_k} \qquad (k \ge 1).$

Then $(x_k)$ is strictly increasing, every term satisfies $0 \le x_k < 2$, and

$\lim_{k} x_k = 2 .$

Informally this is the value of the nested radical $\sqrt{2 + \sqrt{2 + \sqrt{2 + \cdots}}}$, and the point of the example is that the expression means nothing until the sequence is shown to converge; only then does passing to the limit in the recursion identify the value.

Indexing. As in The Babylonian sequence $x_1 = 2$, $x_{k+1} = (x_k + 2/x_k)/2$ decreases to $\sqrt{2}$, the family indexed from $1$ is realised as $x_k := g_{k-1}$ for the sequence $(g_j)_{j \in \mathbb{N}}$ with $g_0 = 1$ and $g_{j+1} = \sqrt{2 + g_j}$, and the verification works with $(g_j)$ (Sequences of reals: bounded, eventually, frequently, tails, subsequences, Convergence depends only on the tail).

• The limit is not attained. Every term is strictly below $2$ and the limit is $2$, which is the supremum of the range and does not belong to it. That is the ordinary situation for a strictly increasing convergent sequence, and it is why A nondecreasing sequence bounded above converges to the supremum of its range, and a nonincreasing sequence bounded below to the infimum is stated with a supremum rather than a maximum.

• The quadratic has two roots and only one is admissible. The limit equation $L^2 = 2 + L$ is solved by $L = 2$ and by $L = -1$. The second is excluded by step 4.1, which is why the bound $L \ge 1$ is proved rather than waved through: without it the argument would identify the limit only up to a sign, and a reader who writes down the limit equation without checking the range of $L$ has proved strictly less than the example claims.

• Squaring the recursion avoids a continuity argument. Passing to the limit in $g_{j+1} = \sqrt{2 + g_j}$ directly would need continuity of the square root, which this library has not proved at this point. Squaring first turns the recursion into $(g_{j+1})^2 = 2 + g_j$, in which only the algebra of limits is required. The device is worth remembering: an identity between polynomials in the terms passes to the limit for free, whereas an identity involving a function does not.

For $k \ge 1$ let $I_k := [0, 1/k]$, a nonempty closed bounded interval (Intervals of $\mathbb{R}$: the nine order-convex forms, nondegeneracy, and length). The family is nested, its lengths tend to $0$, and

$\bigcap_{k \ge 1} \Big[0, \frac{1}{k}\Big] = \{0\}.$

This is the standard instance of the single-point case of A nested sequence of nonempty closed bounded intervals has nonempty intersection, and the intersection is a single point exactly when the lengths tend to $0$, and the intersection is computed twice over: once by the theorem, which says the intersection is a single point, and once by inspection, which says that point is $0$.

Indexing. Written on $\mathbb{N}$, the family is $J_j := [0, 1/(j+1)]$ for $j \in \mathbb{N}$, which is the same family under the substitution $k = j+1$ (Sequences of reals: bounded, eventually, frequently, tails, subsequences). The verification uses $(J_j)$.

• The two computations are independent and both are needed. That the intersection is a single point comes from A nested sequence of nonempty closed bounded intervals has nonempty intersection, and the intersection is a single point exactly when the lengths tend to $0$ and uses that the lengths are null; that the point is $0$ comes from inspection. Without the theorem one would still have to rule out the intersection being larger than $\{0\}$, which is exactly the content of the length condition.

• The Archimedean property is the whole of step 2.2. In a non-Archimedean ordered field the same family has lengths that do not tend to $0$, and the intersection contains every positive infinitesimal, so it is not a single point. What makes the example come out as stated is For every $\varepsilon > 0$ in a complete ordered field there is a natural $n \ge 1$ with $1/n < \varepsilon$.

• Compare the open version. Removing the left endpoint gives $(0, 1/k)$, whose intersection is empty (The nested open intervals $(0, 1/k)$ have empty intersection). The two computations differ in exactly one respect, whether the common point $0$ belongs to the sets, and that is the hypothesis of closedness in the theorem.

For $k \ge 1$ let

$x_k = (-1)^k\Big(1 + \frac{1}{k}\Big).$

Then $(x_k)$ is bounded, with $1 < |x_k| \le 2$ at every index, it does not converge, and its subsequential limit set (Subsequential limit of a real sequence, and the subsequential limit set) is exactly

$\operatorname{SL}(x) = \{-1, 1\}.$

The example separates two things that a first reading of Bolzano-Weierstrass can run together. A bounded sequence must have a subsequential limit; it may have several; and having several is exactly what stops it converging. Here there are two, and neither is a value of the sequence, since $|x_k| > 1$ always.

Indexing and the sign. Written on $\mathbb{N}$ the sequence is $u_j := t_j\big(1 + 1/(j+1)\big)$ for $j \in \mathbb{N}$, where $t_j := -s_j$ and $(s_k)$ is the alternating sequence of The even and odd index maps and the alternating sequence: strictly increasing $e, o$ with $\mathbb{N}$ their disjoint union, and the unique $(s_k)$ with $s_0 = 1$, $s_{\sigma(k)} = -s_k$, which satisfies $|s_k| = 1$, $s \circ e \equiv 1$ and $s \circ o \equiv -1$. Since $s_{\sigma(j)} = -s_j$, the sequence $(t_j)$ is $j \mapsto s_{j+1}$, so $u_j = x_{j+1}$ and $(u_j)$ is the family above under the substitution $k = j+1$. The verification uses $(u_j)$.

• Where Bolzano-Weierstrass sits. Bolzano-Weierstrass: every bounded real sequence has a convergent subsequence guarantees that a bounded sequence has at least one subsequential limit; this example computes the whole set and finds two. Nothing above uses the theorem, since the two subsequential limits are exhibited directly, and that is the honest order of business: an existence theorem is not needed once a witness is in hand.

• The perturbation is what makes the example more than the alternating sequence. With $p_j$ replaced by the constant $1$ the sequence is $\pm 1$ alternating and each subsequential limit is attained infinitely often. Here $|x_k| > 1$ at every index, so neither subsequential limit is ever a value of the sequence. Subsequential limits are limits, not values.

• The converse direction is where the partition earns its keep. Step 4.1 rules out every other candidate by taking absolute values, which collapses the sign and leaves the single null perturbation to handle. The alternative, splitting an arbitrary subsequence according to how many of its indices are even, needs the disjointness half of The even and odd index maps and the alternating sequence: strictly increasing $e, o$ with $\mathbb{N}$ their disjoint union, and the unique $(s_k)$ with $s_0 = 1$, $s_{\sigma(k)} = -s_k$, which satisfies $|s_k| = 1$, $s \circ e \equiv 1$ and $s \circ o \equiv -1$ and is longer.

• This is the standard example of a bounded divergent sequence with a computable $\limsup$ and $\liminf$, namely $1$ and $-1$. Those notions are developed on the next page of the track, and this item is written so that it can be cited there without change.

Fix any $a \in \mathbb{R}$ and let $(x_k)$ be the sequence with $x_0 = a$ and

$x_{k+1} = \frac{x_k + 1}{3} \qquad (k \in \mathbb{N}).$

Then $(x_k)$ is contractive with contraction constant $c = 1/3$ (Contractive sequence: $|x_{k+2} - x_{k+1}| \le c\,|x_{k+1} - x_k|$ for a fixed $0 < c < 1$), and

$\lim_{k} x_k = \frac{1}{2},$

whatever the starting value $a$ is. Moreover Every contractive sequence is Cauchy, hence converges, with error bound $|x - x_k| \le c^{k-1}|x_2 - x_1|/(1-c)$ for $k \ge 1$ supplies the error bound $|1/2 - x_k| \le 3^{\,-(k-1)}|x_2 - x_1|/(1 - 1/3)$ for $k \ge 1$, which is computable from the first three terms alone.

The limit $1/2$ is the unique solution of $L = (L+1)/3$, that is the unique fixed point of the map $u \mapsto (u+1)/3$. This is the smallest honest instance of the Banach fixed point theorem: a contraction on $\mathbb{R}$ has one fixed point, and every orbit converges to it.

• The starting value is genuinely arbitrary. Nothing in the verification uses anything about $a$, and the limit does not depend on it. What does depend on it is the error bound, through $|x_2 - x_1|$, which for this recursion equals $|a - 1/2| \cdot 2/9$.

• Contractivity is exact here, not an estimate. Step 1.2 gives equality, $|x_{k+2} - x_{k+1}| = \tfrac13|x_{k+1} - x_k|$, so for every starting value $a \ne 1/2$ the constant $c = 1/3$ is the smallest admissible one; for $a = 1/2$ the sequence is constant, every gap is $0$, and every $c \in (0,1)$ is admissible (Contractive sequence: $|x_{k+2} - x_{k+1}| \le c\,|x_{k+1} - x_k|$ for a fixed $0 < c < 1$). The error bound of Every contractive sequence is Cauchy, hence converges, with error bound $|x - x_k| \le c^{k-1}|x_2 - x_1|/(1-c)$ for $k \ge 1$ is as sharp as that theorem can make it. Contrast $x_{k+1} = x_k + 1/x_k$ from $x_1 = 1$ has strictly decreasing consecutive gaps and diverges, so no uniform $c < 1$ exists, where the ratio of consecutive gaps tends to $1$ and no admissible constant exists at all.

• Why a fixed point is forced. The limit satisfies the recursion equation because a sequence and its shift have the same limit (Convergence depends only on the tail) and the algebra of limits transports the right-hand side. This is the same move as in The Babylonian sequence $x_1 = 2$, $x_{k+1} = (x_k + 2/x_k)/2$ decreases to $\sqrt{2}$ and The sequence $x_1 = 1$, $x_{k+1} = \sqrt{2 + x_k}$ increases to $2$; the difference is that here convergence comes from contractivity rather than from monotonicity, and no monotonicity is available, since for $a > 1/2$ the sequence decreases and for $a < 1/2$ it increases while for $a = 1/2$ it is constant.

Refuted claim: every Cauchy sequence of rationals converges to a rational; equivalently, $\mathbb{Q}$ is complete (FALSE: the rationals are complete, The rationals as equivalence classes of pairs of integers).

The witness is the sequence of truncated decimal approximations of $\sqrt 2$, $s_0 = 1$, $s_1 = 1.4$, $s_2 = 1.41$, $s_3 = 1.414$, and so on: $s_n = k_n/10^n$ where $k_n$ is the largest natural number with $k_n^2 \le 2 \cdot 10^{2n}$. That this sequence is Cauchy in $\mathbb{Q}$ and has no rational limit is proved in full in FALSE: the rationals are complete and is not repeated here.