Complete Spaces and the Banach Fixed-Point Theorem

Chapter 1 defined completeness of $\mathbb{R}$ via the least upper bound property. This chapter gives the general metric-space notion of completeness — stated purely in terms of distance, with no order needed — and shows it is equivalent, in $\mathbb{R}$, to the axiom already assumed. The payoff is the Banach Fixed-Point Theorem, one of the most widely used existence-and-uniqueness results in analysis: it guarantees solutions to equations of the form $x=f(x)$ and, just as importantly, produces an explicit, computable iterative scheme for finding them.

Have to hand: metric spaces, convergence and the triangle inequality (Chapter 2), and Bolzano–Weierstrass (Chapter 3), which supplies the proof that $\mathbb{R}$ is complete in this new sense.

Why a new definition of completeness? The least-upper-bound formulation of Chapter 1 needs an order relation, which most metric spaces (spaces of functions, of sequences, of matrices) do not have. Cauchy completeness, defined below purely from the metric, is the version that generalises.

1. Cauchy Sequences

Definition. A sequence $(x_n)$ in a metric space $(X,d)$ is Cauchy if for every $\varepsilon>0$ there exists $N\in\mathbb{N}$ such that $d(x_m,x_n)<\varepsilon$ for all $m,n\ge N$.

Informally: the terms eventually get arbitrarily close to each other, not merely to some fixed external limit.

Theorem. Every convergent sequence is Cauchy.

Proof. Suppose $x_n\to x$. Given $\varepsilon>0$, choose $N$ with $d(x_n,x)<\varepsilon/2$ for $n\ge N$. Then for $m,n\ge N$, the triangle inequality gives $d(x_m,x_n)\le d(x_m,x)+d(x,x_n) < \varepsilon/2+\varepsilon/2=\varepsilon$. $\blacksquare$

Key distinction. The converse — every Cauchy sequence converges — is not true in every metric space. It is precisely this converse that defines completeness, and its failure is what makes $\mathbb{Q}$ incomplete in the Cauchy sense, matching its incompleteness in the least-upper-bound sense from Chapter 1.

2. Complete Metric Spaces

Definition. $(X,d)$ is complete if every Cauchy sequence in $X$ converges to a point of $X$.

Theorem. $\mathbb{R}$ (with $d(x,y)=|x-y|$) is complete.

Proof. Let $(x_n)$ be Cauchy in $\mathbb{R}$. First, $(x_n)$ is bounded: taking $\varepsilon=1$ in the Cauchy condition gives $N$ with $|x_n-x_N|<1$ for $n\ge N$, so $|x_n|\le|x_N|+1$ for $n\ge N$, and the finitely many earlier terms are individually bounded, so the whole sequence is bounded by $\max(|x_1|,\ldots,|x_{N-1}|,|x_N|+1)$. By Bolzano–Weierstrass (Chapter 3), some subsequence $x_{n_k}\to L$. We claim the whole sequence converges to $L$: given $\varepsilon>0$, the Cauchy condition gives $N$ with $d(x_m,x_n)<\varepsilon/2$ for $m,n\ge N$; convergence of the subsequence gives $k$ with $n_k\ge N$ and $d(x_{n_k},L)<\varepsilon/2$. Then for any $n\ge N$, $d(x_n,L)\le d(x_n,x_{n_k})+d(x_{n_k},L) < \varepsilon/2+\varepsilon/2=\varepsilon$. So $x_n\to L$. $\blacksquare$

This proof pattern — Cauchy $\Rightarrow$ bounded $\Rightarrow$ (by Bolzano–Weierstrass) a convergent subsequence $\Rightarrow$ the whole sequence converges to the same limit — is the standard route to completeness in $\mathbb{R}^n$ as well.

Worked example — $\mathbb{Q}$ is not complete. Let $x_1=1,\ x_{n+1} = \dfrac{x_n}{2}+\dfrac{1}{x_n}$ (Newton's method applied to $x^2=2$). One can show $(x_n)$ is Cauchy in $\mathbb{Q}$ (each $x_n\in\mathbb{Q}$, and the sequence converges in $\mathbb{R}$, hence satisfies the Cauchy criterion), yet its limit is $\sqrt2\notin\mathbb{Q}$. So $(x_n)$ is a Cauchy sequence in $\mathbb{Q}$ with no limit in $\mathbb{Q}$: $\mathbb{Q}$ is not complete.

3. Completeness Is Not Intrinsic the Way Compactness Is

Unlike compactness (Chapter 3), completeness genuinely depends on the ambient metric, not just the set of points: $(0,1)$ with the metric $d(x,y)=|x-y|$ is not complete (the Cauchy sequence $1/n$ has no limit inside $(0,1)$), yet $(0,1)$ is homeomorphic to $\mathbb{R}$ (itself complete) via a suitable bijection — completeness is not preserved by all "shape-preserving" maps; it is preserved by isometries (distance-preserving bijections), more generally by uniformly continuous bijections with uniformly continuous inverse, and by passing to closed subsets.

Theorem. A closed subset of a complete metric space is complete.

Proof. Let $F\subseteq X$ be closed, $X$ complete, and $(x_n)$ Cauchy in $F$. Since $(x_n)$ is also Cauchy in $X$, completeness of $X$ gives $x_n\to x$ for some $x\in X$. Since $F$ is closed and $(x_n)$ is a sequence in $F$ converging to $x$, the sequential characterisation of closed sets (Chapter 2) gives $x\in F$. $\blacksquare$

4. Contractions

Definition. A map $f:X\to X$ on a metric space is a contraction (or contraction mapping) if there exists a constant $k$ with $0\le k<1$ such that $d(f(x),f(y)) \le k\,d(x,y) \quad \text{for all } x,y\in X.$

A contraction is automatically continuous (small changes in input produce even smaller changes in output), but the key feature is the strict shrinkage by a fixed factor $k<1$, uniform over the whole space.

Worked example. $f(x)=\cos(x)/2$ on $\mathbb{R}$ (usual metric) is a contraction: by the Mean Value Theorem, $|f(x)-f(y)| = \tfrac12|\cos x-\cos y| = \tfrac12|\sin(\xi)||x-y| \le \tfrac12|x-y|$ for some $\xi$ between $x,y$, so $k=1/2$ works.

5. The Banach Fixed-Point Theorem

Definition. A fixed point of $f:X\to X$ is a point $x^*$ with $f(x^*)=x^*$.

Theorem (Banach Fixed-Point Theorem). Let $(X,d)$ be a nonempty complete metric space and $f:X\to X$ a contraction with constant $k<1$. Then $f$ has a unique fixed point $x^*\in X$, and for any $x_0\in X$, the iterates $x_{n+1}=f(x_n)$ converge to $x^*$.

Proof. Existence. Fix any $x_0\in X$ and define $x_{n+1}=f(x_n)$. First,

by induction. For $m>n$, repeated use of the triangle inequality gives

using the geometric series (valid since $0\le k<1$). Since $k^n\to0$ (because $0\le k<1$; this is the geometric-sequence limit, assumed familiar), given $\varepsilon>0$ we can choose $N$ with $k^N d(x_1,x_0)/(1-k) < \varepsilon$, giving $d(x_m,x_n)<\varepsilon$ for all $m,n\ge N$: $(x_n)$ is Cauchy. By completeness of $X$, $x_n\to x^*$ for some $x^*\in X$.

$x^*$ is a fixed point. A contraction is continuous, so $f(x_n)\to f(x^*)$. But $f(x_n)=x_{n+1}\to x^*$ too (it is the same sequence shifted by one index, and shifting an index does not change the limit). By uniqueness of limits (Chapter 2), $f(x^*)=x^*$.

Uniqueness. Suppose $f(x^*)=x^*$ and $f(y^*)=y^*$. Then $d(x^*,y^*) = d(f(x^*),f(y^*)) \le k\,d(x^*,y^*)$. If $d(x^*,y^*)>0$, dividing gives $1\le k$, contradicting $k<1$. So $d(x^*,y^*)=0$, i.e. $x^*=y^*$. $\blacksquare$

Why this is so useful. The proof is constructive: it does not merely assert a solution exists, it produces an algorithm (iterate $f$) and an explicit error bound $d(x_n,x^*)\le \dfrac{k^n}{1-k}d(x_1,x_0)$ for how fast it converges — this is the theoretical basis of Newton's method and many other iterative numerical schemes.

Worked example. Solve $x=\cos(x)/2$ on $X=[-1/2,1/2]$ (check $f$ maps this interval into itself: $|\cos x|\le1$ so $|f(x)|\le1/2$), which is complete (closed subset of complete $\mathbb{R}$). With $k=1/2$ from Section 4, Banach's theorem guarantees a unique $x^*\in[-1/2,1/2]$ with $x^*=\cos(x^*)/2$, approximable to any precision by iterating $x_{n+1}=\cos(x_n)/2$ from any starting point in $[-1/2,1/2]$.

Common Exam Pitfalls

• Confusing Cauchy with convergent. Every convergent sequence is Cauchy (always true), but the converse needs completeness of the space — do not assume it in an arbitrary metric space.
• Forgetting to check $f$ maps $X$ into itself. The theorem requires $f:X\to X$; a map defined on $X$ but landing outside it does not satisfy the hypotheses, and the iteration may leave the space entirely.
• Using a non-uniform or non-strict "contraction". $d(f(x),f(y))<d(x,y)$ for all $x\ne y$ (without a single fixed $k<1$ bounding the ratio) is not enough; the theorem can fail without a uniform $k<1$. A classic counterexample on a non-complete or unbounded domain: $f(x)=x+1/x$ type maps can have $|f(x)-f(y)|<|x-y|$ pointwise yet no fixed point.
• Applying Banach's theorem on an incomplete space. The theorem requires completeness of $X$ itself, not just of the ambient space; e.g. a contraction on $(0,1)$ (not complete) can fail to have a fixed point in $(0,1)$.
• Mixing up the roles of $k$ and the distance itself. $k$ is a single constant independent of $x,y$; checking the contraction inequality "on average" or only for specific pairs is not sufficient — it must hold for all $x,y\in X$.
• Assuming completeness is a property of the point set alone. As Section 3 shows, $(0,1)$ and $\mathbb{R}$ have "the same shape" (homeomorphic) but different completeness status — completeness depends on the metric, not just the topology.

Summary

• A sequence is Cauchy if $d(x_m,x_n)\to0$ as $m,n\to\infty$; every convergent sequence is Cauchy, but the converse requires completeness.
• $(X,d)$ is complete if every Cauchy sequence converges in $X$; $\mathbb{R}$ is complete, proved via Bolzano–Weierstrass; $\mathbb{Q}$ is not.
• Completeness is not an intrinsic/topological property like compactness; it depends on the specific metric, though it is inherited by closed subsets of a complete space.
• A contraction $f:X\to X$ satisfies $d(f(x),f(y))\le k\,d(x,y)$ for a fixed $k<1$, uniformly over all $x,y\in X$.
• Banach Fixed-Point Theorem: on a nonempty complete metric space, every contraction has a unique fixed point, obtained as the limit of the iterates $x_{n+1}=f(x_n)$ from any starting point, with explicit error bound $d(x_n,x^*)\le k^n d(x_1,x_0)/(1-k)$.
• The proof is constructive: existence (via a Cauchy-sequence argument), fixed-point verification (via continuity of $f$), and uniqueness (via a direct contraction estimate) are all explicit and checkable.