Contractions

From Fixed-Point Problems to Distance Shrinking

In Fixed-Point Problems, continuity on a closed interval provided an existence argument, while the closedness result described the fixed-point set when the space was Hausdorff. Neither result, on its own, gave a general method for finding a fixed point or guaranteed uniqueness. A contraction supplies a stronger kind of control: it brings every pair of points closer by a uniform factor strictly less than one. That distance estimate will make fixed points unique and will control the successive approximations obtained by repeatedly applying the map.

The setting is a metric space $(X,d)$ and a self-map $f:X\to X$. A metric is needed because the condition compares distances between points and their images. The strict inequality in the definition is essential: a map that merely does not increase distances need not have the same properties.

Definition: Let $(X,d)$ be a metric space and $f:X\to X$. The map $f$ is a contraction if there is a real number $q$ with $0\leq q<1$ such that, for every $x,y\in X$, $$ d(f(x),f(y))\leq q\,d(x,y). $$ Such a number $q$ is called a contraction constant for $f$.

The constant is not necessarily unique. If the inequality holds with one constant $q$, it also holds with any larger constant less than one. The definition requires one constant to work for every pair of points, not a separate factor chosen for each pair. The value $q=0$ is allowed: in that case all image points have distance zero, so the map is constant when $X$ is nonempty.

Immediate Consequences of the Contraction Inequality

The distance estimate first implies continuity. It also rules out two distinct fixed points. These facts follow directly from the defining inequality, so they do not require compactness, connectedness, or completeness of the metric space.

Theorem: Every contraction $f:X\to X$ is continuous.

Proof. Fix $x\in X$, and let $\varepsilon>0$. Choose a contraction constant $q$ for $f$. If $q=0$, then $f$ is constant, so $d(f(y),f(x))=0<\varepsilon$ for every $y\in X$; any $\delta>0$ works. If $q>0$, choose $\delta=\varepsilon/q$. Whenever $d(y,x)<\delta$, the contraction inequality gives

d(f(y),f(x))\leq q\,d(y,x)<q\delta=\varepsilon.

Thus $f$ is continuous at $x$. Since $x$ was arbitrary, $f$ is continuous on $X$. $\square$

Theorem (Uniqueness of a Fixed Point): A contraction on a metric space has at most one fixed point.

Proof. Suppose $p$ and $r$ are fixed points of $f$, and let $q<1$ be a contraction constant. Then

d(p,r)=d(f(p),f(r))\leq q\,d(p,r).

Since $d(p,r)\geq0$ and $1-q>0$, this inequality implies $(1-q)d(p,r)\leq0$, so $d(p,r)=0$. The defining property of a metric then gives $p=r$. Therefore there cannot be two distinct fixed points. This proves at most one, not existence: the theorem does not assert that a fixed point must be present. $\square$

Worked Example: An Affine Contraction on a Closed Interval

Define $f:[0,1]\to[0,1]$ by $f(x)=x/3+2/3$. For $0\leq x\leq1$, the value lies between $2/3$ and $1$, so this is indeed a self-map. For any $x,y\in[0,1]$,

|f(x)-f(y)| =\left|\frac{x-y}{3}\right| =\frac{1}{3}|x-y|.

Thus $f$ is a contraction with constant $q=1/3$. Solving the fixed-point equation gives

\frac{x}{3}+\frac{2}{3}=x \quad\Longleftrightarrow\quad x+2=3x \quad\Longleftrightarrow\quad x=1.

Substitution verifies the candidate: $f(1)=1/3+2/3=1$. The uniqueness theorem now shows that this is the only fixed point in the interval.

Worked Example: A Nonlinear Contraction on a Short Interval

Let $X=[1,4]$ with the usual distance, and define $f(x)=\sqrt{x}$. Since $1\leq\sqrt{x}\leq2$ whenever $x\in[1,4]$, the image lies in $[1,4]$. For $x,y\in[1,4]$, rationalizing the difference gives

|\sqrt{x}-\sqrt{y}| =\frac{|x-y|}{\sqrt{x}+\sqrt{y}} \leq\frac{1}{2}|x-y|,

because both square roots are at least $1$. Therefore $f$ is a contraction with constant $1/2$. Its fixed-point equation is $\sqrt{x}=x$. Both sides are nonnegative, so squaring gives $x=x^2$, or $x(x-1)=0$. The only solution in $[1,4]$ is $x=1$, and $f(1)=1$. In particular, the contraction theorem about uniqueness is consistent with the direct solution.

Repeated Iteration and Geometric Control

A natural way to search for a fixed point is to start at a point $x_0\in X$, apply $f$, then apply $f$ to the result, and continue. This defines the iterates $x_{n+1}=f(x_n)$. The contraction inequality can be applied repeatedly: after each step, the distance between two iterated points shrinks by at least another factor $q$.

Theorem (Contraction Estimate for Iterates): Let $f:X\to X$ be a contraction with constant $q$, where $0\leq q<1$. For every $x,y\in X$ and every integer $n\geq0$, $$ d(f^n(x),f^n(y))\leq q^n d(x,y), $$ where $f^0$ is the identity map.

Proof. We use induction on $n$. For $n=0$, $f^0$ is the identity, so the two sides are equal. Suppose the estimate holds for some $n\geq0$. Applying the contraction inequality to $f^n(x)$ and $f^n(y)$, and then using the induction hypothesis, gives

d(f^{n+1}(x),f^{n+1}(y)) \leq q\,d(f^n(x),f^n(y)) \leq q\,q^n d(x,y) =q^{n+1}d(x,y).

This proves the estimate for $n+1$, and hence for every $n\geq0$. $\square$

The notation $f^n$ here means repeated composition, not an ordinary numerical power of the values of $f$. The estimate says that two starting points become progressively harder to distinguish after the same number of iterations. It does not yet say that the iterates of one starting point converge; for that, we need to compare different stages of the same iteration.

Theorem (Cauchy Estimate for Successive Iterates): Let $f:X\to X$ be a contraction with constant $q$, and choose $x_0\in X$. Define $x_{n+1}=f(x_n)$ for $n\geq0$. For integers $m>n\geq0$, $$ d(x_m,x_n)\leq \frac{q^n}{1-q}\,d(x_1,x_0). $$ Consequently, $(x_n)$ is a Cauchy sequence.

Proof. First, for every $k\geq0$, the contraction inequality gives

d(x_{k+1},x_k) =d(f(x_k),f(x_{k-1})) \leq q\,d(x_k,x_{k-1})\qquad (k\geq1).

By induction, $d(x_{k+1},x_k)\leq q^k d(x_1,x_0)$ for every $k\geq0$; the case $k=0$ is equality. For $m>n$, the triangle inequality and this bound yield

d(x_m,x_n) \leq\sum_{k=n}^{m-1}d(x_{k+1},x_k) \leq d(x_1,x_0)\sum_{k=n}^{m-1}q^k \leq \frac{q^n}{1-q}\,d(x_1,x_0).

The last inequality follows from the finite geometric-sum bound and $0\leq q<1$. As $n$ tends to infinity, $q^n/(1-q)$ tends to zero (and when $q=0$, the bound is already zero for $n\geq1$). Given $\varepsilon>0$, choose $N$ so that the displayed bound is less than $\varepsilon$ whenever $n\geq N$. If $m>n\geq N$, then $d(x_m,x_n)<\varepsilon$; the same conclusion for $n>m$ follows by symmetry, and for $m=n$ the distance is zero. Thus $(x_n)$ is Cauchy. $\square$

Worked Example: Iteration Can Fail to Produce a Fixed Point in an Incomplete Space

Take $X=(0,1)$ with the usual distance and define $f(x)=x/2$. For $x\in(0,1)$, $f(x)\in(0,1/2)\subset(0,1)$, so $f$ is a self-map. Also,

|f(x)-f(y)|=\frac{1}{2}|x-y|,

so it is a contraction with constant $1/2$. A fixed point would satisfy $x/2=x$, which forces $x=0$; but $0\notin X$. Thus the map has no fixed point in its space.

Starting from any $x_0\in(0,1)$, the iterates are $x_n=x_0/2^n$. Indeed, this holds for $n=0$, and if $x_n=x_0/2^n$, then $x_{n+1}=f(x_n)=x_0/2^{n+1}$. They approach $0$, which is not in $X$. The sequence is Cauchy but has no limit in $X$, illustrating why a Cauchy estimate alone does not guarantee a fixed point in the space.

What the Contraction Condition Does—and Does Not—Say

The defining inequality is a uniform, strict form of distance reduction. A useful comparison is a map satisfying $d(f(x),f(y))\leq d(x,y)$, sometimes called nonexpansive. Such a map need not be a contraction: the identity map satisfies this inequality, but on a space with more than one point it has many fixed points. Its distance factor is $1$, which is excluded by the contraction definition.

The strict factor $q<1$ is exactly what makes the uniqueness proof work: if two fixed points existed, their distance would be at most $q$ times itself, forcing that distance to be zero. The same factor also produces the geometric sum in the Cauchy estimate. Yet neither argument places the limit of the iterates inside $X$. The example on $(0,1)$ shows that this issue is substantive, not merely technical.

In a complete metric space, every Cauchy sequence converges to a point of the space. Combined with the estimate above and continuity of a contraction, this is the mechanism behind the contraction mapping theorem: iteration produces a limit, and continuity makes that limit a fixed point. The next tutorial develops the theorem with its full existence and uniqueness conclusion. Here, the key distinction is that the results proved so far establish continuity, at-most-one fixed point, and Cauchy behavior; existence requires an additional hypothesis on the space.

Verify a self-map.
Check that every value $f(x)$ lies in the metric space $X$.

Find a uniform factor.
Show that one constant $q<1$ bounds $d(f(x),f(y))$ by $q\,d(x,y)$ for all pairs.

Use the consequences carefully.
A contraction is continuous, has at most one fixed point, and generates a Cauchy sequence of iterates.

Check completeness for existence.
The Cauchy property guarantees a limit in the space only when the space is complete.

Check Your Understanding

Use the definition and results in this tutorial to answer the following questions.

Why must the contraction constant be strictly less than one, rather than merely less than or equal to one, for the fixed-point uniqueness proof?
Show that the constant map $f(x)=c$ on a nonempty metric space is a contraction, and identify a fixed point when $c\in X$.
For the iteration $x_{n+1}=f(x_n)$, explain why the distances between consecutive terms are bounded by a geometric sequence.
Does the contraction estimate for iterates alone prove that $f$ has a fixed point? Explain the role of completeness.
Give an example of a map that does not increase distances but is not a contraction, and state what its fixed points show.

What You'll Learn