Completeness

Proof:

(\(\Rightarrow\)) Suppose \(X\) is complete in the universal sense, and let \(\{x_n\}\) be a Cauchy sequence in \(X\). We argue by contradiction. Assume that \(\{x_n\}\) does not converge to any point of \(X\). We manufacture a superspace in which \(X\) fails to be closed, contradicting completeness.

Adjoin a single new point \(\omega \notin X\) and set \(Y = X \cup \{\omega\}\). Define \(e : Y \times Y \to [0, \infty)\) by \[ e(a, b) = d(a, b) \ \ (a, b \in X), \quad e(a, \omega) = e(\omega, a) = \lim_{m \to \infty} d(a, x_m) \ \ (a \in X), \quad e(\omega, \omega) = 0. \] The limit defining \(e(a, \omega)\) exists. The reverse triangle inequality \(|d(a, x_m) - d(a, x_k)| \le d(x_m, x_k)\) shows that \(\{d(a, x_m)\}_m\) is a Cauchy sequence of reals, which converges by completeness of \(\mathbb{R}\).

We verify that \(e\) is a metric on \(Y\). Non-negativity and symmetry are immediate. For the identity of indiscernibles, the only non-trivial case is \(e(a, \omega) = 0\) with \(a \in X\). This would give \(d(a, x_m) \to 0\), that is, \(x_m \to a\) in \(X\), contradicting our assumption that \(\{x_n\}\) has no limit in \(X\). Hence \(e(p, q) = 0\) if and only if \(p = q\).

For the triangle inequality, the cases involving \(\omega\) follow by passing to the limit in the corresponding inequality for \(d\). For \(a, b \in X\), taking \(m \to \infty\) in \(d(a, x_m) \le d(a, b) + d(b, x_m)\) yields \(e(a, \omega) \le e(a, b) + e(b, \omega)\). Taking the limit in \(d(a, b) \le d(a, x_m) + d(x_m, b)\) yields \(e(a, b) \le e(a, \omega) + e(\omega, b)\). Since \(e\) restricts to \(d\) on \(X \times X\), the space \((Y, e)\) is a metric superspace of \((X, d)\).

In \((Y, e)\) we have \(x_n \to \omega\). By the \(\varepsilon\)-\(N\) form of the Cauchy condition, each \(\varepsilon \gt 0\) admits an \(N\) with \(d(x_n, x_m) \lt \varepsilon\) for all \(n, m \ge N\). Fixing \(n \ge N\) and letting \(m \to \infty\) gives \(e(x_n, \omega) = \lim_m d(x_n, x_m) \le \varepsilon\). Consequently \(\operatorname{dist}(\omega, X) = \inf_{a \in X} e(\omega, a) = 0\). At the same time \(X^c = Y \setminus X = \{\omega\}\), so \(\operatorname{dist}(\omega, X^c) = e(\omega, \omega) = 0\).

By definition \(\omega\) is thus a boundary point of \(X\) in \(Y\). Since \(\omega \notin X\), the boundary \(\partial X\) is not contained in \(X\), so \(X\) is not closed in \(Y\). This contradicts the completeness of \(X\). Hence \(\{x_n\}\) converges in \(X\).

(\(\Leftarrow\)) Suppose every Cauchy sequence in \(X\) converges in \(X\), and let \((Y, e)\) be any metric superspace of \(X\). To show \(X\) is closed in \(Y\), take any \(z \in \overline{X}^{\,Y}\). If \(z \in X\) there is nothing to prove, so assume \(z \in Y \setminus X\). Then \(z\) is a boundary point, and every ball about \(z\) meets \(X\). Choose \(x_n \in X\) with \(e(x_n, z) \lt 1/n\), so that \(x_n \to z\) in \(Y\).

A convergent sequence is Cauchy in \(Y\). By the \(\varepsilon\)-\(N\) form of the Cauchy condition, each \(\varepsilon \gt 0\) admits an \(N\) with \(e(x_n, x_m) \lt \varepsilon\) for all \(n, m \ge N\). Since \(e\) agrees with \(d\) on \(X\), the same \(N\) works for \(d\), so the sequence \(\{x_n\}\) is Cauchy in \((X, d)\) as well. By hypothesis it converges to some \(x \in X\). Then \(x_n \to x\) in \(Y\) too, and by uniqueness of limits in \(Y\) we conclude \(z = x \in X\). Hence \(\overline{X}^{\,Y} \subseteq X\), so \(\partial X \subseteq X\) and \(X\) is closed in \(Y\). As \(Y\) was arbitrary, \(X\) is complete.

Proof:

Let \(\mathcal{C}\) be the set of all Cauchy sequences in \(X\). For \(\{x_n\}, \{y_n\} \in \mathcal{C}\), two applications of the triangle inequality give \[ |d(x_n, y_n) - d(x_m, y_m)| \leq d(x_n, x_m) + d(y_n, y_m). \] Given \(\varepsilon \gt 0\), the \(\varepsilon\)-\(N\) form of the Cauchy property, applied to \(\{x_n\}\) and to \(\{y_n\}\) with \(\varepsilon/2\), yields a common index beyond which the right-hand side is less than \(\varepsilon\). Hence \(\{d(x_n, y_n)\}\) is Cauchy in \(\mathbb{R}\) and therefore converges, \(\mathbb{R}\) being complete. We may thus define \[ \delta(\{x_n\}, \{y_n\}) = \lim_{n \to \infty} d(x_n, y_n). \]

Letting \(n \to \infty\) in the metric axioms for \(d\), we see that \(\delta\) is non-negative and symmetric, that \(\delta(\{x_n\}, \{x_n\}) = 0\), and that \(\delta\) satisfies the triangle inequality. However, \(\delta\) can vanish on distinct sequences, for instance on two sequences that differ in only finitely many terms. We therefore write \(\{x_n\} \sim \{y_n\}\) when \(\delta(\{x_n\}, \{y_n\}) = 0\). This relation is reflexive and symmetric, and the triangle inequality for \(\delta\) makes it transitive, so it is an equivalence relation. Denote by \(\widehat{X}\) the set of equivalence classes, write \([x_n]\) for the class of \(\{x_n\}\), and define \[ \widehat{d}([x_n], [y_n]) = \delta(\{x_n\}, \{y_n\}). \]

The value does not depend on the representatives. If \(\{x_n\} \sim \{x'_n\}\) and \(\{y_n\} \sim \{y'_n\}\), then, exactly as for \(d\) above, \[ |\delta(\{x_n\}, \{y_n\}) - \delta(\{x'_n\}, \{y'_n\})| \leq \delta(\{x_n\}, \{x'_n\}) + \delta(\{y_n\}, \{y'_n\}), \] and both terms on the right vanish. The function \(\widehat{d}\) inherits non-negativity, symmetry, and the triangle inequality from \(\delta\), and \(\widehat{d}([x_n], [y_n]) = 0\) holds exactly when \(\{x_n\} \sim \{y_n\}\), that is, when the two classes coincide. Hence \((\widehat{X}, \widehat{d})\) is a metric space.

For \(a \in X\), the constant sequence \((a, a, a, \ldots)\) is Cauchy. Let \(\iota(a)\) be its class. Then \(\widehat{d}(\iota(a), \iota(b)) = d(a, b)\), so \(\iota : X \to \widehat{X}\) is an isometry. More generally, for \(a \in X\) and \([x_n] \in \widehat{X}\), \[ \widehat{d}(\iota(a), [x_n]) = \lim_{m \to \infty} d(a, x_m). \]

The subspace \(\iota(X)\) is dense. Fix \(\xi = [x_n] \in \widehat{X}\) and \(\varepsilon \gt 0\), and choose \(N\) with \(d(x_n, x_m) \lt \varepsilon\) for all \(n, m \geq N\). For each \(n \geq N\), the formula above with \(a = x_n\) gives \(\widehat{d}(\iota(x_n), \xi) = \lim_{m} d(x_n, x_m) \leq \varepsilon\). Hence \(\widehat{d}(\iota(x_n), \xi) \to 0\), so \(\iota(x_n) \to \xi\) by the ball form of convergence. Every point of \(\widehat{X}\) is therefore the limit of a sequence drawn from \(\iota(X)\), which is one of the equivalent forms of density.

It remains to show that \(\widehat{X}\) is complete. By the Cauchy Criterion, it suffices to show that each Cauchy sequence \(\{\xi_j\}\) in \(\widehat{X}\) has a limit in \(\widehat{X}\). Density lets us choose \(a_j \in X\) with \(\widehat{d}(\iota(a_j), \xi_j) \lt 1/j\). Since \(\iota\) is an isometry, the triangle inequality in \(\widehat{X}\) gives \[ \begin{align*} d(a_i, a_j) &= \widehat{d}(\iota(a_i), \iota(a_j)) \\\\ &\leq \widehat{d}(\iota(a_i), \xi_i) + \widehat{d}(\xi_i, \xi_j) + \widehat{d}(\xi_j, \iota(a_j)) \\\\ &\lt \frac{1}{i} + \widehat{d}(\xi_i, \xi_j) + \frac{1}{j}. \end{align*} \] Because \(\{\xi_j\}\) is Cauchy and \(1/j \to 0\), the right-hand side falls below any given \(\varepsilon \gt 0\) once \(i\) and \(j\) are both large enough. Thus \(\{a_j\}\) is Cauchy in \(X\), and its class \(\xi = [a_i]\) is a point of \(\widehat{X}\).

We claim that \(\xi_j \to \xi\). The triangle inequality and the formula for \(\widehat{d}(\iota(a), \cdot)\) with \(a = a_j\) give \[ \begin{align*} \widehat{d}(\xi_j, \xi) &\leq \widehat{d}(\xi_j, \iota(a_j)) + \widehat{d}(\iota(a_j), \xi) \\\\ &\lt \frac{1}{j} + \lim_{i \to \infty} d(a_j, a_i). \end{align*} \] Given \(\varepsilon \gt 0\), there is \(J\) such that \(d(a_j, a_i) \lt \varepsilon\) whenever \(i, j \geq J\). For every \(j \geq J\) the limit on the right is then at most \(\varepsilon\), so \(\widehat{d}(\xi_j, \xi) \lt 1/j + \varepsilon\), which is less than \(2\varepsilon\) once also \(j \gt 1/\varepsilon\). Hence \(\widehat{d}(\xi_j, \xi) \to 0\), that is, \(\xi_j \to \xi\), and \(\widehat{X}\) is complete.

We have shown that \((\widehat{X}, \widehat{d})\) is complete and that \(\iota\) maps \(X\) isometrically onto the dense subspace \(\iota(X)\). Therefore \((\widehat{X}, \widehat{d})\) is a completion of \((X, d)\).

Proof Sketch:

The map \(f := \phi \circ \psi^{-1}\) is an isometry from the dense subspace \(\psi(X)\) of \(X'\) onto the dense subspace \(\phi(X)\) of \(X''\).

Since \(X''\) is complete, \(f\) has a unique continuous extension \(\tilde f\) to \(X'\) (by the extension principle above), and this extension is isometric because the isometry equation passes through limits.

Because \(\tilde f\) is an isometry and \(X'\) is complete, the range \(\tilde f(X')\) inherits completeness (Cauchy sequences transfer across isometries), and by the complete subset theorem applied in \(X''\), \(\tilde f(X')\) is closed in \(X''\). Since \(\tilde f(X') \supseteq \phi(X)\), it contains the closure \(\overline{\phi(X)} = X''\). Thus, \(\tilde f\) is an isometry from \(X'\) onto \(X''\).

Example: \(\mathbb{Q}\) Completes to \(\mathbb{R}\)

The completion of the rational numbers \((\mathbb{Q}, |\cdot|)\) is the real numbers \((\mathbb{R}, |\cdot|)\). While we typically construct \(\mathbb{R}\) as equivalence classes of Cauchy sequences, there are other historically significant methods, such as Dedekind cuts. The Cauchy-sequence route cannot reuse the existence proof above verbatim, since that proof takes limits of real distances. Building \(\mathbb{R}\) this way runs the same idea with rational tolerances only, and it must also construct the order and the field operations on the classes.

• Cauchy Sequences:
  Constructing \(\mathbb{R}\) via the limits of sequences that "should" converge (for example, \((1, 1.4, 1.41, \dots) \to \sqrt{2}\)).
• Dedekind Cuts:
  Constructing \(\mathbb{R}\) by partitioning \(\mathbb{Q}\) into two sets (those less than \(\sqrt{2}\) and those greater).

The Uniqueness Theorem provides the bridge for the metric structure. Once each construction is known to be a completion of \(\mathbb{Q}\), it shows that the two "implementations" are isometric, by a map that carries the rationals of one onto the rationals of the other. Matching the order and the field operations as well takes a separate result, that any two ordered fields with the least-upper-bound property are isomorphic as ordered fields, which we state without proof. Together, these let us speak of "The Real Numbers" rather than "the real numbers according to Cauchy" or "the real numbers according to Dedekind," and treat \(\mathbb{R}\) as a single, canonical abstract data type.

Proof: Equivalence of the Two Criteria

The sketch above settles the nested-sequence form, so it is enough to show that the two criteria impose the same condition on \(X\).

(Nest \(\Rightarrow\) sequence.) A sequence \(\{F_n\}\) of non-empty closed sets with \(F_{n+1} \subseteq F_n\) is a nest, and \(\operatorname{diam}(F_n) \to 0\) gives \(\inf \{\operatorname{diam}(F_n) \mid n \in \mathbb{N}\} = 0\). The nest criterion therefore applies and returns a singleton intersection, which is what the sequence criterion asks for.

(Sequence \(\Rightarrow\) nest.) Let \(\mathcal{F}\) be a nest of non-empty closed subsets of \(X\) with \(\inf \{\operatorname{diam}(A) \mid A \in \mathcal{F}\} = 0\). For each \(n \in \mathbb{N}\) choose \(A_n \in \mathcal{F}\) with \(\operatorname{diam}(A_n) \lt 1/n\), and let \(B_n\) be the smallest of \(A_1, \dots, A_n\). This least element exists because any two members of a nest are comparable, so every finite subfamily is a chain under inclusion. Since \(B_n\) is one of \(A_1, \dots, A_n\), it lies in \(\mathcal{F}\) and is therefore non-empty and closed, and \(B_{n+1} \subseteq B_n\). From \(B_n \subseteq A_n\) and the fact that the diameter is a supremum over a smaller set, we obtain \(\operatorname{diam}(B_n) \lt 1/n\). The nested-sequence criterion therefore gives \(\bigcap B_n = \{z\}\) for some \(z \in X\).

Now fix \(C \in \mathcal{F}\). Since \(\mathcal{F}\) is a nest, for each \(n\) either \(B_n \subseteq C\) or \(C \subseteq B_n\). If the first alternative holds for some \(n\), then \(z \in B_n \subseteq C\). Otherwise \(C \subseteq B_n\) for every \(n\), so \(C \subseteq \bigcap B_n = \{z\}\), and \(C\) is non-empty, forcing \(C = \{z\}\). Either way \(z \in C\), so \(z \in \bigcap \mathcal{F}\). Conversely every \(B_n\) lies in \(\mathcal{F}\), so \(\bigcap \mathcal{F} \subseteq \bigcap B_n = \{z\}\). Hence \(\bigcap \mathcal{F} = \{z\}\).

Proof:

(\(\Rightarrow\)) \(S\) complete \(\Rightarrow\) \(S\) closed. Suppose, for contradiction, that \(S\) is not closed in \(X\). Then there exists \(x \in \partial S\) with \(x \notin S\). By the definition of a boundary point, \(\operatorname{dist}(x, S) = 0\), so for each \(n \in \mathbb{N}\) we can pick \(s_n \in S\) with \(d(s_n, x) \lt 1/n\). Then \(s_n \to x\) in \(X\) (ball form of convergence), hence \(\{s_n\}\) is Cauchy in \(X\).

To transfer this to \(S\), take \(r \gt 0\). Some ball \(\mathcal{B}^X[c; r/2)\) of \(X\) includes a tail \(\{s_n : n \geq N\}\). Re-centering at \(s_N \in S\) and applying the triangle inequality, we obtain \(d(s_n, s_N) \leq d(s_n, c) + d(c, s_N) \lt r/2 + r/2 = r\) for all \(n \geq N\), so the tail lies in \(\mathcal{B}^S[s_N; r)\). Thus \(\{s_n\}\) is also Cauchy in \(S\).

By completeness of \(S\), \(s_n \to s\) for some \(s \in S\). Since every ball of \(S\) is included in the corresponding ball of \(X\), convergence in \(S\) implies convergence in \(X\) to the same point, so \(s_n \to s\) in \(X\) as well. Uniqueness of limits in \(X\) then forces \(s = x\), so \(x \in S\), contradicting \(x \notin S\). Hence \(S\) is closed.

(\(\Leftarrow\)) \(S\) closed \(\Rightarrow\) \(S\) complete. Let \(\{s_n\}\) be Cauchy in \(S\). Since any ball of \(S\) is included in the corresponding ball of \(X\), \(\{s_n\}\) is also Cauchy in \(X\). By completeness of \(X\) and the Cauchy Criterion, \(s_n \to x\) for some \(x \in X\).

We claim \(x \in S\). Any open ball \(\mathcal{B}^X[x; r)\) includes a tail of \(\{s_n\} \subseteq S\), so \(\mathcal{B}^X[x; r) \cap S \neq \emptyset\) for every \(r \gt 0\). Hence \(\operatorname{dist}(x, S) = 0\). If \(x \notin S\), then \(x \in S^c\) gives \(\operatorname{dist}(x, S^c) = 0\) as well, so \(x \in \partial S\). But \(S\) is closed, forcing \(x \in S\), a contradiction. Thus \(x \in S\), and by the subspace convergence theorem, \(\{s_n\}\) converges to \(x\) in \(S\). Hence \(S\) is complete.

Proof:

(1) By iterating the contraction inequality, \[ d(f^n(a), f^n(b)) \leq k \cdot d(f^{n-1}(a), f^{n-1}(b)) \leq \cdots \leq k^n \cdot d(a, b). \] Since \(k \in [0, 1)\), we have \(k^n \to 0\), so \(d(f^n(a), f^n(b)) \to 0\).

(2) Fix \(x \in X\) and set \(c := d(x, f(x))\). By (1) applied with \(a = x, b = f(x)\), we obtain \(d(f^n(x), f^{n+1}(x)) \leq k^n c\). For \(m \gt n\), the triangle inequality and the geometric series yield \[ d(f^n(x), f^m(x)) \leq \sum_{i=n}^{m-1} d(f^i(x), f^{i+1}(x)) \leq \sum_{i=n}^{m-1} k^i c \leq \frac{k^n}{1 - k} \cdot c. \] Since \(k^n \to 0\), the right-hand side can be made arbitrarily small by choosing \(n\) large, which establishes the Cauchy property.

Proof: Suppose that \(w \in X\). By the preceding theorem, \(\{f^n(w)\}\) is Cauchy in \(X\), and since \(X\) is complete, this sequence converges in \(X\).
Let \(z = \lim f^n(w)\). Since \(f\) is a contraction, it is uniformly continuous (Lipschitz with constant \(k\)), hence continuous, so \(f(x_n) \to f(z)\) whenever \(x_n \to z\). In particular, \[ f(z) = \lim_{n \to \infty} f(f^n(w)) = \lim_{n \to \infty} f^{n+1}(w). \] Since \(\{f^{n+1}(w)\}\) is a subsequence of \(\{f^n(w)\}\), it has the same limit: \[ \lim_{n \to \infty} f^{n+1}(w) = \lim_{n \to \infty} f^n(w) = z, \] so that \(f(z) = z\) as required.
The map \(f\) has no other fixed point. If \(a \in X\) were also fixed, then \[ d(a, z) = d(f(a), f(z)) \leq k \, d(a, z), \] which forces \(d(a, z) = 0\) and thus \(a = z\) because \(k \lt 1\).

Proof:

For \(m \gt n\), iterating the contraction inequality gives \(d(f^i(w), f^{i+1}(w)) \leq k^i \, d(w, f(w))\), so the triangle inequality and the geometric series give: \[ d(f^n(w), f^m(w)) \leq \sum_{i=n}^{m-1} d(f^i(w), f^{i+1}(w)) \leq \sum_{i=n}^{m-1} k^i \cdot d(w, f(w)) \leq \frac{k^n}{1-k} \cdot d(w, f(w)). \] Taking \(m \to \infty\) yields the result.