From Iterates to a Fixed Point
The Contraction Mapping Theorem states that a contraction on a nonempty complete metric space has a unique fixed point, and that iteration from any starting point converges to it. The proof brings together two ideas from earlier in this course: contraction estimates force successive iterates to become close, and completeness ensures that a Cauchy sequence has a limit in the space. The remaining step is to prove that this limit is fixed by the map.
Fix a starting point \(x_0\in X\) and define \(x_{n+1}=f(x_n)\). The Cauchy Estimate for Successive Iterates gives the key estimate when \(0<q<1\). For integers \(m>n\),
Since \(q^n\) tends to zero, the right-hand side can be made smaller than any prescribed positive number by taking \(n\) sufficiently large. This is precisely the Cauchy condition: once the index is large, all later iterates are close to one another. Completeness now supplies a point \(p\in X\) such that \(x_n\to p\).
If \(q=0\), the contraction inequality says \(d(f(x),f(y))=0\) for all \(x,y\in X\). Thus \(f\) is constant. In particular, \(x_2=f(x_1)=f(x_0)=x_1\), so every iterate from \(x_1\) onward equals \(x_1\). The iteration converges in this case as well. This handles the endpoint allowed in the theorem without using a geometric-series estimate with a zero contraction constant.
The Proof of the Contraction Mapping Theorem
Proof. Choose any \(x_0\in X\), which is possible because \(X\) is nonempty, and define the iterates. If \(0<q<1\), the Cauchy Estimate for Successive Iterates shows that \((x_n)\) is Cauchy. Completeness gives a point \(p\in X\) with \(x_n\to p\). If \(q=0\), the iterates are constant from \(x_1\) onward, so they converge to \(p=x_1\). Thus in either case there is a limit \(p\in X\).
It remains to show that \(f(p)=p\). For every \(n\), the triangle inequality, the contraction inequality, and \(f(x_n)=x_{n+1}\) give
As \(n\) tends to infinity, both \(d(p,x_n)\) and \(d(x_{n+1},p)\) tend to zero. Hence \(d(f(p),p)=0\), which implies \(f(p)=p\) by the defining properties of a metric. This proves existence.
The Uniqueness of a Fixed Point theorem, proved in Contractions, says that a contraction has at most one fixed point. It applies here, so the fixed point \(p\) is unique. The starting point \(x_0\) was arbitrary: the same argument shows that iteration from every point of \(X\) converges to a fixed point. Since there is only one fixed point, every such limit is \(p\). This proves the convergence assertion and completes the proof. \(\square\)
Notice the role of the self-map hypothesis \(f:X\to X\): it ensures that every iterate is defined and remains in \(X\). Completeness then places the limit in \(X\), where the contraction inequality can be applied to compare \(f(p)\) with \(f(x_n)\). A Cauchy sequence in an incomplete space might converge only outside the space, leaving no candidate \(p\) at which to use this argument.
Worked Examples: Applying the Proof
Worked Example: A Polynomial Contraction on an Interval
Let \(X=[0,1]\) with the usual distance and define \(f(x)=(x^2+1)/4\). For \(x\in[0,1]\), \(1\leq x^2+1\leq2\), so \(1/4\leq f(x)\leq1/2\). Thus \(f\) maps \(X\) into itself. The closed interval is complete. For \(x,y\in[0,1]\),
because \(x+y\leq2\). The Contraction Mapping Theorem therefore gives a unique fixed point and convergence of the iterates from every starting point. To identify the point explicitly, solve
Since \(1<\sqrt{3}<2\), the root \(2-\sqrt{3}\) belongs to \([0,1]\), while \(2+\sqrt{3}>1\). The equation used to obtain the root also verifies the fixed-point identity: \((2-\sqrt{3})^2+1=4(2-\sqrt{3})\), so \(f(2-\sqrt{3})=2-\sqrt{3}\). Uniqueness guarantees that no other point of the interval is fixed.
Worked Example: A Contraction on a Square
Let \(X=[0,1]^2\) with the maximum metric \(d((x,y),(u,v))=\max\{|x-u|,|y-v|\}\), and set
The first coordinate lies in \([1/4,3/4]\), and the second lies in \([1/3,2/3]\), so \(F\) maps the square into itself. The square is complete: a Cauchy sequence in the maximum metric has Cauchy coordinate sequences in \([0,1]\); each coordinate converges in \([0,1]\), and the pair converges in the maximum metric. For two points \((x,y),(u,v)\in X\), the coordinate estimates are
Taking the maximum of the two coordinate differences shows that \(F\) is a contraction with constant \(1/2\). Its fixed point is \((1/2,1/2)\): substituting gives first coordinate \((1/2+1/2+1)/4=1/2\), and second coordinate \((1/2+1/2+2)/6=1/2\). The theorem says that iteration converges to this point from every point of the square.
A Localization Result for Closed Subsets
The theorem can be used on a closed part of a larger complete space, provided the map sends that subset into itself. This is useful when the map is defined or convenient on a large space but the desired fixed point is known to lie in a particular region. The subset need not be the whole space; it must be nonempty, closed, and invariant under the map.
Proof. First, \(A\) is complete with the metric inherited from \(X\). Indeed, any Cauchy sequence in \(A\) is a Cauchy sequence in \(X\), so it converges to some point \(a\in X\) by completeness of \(X\). Because \(A\) is closed, it contains the limit \(a\). Thus every Cauchy sequence in \(A\) converges in \(A\). The restriction \(f:A\to A\) is a contraction on the nonempty complete metric space \(A\). Applying the Contraction Mapping Theorem to \(A\) proves the claim. \(\square\)
Worked Example: A Closed Invariant Region
Take \(X=\mathbb{R}\), \(A=[0,2]\), and define \(f:A\to A\) by \(f(x)=1+x/4\). For \(x\in[0,2]\), \(1\leq f(x)\leq3/2\), so \(f(x)\in A\). The interval \(A\) is closed in the complete space \(\mathbb{R}\), and
for all \(x,y\in A\). The closed-subset result gives a unique fixed point in \(A\), with convergence from every starting point in \(A\). Solving \(x=1+x/4\) gives \(3x/4=1\), so \(x=4/3\); substitution verifies \(f(4/3)=1+1/3=4/3\). The invariant set matters: the conclusion is established by applying the theorem on \(A\), where the iteration remains, rather than by assuming that the map is a self-map of all of \(\mathbb{R}\).
Worked Example: A Contraction on a Sequence Space
Worked Example: Prepending a Digit
Let \(S=\{0,1\}^{\mathbb{N}_0}\) be the set of all sequences of zeros and ones indexed from \(0\). For distinct \(s,t\in S\), let \(k\) be the first index at which they differ and define \(d(s,t)=2^{-k}\); set \(d(s,s)=0\). This is a metric. In particular, if \(s\) and \(t\) first differ at index \(k\), then for any third sequence \(u\), at least one of the pairs \((s,u)\) and \((u,t)\) must differ at some index no later than \(k\). Consequently, \(\max\{d(s,u),d(u,t)\}\geq2^{-k}=d(s,t)\), which implies the triangle inequality.
The space is complete. Let \((s^{(m)})\) be a Cauchy sequence in \(S\). For each fixed coordinate \(i\), the Cauchy condition with tolerance \(2^{-i}\) implies that sufficiently late terms agree at coordinate \(i\): if two terms differed there or at an earlier coordinate \(k\leq i\), their distance would be \(2^{-k}\geq2^{-i}\). Define \(s_i\) to be this eventual value at coordinate \(i\). These coordinates define a sequence \(s\in S\). Given \(\varepsilon>0\), choose \(N\) with \(2^{-(N+1)}<\varepsilon\). For all sufficiently large \(m\), \(s^{(m)}\) agrees with \(s\) in coordinates \(0,\ldots,N\). If they differ at all, their first differing coordinate is at least \(N+1\), so \(d(s^{(m)},s)\leq2^{-(N+1)}<\varepsilon\). Hence \(s^{(m)}\to s\), proving completeness.
Define \(T:S\to S\) by \(T(s)=(1,s_0,s_1,\ldots)\), which prepends a \(1\). If \(s\ne t\) first differ at coordinate \(k\), then \(T(s)\) and \(T(t)\) first differ at coordinate \(k+1\). Therefore \(d(T(s),T(t))=2^{-(k+1)}=\tfrac12d(s,t)\), so \(T\) is a contraction. The sequence \(p=(1,1,1,\ldots)\) satisfies \(T(p)=p\), and the theorem guarantees that it is the unique fixed point. It also guarantees convergence to \(p\) from every starting sequence: after \(n\) iterations, the first \(n\) coordinates have been replaced by \(1\), so the distance to \(p\) is at most \(2^{-n}\).
What the Proof Depends On
The argument separates the work cleanly. The contraction estimate makes the iterates Cauchy; completeness puts their limit in the space; and the estimate comparing \(f(p)\) with \(f(x_n)\) shows that the limit is fixed. Uniqueness then identifies the limit for every starting point. When applying the theorem, verify each of these structural requirements: a complete metric space, a self-map, and one contraction constant strictly below one. For a restricted domain, verify that the subset is nonempty, closed, and invariant before applying the theorem there.
Check Your Understanding
Use the proof and examples to answer the following questions.
- Where does completeness enter the proof, and what does it provide?
- Why does \(d(f(p),p)\leq q\,d(p,x_n)+d(x_{n+1},p)\) imply that \(p\) is fixed?
- In the square example, why is the maximum of the two coordinate estimates bounded by one half of the distance between the inputs?
- Why does a closed subset of a complete metric space remain complete with its inherited metric?
- In the sequence-space example, if two inputs first differ at coordinate \(k\), at which coordinate do their images first differ?