ALTERNATIVE APPROACHES TO PROOFS OF CONTRACTION MAPPING FIXED POINT THEOREMS

James E. Joseph and Myung H. Kwack

While preparing a lecture on Banach’s Contraction Mapping Theorem for a classroom presentation to a group of mathematics students in elementary real analysis, we discovered elegant alternative proofs of the theorem and some of its generalizations and variations. The approaches to these proofs are more in the nature of ones which an undergraduate mathematics major might attempt while studying complete metric spaces if asked to produce a proof of Banach’s theorem before having seen the ingenious proof given by Banach.

In [1], Banach proved the celebrated Contraction Mapping Theorem.

(1) If (X, d) is a complete metric space and g: X → X is a function satisfying d(g(x), g(y)) ≤ μd(x, y) for all x, y ∈ X and some fixed 0 < μ < 1, then g has a unique fixed point.

Banach showed that for any v ∈ X, the sequence of iterates {g^{n}(v)} is a Cauchy sequence and is therefore convergent to some p ∈ X. By the continuity of g, the subsequence {g^{n+1}(v)} converges to g(p). Thus, g(p) = p. Most contraction mapping type theorems have been established by variations on this technique (see [4,5,6,7,8]).

In [2], Boyd and Wong gave an alternative approach to the proof of (1), using Cantor’s intersection property. Their proof, while not the first to directly utilize the Cantor theorem, was more direct than those previously given (see [7]). We now present another alternative approach. Let I(g) = {d(x, g(x)) : x ∈ X}. We show first that 0 = inf I(g) and then that 0 ∈ I(g).

\underline{Our Proof of (1)}. Let c = inf I(g). If c > 0 we have c/μ > c and an x ∈ X satisfying

d(g(x), g(g(x))) ≤ μd(x, g(x)) < c,

a contradiction. Thus, c = 0. Let {x_{n}} be a sequence in X with d(x_{n}, g(x_{n})) → 0. Then {x_{n}} is a Cauchy sequence since

d(x_{n}, x_{m}) ≤ d(x_{n}, g(x_{n})) + d(g(x_{n}), g(x_{m})) + d(x_{m}, g(x_{m}))

gives

(1 − μ)d(x_{n}, x_{m}) ≤ d(x_{n}g(x_{n})) + d(x_{m}, g(x_{m})).

Thus, there is a p ∈ X with x_{n} → p, and g(x_{n}) → p follows from the fact that d(x_{n}, g(x_{n})) → 0. It follows that d(g(x_{n}), g(p)) ≤ μd(x_{n}, p), so g(x_{n}) → g(p) and g(p) = p. The uniqueness of p follows as usual from the contractive nature of g.

\underline{Remark 1}. One of the useful features of Banach’s proof of the theorem is that

d(g^{n}(v), p) ≤ \frac{μ^{n}}{1 − μ}d(v, g(v)).

We see readily that this feature is captured by our method since for any v ∈ X, we have by induction that

d(g^{n}(v), p) = d(g^{n}(v), g^{n}(p)) ≤ μ^{n}d(v, p) ≤ \frac{μ^{n}}{1 − μ}d(v, g(v)).

As another application of this method, we present an alternative proof of the following theorem due to Fisher [5].

(2) If g is a mapping of a complete metric space (X, d) into itself satisfying the condition

d(g(x), g(y)) ≤ μ[d(x, g(y)) + d(y, g(x))]

for all x, y ∈ X and some 0 ≤ μ < 1/2, then g has a unique fixed point.

\underline{Our Proof of (2)}. Let c = inf I(g) and suppose 0 < μ. If c > 0 then ((1 − μ)/μ)c > c since μ < 1/2; so there is an x ∈ X satisfying

d(g(x), g^{2}(x)) ≤ \frac{μ}{1 − μ}d(x, g(x)) < c.

Hence, c = 0 and d(x_{n}, g(x_{n})) → 0 for some sequence {x_{n}} in X. Such a sequence satisfies

\begin{aligned}d(x_{n}, x_{m}) & ≤ d(x_{n}, g(x_{n})) + d(g(x_{n}), g(x_{m})) + d(g(x_{m}), x_{m}) \\ & ≤ \frac{1 + μ}{1 − 2μ}[d(x_{n}, g(x_{n})) + d(x_{m}, g(x_{m}))]. \end{aligned}

Hence, {x_{n}} is a Cauchy sequence. Choose p ∈ X with x_{n} → p. Then g(x_{n}) → p since d(x_{n}, g(x_{n})) → 0. Since

d(g(x_{n}), g(p)) ≤ μ[d(p, g(x_{n})) + d(x_{n}, g(p))]

we obtain d(p, g(p)) ≤ μd(p, g(p)) and g(p) = p.

\underline{Remark 2}. An analysis of the proof of (2) shows that any sequence \{x_{n}\} in X with d(x_{n}, g(x_{n})) → 0 must converge to the fixed point. We observe that if v ∈ X and x_{n} = g^{n−1}(v) it follows by induction that

d(x_{n}, g(x_{n})) ≤ (\frac{μ}{1 − μ})^{n−1}d(v, g(v)),

so the sequence of iterates of any point converges to the fixed point.

\underline{Remark 3}. If p is the fixed point assured in (2) and \{x_{n}\} is any sequence in X, then

\begin{aligned}d(x_{n}, p)) & ≤ d(x_{n}, g(x_{n})) + d(g(x_{n}), g(p)) \\ & ≤ \frac{1 + μ}{1 − 2μ}d(x_{n}, g(x_{n})). \end{aligned}

Therefore, from Remark 2, if v ∈ X and x_{n} = g^{n−1}(v) it follows that

d(x_{n}, p) ≤ \frac{1 + μ}{1 − 2μ}(\frac{μ}{1 − μ})^{n−1}d(v, g(v)),

which gives an estimate for the rate of convergence of the iterates of the point v to the fixed point.

\underline{Remark 4}. We observe that a consequence of (2) is that if (X, d) is a complete metric space and g: X → X is a function satisfying d(g(x), g(y)) ≤ μd(x, y) for all x, y ∈ X and some fixed 0 < μ < 1/3, then g has a unique fixed point. This follows from

\begin{aligned}d(g(x), g(y)) & ≤ μ[d(x, g(y)) + d(g(x), g(y)) + d(y, g(x))] \\ & ≤ \frac{μ}{1 − μ}[d(x, g(y)) + d(y, g(x))], \end{aligned}

and (μ/(1 − μ)) < 1/2.

Our next illustration of this method is a proof of a common generalization of (1) and (2) which is due to Hardy and Rogers [6].

(3) Let (X, d) be a complete metric space and let g be a self mapping of X satisfying the following condition for all x, y ∈ X and fixed nonnegative a, b, c, e, f with a + b + c + e + f < 1:

d(g(x), g(y)) ≤ ad(x, g(x)) + bd(y, g(y)) + cd(x, g(y)) + ed(y, g(x)) + fd(x, y).

Then g has a unique fixed point p and, for each v ∈ X, g^{n}(v) → p.

\underline{Our Proof of (3)}. Let q = inf I(g). By the lemma in [6] there is a μ < 1 satisfying

d(g(x), g^{2}(x)) ≤ μd(x, g(x))

for all x ∈ X. Thus, q = 0. There is a sequence {x_{n}} in X with d(x_{n}, g(x_{n})) → 0. We see that {x_{n}} is a Cauchy sequence since

[1 − (c + e + f)]d(x_{n}, x_{m}) ≤ (1 + a + e)d(x_{n}, g(x_{n})) + (1 + b + c)d(x_{m}, g(x_{m})).

Let p ∈ X satisfy x_{n} → p. Then g(x_{n}) → p and g(p) = p since

\begin{aligned}d(g(x_{n}), g(p)) & ≤ ad(x_{n}, g(x_{n})) + bd(p, g(p)) + cd(x_{n}, p) \\ & + cd(p, g(p)) + ed(x_{n}, p) + ed(p, g(p)) + fd(x_{n}, p), \end{aligned}

which gives

d(p, g(p)) ≤ (b + c)d(p, g(p)).

The uniqueness of p is readily established. It is seen from the argument above that if {x_{n}} is any sequence in X with d(x_{n}, g(x_{n})) → 0, we have x_{n} → p; since

d(g^{n}(v), g^{n+1}(v)) ≤ μ^{n}d(v, g(v))

for any v ∈ X, it follows that g^{n}(v) → p. Also, we observe that if p is the fixed point and d(x_{n}, g(x_{n})) → 0, we have

[1 − (c + e + f)]d(x_{n}, p) ≤ (1 + a + e)d(x_{n}, g(x_{n})),

so

\begin{aligned}d(g(x_{n}), p) & ≤ \frac{1 + a + e}{1 − (c + e + f)}d(g^{n}(v), g^{n+1}(v)) \\ & ≤ \frac{1 + a + e}{1 − (c + e + f)}μ^{n}d(v, g(v)). \end{aligned}

This furnishes an estimate for the rate of convergence of the iterates of a point in the space.

\underline{Remark 5}. An alternative proof of a theorem of Edelstein [4] concerning contraction mappings on ϵ–chainable spaces may be obtained by a slight modification of the method employed above.

For our final demonstration of alternative proofs we produce two proofs of the following theorem on common fixed points, a result due to Kannan [7]. The first uses the ideas employed above in the proofs of (1), (2), (3), and the second uses the Cantor Intersection Property.

(4) If (X, d) is a complete metric space and g, h: X → X are functions satisfying

d(g(x), h(y)) ≤ μ[d(x, g(x)) + d(y, h(y))]

for all x, y ∈ X and some 0 < μ < 1/2, then g and h have a unique common fixed point.

\underline{Our First Proof of (4)}. Let c = inf(I(g) ∪ I(h)). Then c = inf I(g) or c = inf I(h). We exhaust the possibilities.

\underline{Case 1}. c = inf I(g). If c ≠ 0 then ((1 − μ)/μ)c > c and there is an x ∈ X such that d(x, g(x)) < ((1 − μ)/μ)c. For such an x we have

d(g(x), h(g(x)) ≤ \frac{μ}{1 − μ}d(x, g(x)) < c,

a contradiction. Let {x_{n}} be a sequence in X such that d(x_{n}, g(x_{n})) → 0. Then

d(x_{n}, h(x_{n})) ≤ d(x_{n}, g(x_{n})) + d(g(x_{n}), h(x_{n}))

≤ (1 + μ)d(x_{n}, g(x_{n})) + μd(x_{n}, h(x_{n}))

≤ \frac{1 + μ}{1 − μ}d(x_{n}, g(x_{n})).

Hence, d(x_{n}, h(x_{n})) → 0. We see that {x_{n}} is a Cauchy sequence from the fact that

d(x_{n}, x_{m}) ≤ (1 + μ)[d(x_{n}, g(x_{n})) + d(x_{m}, h(x_{m}))].

Let x_{n} → p. Then

(1 − μ)d(g(p), p) ≤ (1 + μ)d(h(x_{n}), x_{n}) + d(x_{n}, p),

so g(p) = p. To see that h(p) = p note that

(1 − μ)d(h(p), p) ≤ (1 + μ)d(g(x_{n}), x_{n}) + d(x_{n}, p).

\underline{Case 2}. c = inf I(h). Entirely similar to Case 1.

To effect our second proof of (4) we utilize the following well–known notions and properties of metric spaces (see [3]).

(a) In a metric space, the diameter of a nonempty subset A (sup{d(x, y) : x, y ∈ A\}) is the same as the diameter of the closure \overline{A}. We denote the diameter of A by δ(A).

(b) A metric space is complete if and only if ∩F_{n} is a singleton set for every decreasing sequence {F_{n}} of nonempty closed subsets of the space with δ(F_{n}) → 0.

For convenience we adopt the following additional notations. If (X, d) is a metric space and g : X → X is a function we will denote the graph of g in X × X by G(g), and will denote by e the distance function induced on X × X by d (e((x, y), (u, v)) = d(x, u) + d(y, v)). With this metric, X × X is complete when X is complete.

\underline{Our Second Proof of (4)}. Let c = inf(I(g) ∪ I(h)). Then c ≥ 0, and if c > 0 then ((1 − μ)/μ)c > c since μ < 1/2. Hence, there is an x ∈ X satisfying either (i) d(x, g(x)) < ((1 − μ)/μ)c > c

or (ii) d(x, h(x)) < ((1 − μ)/μ)c. If x satisfies (i) then

d(g(x), h(g(x))) ≤ \frac{μ}{1 − μ}d(x, g(x)) < c.

If x satisfies (ii) then

d(h(x), g(h(x))) ≤ \frac{μ}{1 − μ}d(x, h(x)) < c.

Consequently, c ≠ inf(I(g) ∪ I(h)). Hence, c = 0. For each positive integer n let

F_{n} = d^{−1}([0, 1/n]) ∩ (G(g) ∪ G(h)).

Then \overline{F}_{n} ≠ ∅ and \overline{F}_{n+1} ⊂ \overline{F}_{n}. We will complete the proof by distinguishing two cases.

\underline{Case 1}. (x, g(x)), (y, h(y)) ∈ F_{n}. Then

e((x, g(x)), (y, h(y))) = d(x, y) + d(g(x), h(y))

≤ d(x, g(x)) + d(g(x), h(y)) + d(h(y), y) + d(g(x), h(y)) ≤ d(x, g(x)) + 2μ[d(x, g(x)) + d(h(y), y)] + d(h(y), y)

≤ (1 + 2μ)[d(x, g(x)) + d(h(y), y)] ≤ (1 + 2μ)\frac{2}{n}.

\underline{Case 2}. (x, g(x)), (y, g(y)) ∈ F_{n}. Then (g(x), h(g(x)) ∈ F_{n}, so

\begin{aligned}e((x, g(x)), (y, g(y))) & ≤ e((x, g(x)), (g(x), h(g(x))) + e((g(x), h(g(x)))), (y, g(y))) \\ & ≤ (1 + 2μ)\frac{4}{n} \end{aligned}

from Case 1. Hence, δ(\overline{F}_{n}) = δ(F_{n}) → 0, and ∩\overline{F}_{n} = \{(x, y)\}; d(x, y) ∈ [0, 1/n] for each n so x = y. If (x_{k}, g(x_{k})) → (x, x), then

d(g(x_{k}), h(x)) ≤ μ[d(x_{k}, g(x_{k})) + d(x, h(x))],

so

d(x, h(x)) ≤ μd(x, h(x))

and h(x) = x. Also

d(x, g(x)) = d(h(x), g(x)) ≤ μd(x, g(x))

and g(x) = x. A similar argument gives g(x) = h(x) = x if (x_{k}, h(x_{k})) → (x, x). We conclude with two exercises for the reader.

\underline{Exercise 1}. Give a proof of Banach’s Contraction Mapping Theorem using the Cantor Intersection Theorem.

\underline{Exercise 2}. Give a proof of (2) using the Cantor Intersection Theorem.

\underline{References}

1. S. Banach, “Sur les Operations dan les Ensembles Abstraite et leur Application aux Equations Integrales,” Fund. Math., 3 (1922), 133–181.

2. D. W. Boyd and J. S. W. Wong, “Another Proof of the Contraction Mapping Theorem,” Canad. Math. Bull., 11 (1968), 605–606.

3. J. Dugundji, Topology, Allyn & Bacon, Inc., Boston, Mass., 1966.

4. M. Edelstein, “An Extension of Banach’s Contraction Principle,” Proc. Amer. Math. Soc., 12 (1961), 7–10.

5. B. Fisher, “A Fixed Point Theorem,” Math. Mag., 48 (1975), 223–225.

6. G. E. Hardy and T. D. Rogers, “A Generalization of a Fixed Point Theorem of Reich,” Canad. Math. Bull., 16 (1973), 201–206.

7. R. Kannan, “Some Results on Fixed Points,” Bull. Cal. Math., 60 (1968), 71– 76.

8. I. I. Kolodner, “On the Proof of the Contraction Mapping Theorem,” Amer. Math. Monthly, 74 (1967), 1212–1213.

James E. Joseph Department of Mathematics Howard University Washington, D.C. 20059 email: jjoseph@scs.howard.edu

Myung H. Kwack Department of Mathematics Howard University Washington, D.C. 20059