Proof of Contraction Mapping Theorem on a Nonempty Complete Metric Space

By Contraction of a Metric Space §contraction, choose a real number $\lambda$ with $0\le\lambda<1$ such that $f$ is a contraction with constant $\lambda$, that is, $d(f(u),f(v))\le\lambda\,d(u,v)$ for all $u,v\in X$. $\mathbb{R}$ is an ordered field by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §reals, so Rules of Arithmetic and Order in an Ordered Field, Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares and Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality apply to it; powers are as in Commutative Rings, Fields and Ordered Fields: Standard Notation §rings, with $\lambda^{0}=1$, and arithmetic and order in $\mathbb{N}_{0}$ obey The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §laws.

Step 0 (the constant). $\lambda\le1$ as $\lambda<1$, and $0<1-\lambda$ by Rules of Arithmetic and Order in an Ordered Field §order-sum. Since $0<1$ by Rules of Arithmetic and Order in an Ordered Field §squares, $-1<-0$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §strict-negative, and $-0=0$ by Negatives, Differences, Reciprocals and Quotients §negative, as $0+0=0$ by the neutral law of Commutative Rings §ring; so $-1<\lambda$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §mixed, and $|\lambda|<1$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §absolute-strict. Hence $\lambda^{n}\to0$ by Completeness of the Real Numbers for Sequences: Monotone Convergence, the Bolzano-Weierstrass Theorem and Cauchy Sequences §geometric, and for every real $C$ the sequence $(C\lambda^{n})_{n\in\mathbb{N}}$ converges to $C\cdot0=0$ by Limits of Sequences of Real Numbers: Uniqueness, Boundedness, Constants, Tails, Arithmetic, Quotients, Absolute Values, Finite Sums, Order, Squeezing, Domination and Subsequences §arithmetic and Rules of Arithmetic in a Commutative Ring: Zero, Signs and Squares, and No Zero Divisors in a Field §zero. As $C\lambda^{n}=C\lambda^{n}-0\le|C\lambda^{n}-0|$ by Rules of Arithmetic and Order in an Ordered Field §absolute-value, Convergent Sequences of Real Numbers §converges and Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §mixed give: (G) for every real $C$ and every real $\varepsilon>0$ there is $N\in\mathbb{N}$ with $C\lambda^{n}<\varepsilon$ for all $n\in\mathbb{N}$ with $n\ge N$.

Step 1 (geometric decay). Let $(c_{n})$ be a sequence in $\mathbb{R}$ with $c_{n+1}\le\lambda c_{n}$ for every $n\in\mathbb{N}$. We show $c_{j+1}\le\lambda^{j}c_{1}$ for every $j\in\mathbb{N}_{0}$, by induction from $0$ on $\mathbb{N}_{0}$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §induction). For $j=0$, $c_{1}=1\cdot c_{1}=\lambda^{0}c_{1}$. If $c_{j+1}\le\lambda^{j}c_{1}$, then, as $j+1\in\mathbb{N}$ and $0\le\lambda$, Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §nonnegative-scaling gives $c_{j+2}\le\lambda c_{j+1}\le\lambda\lambda^{j}c_{1}=\lambda^{j+1}c_{1}$, the equality by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §exponents and Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product.

Step 2 (shifting an index). Let $N,m\in\mathbb{N}$ with $N+1\le m$. Then $1\le m$, so $n=m-1\in\mathbb{N}_{0}$ satisfies $n+1=m$ by The Difference of Two Natural Numbers with Zero §difference; from $N+1\le n+1$ we get $N\le n$, so $n\in\mathbb{N}$ with $n\ge N$.

Step 3 (iteration). Let $(x_{n})$ be a sequence in $X$ with $x_{n+1}=f(x_{n})$ for every $n\in\mathbb{N}$, and let $p\in X$ with $f(p)=p$. Put $c_{n}=d(x_{n},p)$. Then $c_{n+1}=d(f(x_{n}),f(p))\le\lambda c_{n}$, so $c_{j+1}\le\lambda^{j}c_{1}$ for $j\in\mathbb{N}_{0}$ by Step 1. Let $\varepsilon>0$ be real; by (G) with $C=c_{1}$ choose $N\in\mathbb{N}$ with $c_{1}\lambda^{n}<\varepsilon$ for all $n\ge N$. For $m\in\mathbb{N}$ with $m\ge N+1$, take $n$ as in Step 2; then $d(x_{m},p)=c_{n+1}\le\lambda^{n}c_{1}<\varepsilon$, so $d(x_{m},p)<\varepsilon$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §mixed. Hence $(x_{n})$ converges to $p$ in $(X,d)$ by Convergent Sequence in a Metric Space §converges, with $N+1$ as the index there. This proves the clause iteration.

Step 4 (a Cauchy sequence of iterates). As $X$ is nonempty, choose $a\in X$. By Sets and Maps: Ordinary Notation §maps there is a map $g:\mathbb{N}\times X\to X$ with $g(n,u)=f(u)$, and by Recursion on the Natural Numbers Starting at One §recursion a map $x:\mathbb{N}\to X$, a sequence $(x_{n})$ in $X$ by Sequences §sequence, with $x_{1}=a$ and $x_{n+1}=g(n,x_{n})=f(x_{n})$ for every $n\in\mathbb{N}$.

Put $e_{n}=d(x_{n},x_{n+1})$. Then $e_{n+1}=d(f(x_{n}),f(x_{n+1}))\le\lambda e_{n}$, so Step 1 gives $e_{j+1}\le\lambda^{j}D$ for $j\in\mathbb{N}_{0}$, where $D=e_{1}\ge0$ by Metric Space §nonnegative. Let $S=D/(1-\lambda)$ and $t_{j}=\lambda^{j}S$ for $j\in\mathbb{N}_{0}$. By Rules of Arithmetic and Order in an Ordered Field §positive-reciprocal, Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §sign and Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §positive-product, $0\le S$ and $0\le t_{j}$. By Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §exponents, Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product, Rules of Arithmetic in a Commutative Ring: Zero, Signs and Squares, and No Zero Divisors in a Field §signs and Negatives, Differences, Reciprocals and Quotients §reciprocal, $t_{j}-t_{j+1}=\lambda^{j}S(1-\lambda)=\lambda^{j}D$, so $e_{j+1}\le t_{j}-t_{j+1}$.

Fix $j\in\mathbb{N}_{0}$; we show $d(x_{j+1},x_{j+1+k})\le t_{j}-t_{j+k}$ for every $k\in\mathbb{N}_{0}$, by induction on $k$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §induction). For $k=0$ both sides are $0$, by Metric Space §zero and Negatives, Differences, Reciprocals and Quotients §negative. If it holds for $k$, then Metric Space §triangle and Rules of Arithmetic and Order in an Ordered Field §order-sum give

$$d(x_{j+1},x_{j+k+2})\le d(x_{j+1},x_{j+k+1})+e_{j+k+1}\le(t_{j}-t_{j+k})+(t_{j+k}-t_{j+k+1})=t_{j}-t_{j+k+1}.$$

As $0\le t_{j+k}$, Rules of Arithmetic and Order in an Ordered Field §order-sum also gives $t_{j}-t_{j+k}\le t_{j}$; so $d(x_{j+1},x_{j+1+k})\le t_{j}$ for all $j,k\in\mathbb{N}_{0}$.

Let $\varepsilon>0$ be real; by (G) with $C=S$ choose $N\in\mathbb{N}$ with $t_{n}=S\lambda^{n}<\varepsilon$ for all $n\ge N$. Let $m,\ell\in\mathbb{N}$ with $m,\ell\ge N+1$; by Metric Space §symmetric and totality of the order of $\mathbb{N}$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §order, Partial and Total Orders on a Set and the Associated Strict Relation §total) we may assume $m\le\ell$. Take $n$ as in Step 2 for $m$, and $k=\ell-m\in\mathbb{N}_{0}$, so $m+k=\ell$ by The Difference of Two Natural Numbers with Zero §difference. Then $d(x_{m},x_{\ell})=d(x_{n+1},x_{n+1+k})\le t_{n}<\varepsilon$, and $d(x_{m},x_{\ell})<\varepsilon$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §mixed. So $(x_{n})$ is a Cauchy sequence in $(X,d)$ by Cauchy Sequence in a Metric Space §cauchy, with $N+1$ as the index there.

Step 5 (a fixed point). As $(X,d)$ is complete, Complete Metric Space §complete and Convergent Sequence in a Metric Space §convergent give $p\in X$ to which $(x_{n})$ converges. Let $(y_{n})$ be the sequence $n\mapsto x_{n+1}$ in $X$ (Sets and Maps: Ordinary Notation §maps). Let $\varepsilon>0$ be real and choose $N\in\mathbb{N}$ with $d(x_{n},p)<\varepsilon$ for all $n\ge N$ (Convergent Sequence in a Metric Space §converges). For $n\ge N$ we have $n+1\ge N$, so $d(y_{n},p)<\varepsilon$; and since $\lambda\le1$ and $0\le d(x_{n},p)$, Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §nonnegative-scaling and Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §mixed give

$$d(y_{n},f(p))=d(f(x_{n}),f(p))\le\lambda\,d(x_{n},p)\le d(x_{n},p)<\varepsilon .$$

So $(y_{n})$ converges to both $p$ and $f(p)$ in $(X,d)$, and $f(p)=p$ by Uniqueness of Limits in a Metric Space §unique.

Step 6 (uniqueness). Let $p,q\in X$ with $f(p)=p$ and $f(q)=q$, and put $t=d(p,q)$, so $0\le t$ by Metric Space §nonnegative and $t=d(f(p),f(q))\le\lambda t$. If $0<t$, then $\lambda t<1\cdot t=t$ by Rules of Arithmetic and Order in an Ordered Field §order-product, and $t<t$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §mixed, which is impossible. Hence $t=0$, and $p=q$ by Metric Space §zero. With Step 5 this proves the clause fixed-point.