Metric Spaces & Completeness
Metric Spaces & Completeness
A metric space $(X,d)$ generalizes real analysis to abstract settings. A sequence $(x_n)$ is Cauchy if $d(x_m,x_n)\to 0$; the space is complete if every Cauchy sequence converges. The contraction mapping theorem (Banach fixed-point theorem) guarantees a unique fixed point for contractions in complete metric spaces, with applications ranging from the existence of ODE solutions to the convergence of iterative algorithms.
Metric Space & Completeness
A metric space is $(X,d)$ where $d:X\times X\to[0,\infty)$ satisfies: (i) $d(x,y)=0\iff x=y$; (ii) $d(x,y)=d(y,x)$; (iii) $d(x,z)\leq d(x,y)+d(y,z)$ (triangle inequality). Examples: $\mathbb{R}^n$ with Euclidean metric; $C[a,b]$ with $d(f,g)=\sup|f-g|$; discrete metric. $(X,d)$ is complete if every Cauchy sequence converges in $X$. $\mathbb{R}$ is complete ($\mathbb{Q}$ is not); $C[a,b]$ with sup-metric is complete (Banach space).
Banach Fixed-Point Theorem
Let $(X,d)$ be a complete metric space and $T:X\to X$ a contraction: $d(Tx,Ty)\leq k\cdot d(x,y)$ for all $x,y$ and some $k\in[0,1)$. Then $T$ has a unique fixed point $x^*=Tx^*$, and for any $x_0\in X$, the iteration $x_{n+1}=T(x_n)$ converges to $x^*$ with error $d(x_n,x^*)\leq k^n d(x_0,x^*)/(1-k)$. Proof: $(x_n)$ is Cauchy: $d(x_{n+1},x_n)\leq k^n d(x_1,x_0)$, so $d(x_{n+m},x_n)\leq k^n d(x_1,x_0)/(1-k)\to 0$. The limit satisfies $Tx^*=x^*$; uniqueness follows from $d(x^*,y^*)\leq k d(x^*,y^*)$ implying $d=0$.
Example 1
Show $(C[0,1],\|\cdot\|_\infty)$ is complete.
Solution: Let $(f_n)$ be Cauchy: $\|f_n-f_m\|_\infty\to 0$. For each $x$, $(f_n(x))$ is Cauchy in $\mathbb{R}$ (since $|f_n(x)-f_m(x)|\leq\|f_n-f_m\|_\infty$), so $f_n(x)\to f(x)$ pointwise. This convergence is uniform: given $\epsilon>0$, choose $N$ so $\|f_n-f_m\|_\infty<\epsilon$ for $n,m>N$; letting $m\to\infty$, $|f_n(x)-f(x)|\leq\epsilon$ for all $x$. So $f_n\to f$ uniformly, and $f$ is continuous (uniform limit of continuous). Hence $f\in C[0,1]$ and $f_n\to f$ in $C[0,1]$.
Example 2
Use the Banach fixed-point theorem to prove the Picard-Lindelöf theorem: $\dot{y}=f(t,y)$, $y(0)=y_0$, has a unique local solution if $f$ is Lipschitz in $y$.
Solution: The ODE is equivalent to the integral equation $y(t)=y_0+\int_0^t f(s,y(s))\,ds$. Define $T:C[0,\tau]\to C[0,\tau]$ by $(Ty)(t)=y_0+\int_0^t f(s,y(s))\,ds$. With Lipschitz constant $L$ and $\tau<1/L$: $\|Ty-Tz\|_\infty\leq\int_0^\tau L|y(s)-z(s)|\,ds\leq L\tau\|y-z\|_\infty$. Since $L\tau<1$, $T$ is a contraction on $(C[0,\tau],\|\cdot\|_\infty)$ (complete). By Banach, there is a unique fixed point — the unique solution.
Practice
- Show that the $\ell^2$ space of square-summable sequences is a complete metric space.
- Prove that a compact metric space is complete and separable.
- Give an example of a metric space that is not complete, and describe its completion.
- Apply the Banach fixed-point theorem to show Newton's method converges quadratically near a simple root.
Show Answer Key
1. If $(x^{(k)})$ is Cauchy in $\ell^2$, define $x_n=\lim_k x_n^{(k)}$ (each coordinate converges). The limit $x=(x_n)$ is in $\ell^2$ by Fatou's lemma, and $\|x^{(k)}-x\|_2\to0$ by dominated convergence.
2. Compact $\Rightarrow$ sequentially compact $\Rightarrow$ every Cauchy sequence has a convergent subsequence $\Rightarrow$ every Cauchy sequence converges (since the subsequence limit equals the sequence limit) $\Rightarrow$ complete. Separable: for each $n$, cover by $1/n$-balls; compactness gives a finite subcover. The centers form a countable dense subset.
3. $\mathbb{Q}$ with the usual metric is not complete ($\sqrt{2}$ is the limit of a Cauchy sequence of rationals). Its completion is $\mathbb{R}$ — the set of equivalence classes of Cauchy sequences of rationals.
4. Near a simple root $r$ with $f(r)=0$, $f'(r)\neq0$: Newton's map $T(x)=x-f(x)/f'(x)$ satisfies $|T(x)-r|\le C|x-r|^2$ for some $C$. Choose $\delta$ small enough that $C\delta<1$. Then $T$ maps $B(r,\delta)$ into itself, and $|x_{n+1}-r|\le C|x_n-r|^2$ gives quadratic convergence by Banach fixed-point theorem.