The Banach Fixed-Point Theorem, Dense Sets, and Separability

Contractions

A map T : X → X is a contraction if it shrinks all distances by a fixed factor: there is a constant k with 0 ≤ k < 1 such that d(T(x), T(y)) ≤ k · d(x, y) for all x, y. The number k is strictly below 1 — applying T pulls any two points closer, by at least the proportion 1 − k. A fixed point is a point p with T(p) = p, one the map does not move. The theorem below says: on a complete space, a contraction has one and only one fixed point, and you can find it by simply iterating from anywhere.

The Banach fixed-point theorem

Here is the statement and the proof in full. The strategy: start anywhere, iterate, show the orbit is Cauchy (this is where the contraction factor and a geometric series enter), invoke completeness to get a limit, and check the limit is fixed and unique.

BANACH FIXED-POINT THEOREM.
Let (X, d) be a NON-EMPTY COMPLETE metric space and
T : X -> X a contraction with constant k, 0 <= k < 1.
Then T has exactly one fixed point p, and for any start x_0
the iterates x_{n+1} = T(x_n) converge to p.

PROOF.
Step 1 (consecutive gaps shrink geometrically).
  Let D = d(x_0, x_1).  Applying the contraction repeatedly,
      d(x_n, x_{n+1}) = d(T(x_{n-1}), T(x_n)) <= k * d(x_{n-1}, x_n),
  so by induction   d(x_n, x_{n+1}) <= k^n * D.

Step 2 (the orbit is Cauchy).
  For m > n, chain the triangle inequality across the gaps:
      d(x_n, x_m) <= d(x_n,x_{n+1}) + ... + d(x_{m-1}, x_m)
                  <= (k^n + k^{n+1} + ... + k^{m-1}) * D
                  <= k^n * (1 + k + k^2 + ...) * D
                  =  k^n * D / (1 - k).          [geometric series, k<1]
  Since k^n -> 0, the right side -> 0 as n -> infinity,
  so for every epsilon > 0 we can force d(x_n, x_m) < epsilon.
  Hence (x_n) is Cauchy.

Step 3 (a limit exists).
  X is complete, so x_n -> p for some p in X.

Step 4 (p is fixed).
  T is a contraction, hence continuous, so T(x_n) -> T(p).
  But T(x_n) = x_{n+1} -> p as well.
  Limits are unique, so T(p) = p.

Step 5 (uniqueness).
  Suppose T(p) = p and T(q) = q.  Then
      d(p, q) = d(T(p), T(q)) <= k * d(p, q).
  So (1 - k) * d(p, q) <= 0.  Since 1 - k > 0 and d >= 0,
  we get d(p, q) = 0, i.e. p = q.   QED

Dense sets and separability

We finish with a different flavour of structure. A set D is a dense subset of X if its closure is all of X — equivalently, every point of X is a limit of points of D, so every ball, however small, meets D. The rationals are dense in R: any real is approximated as closely as you like by fractions. A space is separable if it has a countable dense subset — a countable scaffold from which, by taking limits, you reach every point.

Separability is a smallness condition that real spaces enjoy and pathological ones violate. The line R is separable, witnessed by the rationals; so is R^n, witnessed by points with rational coordinates. Separability is what lets us approximate and compute: a countable dense set is a list you can iterate over, store, and feed to an algorithm. Many later theorems quietly assume it.