Topology

Metric spaces

A metric space equips a set with a distance function satisfying three axioms; contraction mappings on complete metric spaces always have a unique fixed point (Banach's theorem), the engine behind PageRank, iterative solvers, and fractal image compression.

IntuitionMeasuring distance without a ruler

GPS uses straight-line distance, a taxi driver uses street-grid distance, and a spell-checker uses "edit distance" between words. All three are legitimate notions of distance because they share the same three common-sense rules: distance is never negative and is zero only when two points coincide, distance from $A$ to $B$ equals distance from $B$ to $A$ , and going via a detour $C$ never shortens the direct trip from $A$ to $B$ . A metric space is exactly a set equipped with any distance function obeying these three rules.

The map

T(x) = 0.5x + 1

\mathbb{R}

(with

d(x,y)=|x-y|

) is a contraction with ratio

q=0.5

: it always halves the distance between any two points. Adjust the sliders and watch that every starting point iterates toward the same fixed point

x^* = 2

UndergraduateThe three axioms

Definition: Metric space

A metric on a set $X$ is a function $d: X \times X \to \mathbb{R}$ satisfying, for all $x,y,z \in X$ : (M1) positivity $d(x,y) \ge 0,\ d(x,y)=0 \iff x=y$ ; (M2) symmetry $d(x,y) = d(y,x)$ ; (M3) the triangle inequality $d(x,z) \le d(x,y) + d(y,z)$ . The pair $(X,d)$ is a metric space.

d(x,y) \ge 0,\quad d(x,y)=0 \iff x=y \qquad d(x,y)=d(y,x) \qquad d(x,z) \le d(x,y)+d(y,z)

Two families of examples matter most. On $\mathbb{R}^n$ , the ** $\ell_p$ metrics** are $d_p(x,y) = \left(\sum_{i=1}^n |x_i - y_i|^p\right)^{1/p}$ for $p \ge 1$ (so $p=2$ gives ordinary Euclidean distance, $p=1$ gives "taxicab" distance, and $p\to\infty$ gives the maximum coordinate difference). On the space $C([a,b])$ of continuous functions, the sup-metric is $d_\infty(f,g) = \sup_{t \in [a,b]} |f(t) - g(t)|$ : two functions are close if their graphs never separate by more than a small margin anywhere on $[a,b]$ .

d_p(x,y) = \left(\sum_{i=1}^n |x_i - y_i|^p\right)^{1/p} \qquad d_\infty(f,g) = \sup_{t \in [a,b]} |f(t) - g(t)|

Metrics on $\mathbb{R}^n$ compared
Metric	Formula	Unit ball shape	Typical use
$\ell_1$ (taxicab)	$\sum \|x_i-y_i\|$	diamond	sparse recovery, city blocks
$\ell_2$ (Euclidean)	$\sqrt{\sum (x_i-y_i)^2}$	disk	physical distance, PCA
$\ell_\infty$ (Chebyshev)	$\max_i \|x_i-y_i\|$	square	worst-case error bound

UndergraduateBalls, completeness, and contractions

The open ball $B(x_0, r) = \{x \in X : d(x, x_0) < r\}$ is the set of points within distance $r$ of the center. A sequence $(x_n)$ is Cauchy if $\forall \varepsilon > 0\ \exists N\ \forall m,n > N:\ d(x_m,x_n) < \varepsilon$ : its terms eventually get arbitrarily close to each other (not necessarily to any fixed limit point yet). A metric space is complete if every Cauchy sequence converges to a point of $X$ . $\mathbb{R}^n$ with any $\ell_p$ metric is complete; $\mathbb{Q}$ with $d(x,y)=|x-y|$ is not, since $\sqrt{2}$ is missing.

UndergraduateTheorems

Theorem: Reverse triangle inequality

For all $x,y,z$ in a metric space, $|d(x,z) - d(y,z)| \le d(x,y)$ .

Why is it true?

It shows the distance function itself is Lipschitz-continuous (with constant 1) in each argument, which is what lets you take limits of distances safely.

Proof

Step 1 — Two applications of the triangle inequality. By (M3), $d(x,z) \le d(x,y) + d(y,z)$ , which rearranges to $d(x,z) - d(y,z) \le d(x,y)$ . Swapping the roles of $x$ and $y$ in the same axiom gives $d(y,z) \le d(y,x) + d(x,z) = d(x,y) + d(x,z)$ (using symmetry $d(y,x)=d(x,y)$ ), which rearranges to $d(y,z) - d(x,z) \le d(x,y)$ , i.e. $-(d(x,z)-d(y,z)) \le d(x,y)$ .

Step 2 — Combine both bounds. The two inequalities say $d(x,z)-d(y,z) \le d(x,y)$ and $-(d(x,z)-d(y,z)) \le d(x,y)$ simultaneously, which is exactly the statement $|d(x,z)-d(y,z)| \le d(x,y)$ by the definition of absolute value: a real number $u$ satisfies $|u| \le c$ precisely when both $u \le c$ and $-u \le c$ hold.

Theorem: Banach fixed-point theorem (contraction mapping theorem)

Let $(X,d)$ be a complete metric space and $T: X \to X$ a contraction: $d(T(x), T(y)) \le q\, d(x,y)$ for some fixed $0 \le q < 1$ and all $x,y \in X$ . Then $T$ has exactly one fixed point $x^* \in X$ (i.e. $T(x^*)=x^*$ ), and starting from any $x_0 \in X$ the iterates $x_{n+1}=T(x_n)$ converge to $x^*$ with the explicit error bound $d(x_n, x^*) \le \dfrac{q^n}{1-q}\, d(x_1, x_0)$ .

Why is it true?

It converts existence-and-uniqueness questions (does this equation have exactly one solution?) into a mechanical, guaranteed-to-converge computation, with a precomputable bound on how many iterations are needed for any target accuracy.

Proof

Step 1 — The iterates form a Cauchy sequence. Fix $x_0 \in X$ and set $x_n = T^n(x_0)$ . By the contraction property applied repeatedly, $d(x_{n+1},x_n) = d(T(x_n),T(x_{n-1})) \le q\,d(x_n,x_{n-1}) \le \dots \le q^n\,d(x_1,x_0)$ . For $m > n$ , the triangle inequality chains this along the path $x_n, x_{n+1}, \dots, x_m$ : $d(x_m,x_n) \le \sum_{k=n}^{m-1} d(x_{k+1},x_k) \le \sum_{k=n}^{m-1} q^k\,d(x_1,x_0) \le d(x_1,x_0)\sum_{k=n}^{\infty} q^k = d(x_1,x_0)\,\dfrac{q^n}{1-q}$ , using the geometric series formula since $0 \le q < 1$ . As $n \to \infty$ , $q^n \to 0$ , so this tail bound goes to 0: $(x_n)$ is Cauchy.

Step 2 — Completeness gives a limit, and continuity makes it a fixed point. Since $X$ is complete, the Cauchy sequence $(x_n)$ converges to some $x^* \in X$ . The contraction inequality $d(T(x),T(y)) \le q\,d(x,y)$ shows $T$ is (Lipschitz) continuous, so $T(x^*) = T(\lim_n x_n) = \lim_n T(x_n) = \lim_n x_{n+1} = x^*$ . Thus $x^*$ is a fixed point.

Step 3 — Uniqueness. Suppose $x^*$ and $y^*$ are both fixed points. Then $d(x^*,y^*) = d(T(x^*),T(y^*)) \le q\,d(x^*,y^*)$ , so $(1-q)\,d(x^*,y^*) \le 0$ . Since $1-q>0$ , this forces $d(x^*,y^*)=0$ , i.e. $x^*=y^*$ .

Step 4 — The error bound. Letting $m \to \infty$ in the Step 1 estimate $d(x_m,x_n) \le \dfrac{q^n}{1-q}\,d(x_1,x_0)$ and using continuity of $d$ gives exactly $d(x_n,x^*) \le \dfrac{q^n}{1-q}\,d(x_1,x_0)$ : the distance to the true fixed point after $n$ steps shrinks geometrically, and the bound can be computed before running a single iteration.

UndergraduateReal-World Applications and Worked Examples

Google's PageRank computes the dominant eigenvector of a web-link matrix by repeatedly applying it to a probability vector — this power iteration is a contraction in the $\ell_1$ metric on probability distributions. Iterative linear solvers (Jacobi, Gauss–Seidel) rewrite $Ax=b$ as a fixed-point map $x \mapsto Cx+d$ that is a contraction in the sup-metric whenever $A$ is diagonally dominant. Fractal (IFS) image compression represents an image as the unique fixed point of a contraction on the space of images equipped with the sup/Hausdorff metric, so decompression is just iterating the map.

Example: PageRank as a contraction on probability vectors

A tiny 2-page web has link matrix $M = \begin{pmatrix} 0.1 & 0.9 \\ 0.9 & 0.1 \end{pmatrix}$ (each column redistributes rank with a damping factor). Starting from $r_0 = (1,0)$ , compute $r_1 = Mr_0$ and $r_2 = Mr_1$ using the $\ell_1$ metric $d(x,y)=|x_1-y_1|+|x_2-y_2|$ , and check $d(r_1,r_2) \le q\,d(r_0,r_1)$ for $q=0.8$ .

Solution

Step 1 — Compute $r_1$ . $r_1 = M r_0 = (0.1 \cdot 1 + 0.9 \cdot 0,\ 0.9 \cdot 1 + 0.1 \cdot 0) = (0.1, 0.9)$ .

Step 2 — Compute $r_2$ . $r_2 = M r_1 = (0.1(0.1)+0.9(0.9),\ 0.9(0.1)+0.1(0.9)) = (0.01+0.81,\ 0.09+0.09) = (0.82, 0.18)$ .

Step 3 — Compute distances and check the contraction ratio. $d(r_0,r_1) = |1-0.1|+|0-0.9| = 0.9+0.9=1.8$ . $d(r_1,r_2)=|0.1-0.82|+|0.9-0.18|=0.72+0.72=1.44$ . Indeed $1.44 = 0.8 \times 1.8$ , matching $q=0.8$ exactly (the row/column sums of $M$ shifted by 0.5 from the damping factor give this ratio), confirming the iteration contracts and will converge to the stationary rank vector $(0.5,0.5)$ .

Example: How many iterations for a target compression accuracy?

A fractal image-compression decoder applies a contraction $T$ with ratio $q=0.6$ on the sup-metric over images, and the first two iterates satisfy $d(x_1,x_0)=100$ (pixel-intensity units). Using the error bound $d(x_n, x^*) \le \dfrac{q^n}{1-q}\, d(x_1, x_0)$ , find the smallest $n$ guaranteeing $d(x_n,x^*) < 1$ .

Solution

Step 1 — Write the inequality to solve. We need $\dfrac{q^n}{1-q}\,d(x_1,x_0) < 1$ , i.e. $\dfrac{0.6^n}{0.4} \times 100 < 1$ , i.e. $0.6^n < 0.004$ .

Step 2 — Take logarithms. $n \ln(0.6) < \ln(0.004)$ . Since $\ln(0.6) \approx -0.5108$ is negative, dividing flips the inequality: $n > \dfrac{\ln(0.004)}{\ln(0.6)} = \dfrac{-5.521}{-0.5108} \approx 10.81$ .

Step 3 — Round up to the smallest integer. $n = 11$ iterations guarantee $d(x_n,x^*) < 1$ pixel-intensity unit, and this number was known before running any iteration — exactly the practical value of the a priori error bound in compression codecs.

Which property FAILS for $d(x,y) = (x-y)^2$ on $\mathbb{R}$ ?

Using the $\ell_2$ metric, what is $d((1,2,2),(4,6,2))$ in $\mathbb{R}^3$ ?

An iterative solver has contraction ratio $q=0.9$ instead of $q=0.1$ for the same problem. What happens?

Which pair of conditions guarantees the Banach fixed-point theorem applies?

References

Walter Rudin (1976). Principles of Mathematical Analysis
James Munkres (2000). Topology
Shaojie Bai, J. Zico Kolter, Vladlen Koltun (2019). Deep Equilibrium Models · arXiv:1909.01377