Chapter 1

CONTRACTION MAPPINGS AND EXTENSIONS

W. A. Kirk

Department of Mathematics The University of Iowa Iowa City, IA 52242-1419 USA

kirk@math.uiowa.edu

Keywords: Contraction mappings, fixed points, Picard iterates

1. Introduction

A complete survey of all that has been written about contraction mappings would appear to be nearly impossible, and perhaps not really useful. In particular the wealth of applications of Banach’s contraction mapping principle is astonishingly diverse. We only attempt to touch on some of the high points of this profound and seminal development in metric fixed point theory.

The origins of metric contraction principles and, ergo, metric fixed point theory itself, rest in the method of successive approximations for proving existence and uniqueness of solutions of differential equations. This method is associated with the names of such celebrated nineteenth century mathematicians as Cauchy, Liouville, Lipschitz, Peano, and, especially, Picard. In fact the precursors of the fixed point theoretic approach are explicit in the work of Picard. However it is the Polish mathematician Stefan Banach who is credited with placing the ideas underlying the method into an abstract framework suitable for broad applications well beyond the scope of elementary differential and integral equations. Accordingly we take Banach’s formulation as our point of departure in Section 2. It is remarkable in its simplicity, yet it is perhaps the most widely applied fixed point theorem in all of analysis. This is because the contractive condition on the mapping is easy to test and because it requires only the structure of a complete metric space for its setting.

The key ingredients of the Contraction Mapping Principle as it first appeared in Banach’s 1922 thesis [3] are these. (M, d) is a complete metric space and T : M → M is a contraction mapping. Thus there exists a constant k < 1 such that

d (T (x) , T (y)) ≤ kd (x, y)

for each x, y ∈ M. From this one draws three conclusions:

(i) T has a unique fixed point, say x_{0}.

(ii) For each x ∈ M the Picard sequence {T^{n} (x)} converges to x_{0}.

(iii) The convergence is uniform if M is bounded.

In fact condition (iii) can be put in much more explicit form in terms of error estimates.

(iii)_{1} d(T^{n}(x), x_{0}) ≤ \frac{k^{n}}{1 − k} d (x, T (x)) for each x ∈ M and n ≥ 1;

(iii)_{2} d (T^{n+1} (x) , x_{0}) ≤ \frac{k}{1 − k} d (T^{n+1} (x) , T^{n} (x)) for each x ∈ M and n ≥ 1.

In particular, there is an explicit rate of convergence:

(iv) d (T^{n+1} (x) , x_{0}) ≤ kd (T^{n} (x) , x_{0}) .

A primary early example of an extension of Banach’s principle is a theorem of Caccioppoli [16] which asserts that the Picard iterates of a mapping T converge in a complete metric space M provided for each n ≥ 1, there exists a constant c_{n} such that

d (T^{n} (x) , T^{n} (y)) ≤ c_{n}d (x, y)

for all x, y ∈ M, where ∑_{n=1}^{∞} c_{n} < ∞.

The Contraction Mapping Principle has seen many other extensions particularly to mappings for which conclusions (i) and (ii) hold. In many of these instances (especially ones which reduce to Banach’s principle under an appropriate renorming) it is possible to obtain (iii) as well. We give an overview of these facts below. We begin with an explicit proof of Banach’s theorem (one of many) along with one of its canonical applications. We then take up many of the extensions. We conclude with a brief discussion of converses of Banach’s theorem. Many other parts of this volume are devoted to the limiting case k = 1, where in general it is possible to conclude at most that T has a (not necessarily unique) fixed point.

Before proceeding we turn to a simple example to illustrate the usefulness of the contraction mapping principle. Consider the Volterra integral equation

u (x) = f (x) + ∫_{0}^{x} F (x, y) u (y) dy,  (1.1)

where f and the kernel F are defined and continuous on, respectively, [0, a] and [0, a] × [0, a] . By employing the standard method of successive approximations it is possible to show that 1.1 has a unique continuous solution for any F. On the other hand, if the operator T : C [0, a] → C [0, a] is defined by setting

T (u (x)) = f (x) + ∫_{0}^{x} F (x, y) u (y) dy,  (1.2)

then it is easy to see that for u, v ∈ C [0, a]

∥T (u) − T (v)∥ ≤ aK ∥u − v∥

where K = sup_{0≤x,y≤a} |F (x, y)| and ∥·∥ is the usual supremum norm on C [0, a] . Banach’s contraction principle thus immediately yields a unique solution (with convergence of successive approximations) on any interval for which aK < 1. The problem is that in order to obtain a solution one must either restrict the size of the interval [0, a] or the magnitude of the kernel F. This is not serious since in the first instance standard continuation arguments can then be applied to extend the solution.

On the other hand, A. Bielecki [6] discovered another way to remedy this ‘problem’. By assigning a new norm ∥·∥_{λ} , λ > 0, to C [0, a] as follows:

∥u∥_{λ} = sup_{0≤x≤a} [exp (−λx) |u (x)|] ,  (1.3)

it is possible to show that for all u, v ∈ C [0, a] ,

∥T (u) − T (v)∥_{λ} ≤ \frac{K}{λ} ∥u − v∥_{λ} ,

where K is defined as above. (For details, see e.g., [39].) It is then clear that for λ sufficiently large T is indeed a contraction mapping on the Banach space (C [0, a] , ∥·∥_{λ}) . A direct application of the contraction mapping principle now yields the desired solution.

2. The contraction mapping principle

Let (M, d) be a metric space. A mapping T : M → M is said to be lipschitzian if there is a constant k ≥ 0 such that for all x, y ∈ M

d(T (x), T (y)) ≤ k d(x, y).  (2.1)

The smallest number k for which 2.1 holds is called the Lipschitz constant of T.

Definition 2.1 A lipschitzian mapping T : M → M with Lipschitz constant k < 1 is said to be a contraction mapping.

Theorem 2.2 (Banach’s Contraction Mapping Principle). Let (M, d) be a complete metric space and let T : M → M be a contraction. Then T has a unique fixed point x_{0}. Moreover, for each x ∈ M,

lim_{n→∞} T^{n} (x) = x_{0}

and in fact for each x ∈ M,

d (T^{n}(x), x_{0}) ≤ \frac{k^{n}}{1 − k} d (x, T (x)) , n = 1, 2, · · ·.

Proof. Since T is a contraction mapping we know that for each x ∈ M,

d(T (x), T^{2}(x)) ≤ k d(x, T (x)).

Adding d(x, T (x)) to both sides of the above yields

d(x, T (x)) + d(T (x), T^{2}(x)) ≤ d(x, T (x)) + k d(x, T (x))

which can be rewritten

d(x, T (x)) − k d(x, T (x)) ≤ d(x, T (x)) − d(T (x), T^{2}(x)).

This in turn is equivalent to

d(x, T (x)) ≤ (1 − k)^{−1}[d(x, T (x)) − d(T (x), T^{2}(x))].

Now define the function φ : M → ℝ^{+} by setting φ(x) = (1−k)^{−1}d(x, T (x)), for x ∈ M. This gives us the basic inequality

d(x, T (x)) ≤ φ(x) − φ(T (x)), x ∈ M.

Therefore if we fix x ∈ M and take m, n ∈ ℕ with n < m, we obtain

d(T^{n}(x), T^{m+1}(x)) ≤ ∑_{i=n}^{m} d(T^{i}(x), T^{i+1}(x)) ≤ φ(T^{n}(x)) − φ(T^{m+1}(x)).

(Notice that the last inequality comes from cancellation in the telescoping sum.) In particular by taking n = 1 and letting m → ∞ we conclude that

∑_{i=1}^{∞} d(T^{i}(x), T^{i+1}(x)) ≤ φ(T (x)) < ∞.

This implies that {T^{n}(x)} is a Cauchy sequence. Since M is complete there exists x_{0} ∈ M such that

lim_{n→∞} T^{n}(x) = x_{0}

and since T is continuous

x_{0} = lim_{n→∞} T^{n}(x) = lim_{n→∞} T^{n+1}(x) = T (x_{0}).

Thus x_{0} is a fixed point of T.

In order to see that x_{0} is the only fixed point of T, suppose T (y) = y. Then by what we have just shown

x_{0} = lim_{n→∞} T^{n}(y) = y.

Returning to the inequality

d(T^{n}(x), T^{m+1}(x)) ≤ φ(T^{n}(x)) − φ(T^{m+1}(x)),

upon letting m → ∞ we see that

d(T^{n}(x), x_{0}) ≤ φ(T^{n}(x)) = (1 − k)^{−1}d(T^{n}(x), T^{n+1}(x)).

Since (1 − k)^{−1}d(T^{n}(x), T^{n+1}(x)) ≤ \frac{k^{n}}{1 − k} d(x, T (x)) we obtain

d(T^{n}(x), x_{0}) ≤ \frac{k^{n}}{1 − k} d(x, T (x)).

This provides an estimate on the rate of convergence for the sequence {T^{n}(x)} which depends only on d (x, T (x)) . ■

While the above estimate is sharp, in practical situations it might be necessary to approximate the values of T^{n}(x). Here a natural question arises. If one replaces the sequence {T^{n}(x)} with {y_{n}} where y_{0} = x and y_{n+1} is ‘approximately’ T (y_{n}), then under what conditions will it still be the case that lim_{n→∞} y_{n} = x_{0}? The following positive answer to this question was given by Ostrowski in [87]. (For a recent generalization of this result as well as related literature, see [52].)

Theorem 2.3 Let (M, d) be a complete metric space, let T : M → M be a contraction mapping with Lipschitz constant k ∈ (0, 1) , and suppose x_{0} ∈ M is the fixed point of T. Let {ε_{n}} be a sequence of positive numbers for which lim_{n→∞} ε_{n} = 0, let y_{0} ∈ M, and suppose {y_{n}} ⊂ M satisfies

d (y_{n+1}, T (y_{n})) ≤ ε_{n}, n = 1, 2, · · ·.

Then lim_{n→∞} y_{n} = x_{0}.

Proof. Let y_{0} = x and observe that

d(T^{m+1}(x), y_{m+1}) ≤ d(T (T^{m}(x)), T (y_{m})) + d(T (y_{m}), y_{m+1})

≤ kd(T^{m}(x), y_{m}) + ϵ_{m}

≤ ∑_{i=0}^{m} k^{m−i}ϵ_{i}.

Thus

d(y_{m+1}, x_{0}) ≤ d(y_{m+1}, T^{m+1}(x)) + d(T^{m+1}(x), x_{0})

≤ ∑_{i=0}^{m} k^{m−i}ϵ_{i} + d(T^{m+1}(x), x_{0}).

Now let ϵ > 0. Since lim_{n→∞} ϵ_{n} = 0 there exists N ∈ ℕ such that for m ≥ N, ϵ_{m} ≤ ϵ. Then

∑_{i=0}^{m} k^{m−i}ϵ_{i} = ∑_{i=0}^{N} k^{m−i}ϵ_{i} + ∑_{i=N+1}^{m} k^{m−i}ϵ_{i}

≤ k^{m−N} ∑_{i=0}^{N} k^{N−i}ϵ_{i} + ϵ ∑_{i=N+1}^{m} k^{m−i}.

Hence

lim_{m→∞} ∑_{i=0}^{m} k^{m−i}ϵ_{i} ≤ ϵ (\frac{k^{N+1}}{1 − k} ) .

Since ϵ > 0 is arbitrary, and since lim_{m→∞} d(T^{m+1}(x), x_{0}) = 0 we conclude that lim_{m→∞} y_{m+1} = x_{0}. ■

The following theorem is noteworthy in that the mapping T is not even assumed to be continuous!

Theorem 2.4 Suppose (M, d) is a complete metric space and suppose T : M → M is a mapping for which T^{N} is a contraction mapping for some positive integer N. Then T has a unique fixed point.

Proof. By Banach’s Theorem T^{N} has a unique fixed point x. However,

T^{N+1}(x) = T (T^{N}(x)) = T (x),

so T (x) is also a fixed point of T^{N}. Since the fixed point of T^{N} is unique, it must be the case that T (x) = x. Also, if T (y) = y then T^{N}(y) = y proving (again by uniqueness) that y = x. ■

In considering lipschitzian mappings an obvious question that arises immediately is whether it is possible to weaken the contraction assumption even a little bit and still obtain the existence of fixed points. In a broad sense the answer is no and here is an example. Begin with the complete metric space C[0, 1] and consider the closed subspace M of C[0, 1] consisting of those mappings f ∈ C[0, 1] for which f(1) = 1. Since M is a closed subspace of a complete metric space, M is itself complete. Now define T : M → M by taking T (f) to be the function in M obtained by setting

T (f)(t) = tf(t) t ∈ [0, 1].

If f, g ∈ M then |T (f) − T (g)| ∈ C[0, 1], so by the Maximum Value Theorem |T (f) − T (g)| attains its maximum value at some point t_{0} ∈ [0, 1]. We then have

d(T (f), T (g)) = sup_{t∈[0,1]} |T (f)(t) − T (g)(t)| = t_{0} |f(t_{0}) − g(t_{0})| ≤ d(f, g).

But if f ≠ g it must be the cast that f(t) ≠ g(t) for some t ∈ [0, 1] and since f(1) = g(1) = 1, this in turn implies t_{0} < 1. Therefore, if f, g ∈ M and f ≠ g,

d(T (f), T (g)) < d(f, g).

Now suppose T (f) = f for f ∈ M. This implies that for each t ∈ [0, 1], f(t) = tf(t). This implies that f(t) = 0 for all t ∈ [0, 1). On the other hand, f(1) = 1. This contradicts the assumption that f is continuous, so T can have no fixed point in M. Therefore the Banach Contraction Mapping principle does not even extend to the following slightly more general class of mappings.

Definition 2.5 A mapping T : M → M is said to be contractive if

d(T (x), T (y)) < d(x, y)

for each x, y ∈ M with x ≠ y.

The next obvious question is whether there is a meaningful fixed point result for the contractive mappings. The answer is yes, but the class of spaces to which it applies is much more restrictive.

Theorem 2.6 Let (M, d) be a compact metric space and let T : M → M be a contractive mapping. Then T has a unique fixed point x_{0}, and moreover, for each x ∈ M, lim_{n→∞} T^{n}(x) = x_{0}.

Proof. The existence of a fixed point for T is easy. Introduce the mapping ψ : M → ℝ^{+} by setting

ψ(x) = d(x, T (x)), x ∈ M.

Then ψ is continuous and bounded below, so ψ assumes its minimum value at some point x_{0} ∈ M. Since x_{0} ≠ T (x_{0}) implies

ψ(T (x_{0})) = d(T (x_{0}), T^{2}(x_{0})) < d(x_{0}, T (x_{0})) = ψ(x_{0})

it must be the case that x_{0} = T (x_{0}).

Now let x ∈ M and consider the sequence {d(T^{n}(x), x_{0})}. If T^{n}(x) ≠ x_{0},

d(T^{n+1}(x), x_{0}) = d(T^{n+1}(x), T (x_{0})) < d(T^{n}(x), x_{0}),

so {d(T^{n}(x), x_{0})} is strictly decreasing (until perhaps it reaches x_{0}). Consequently the limit

r = lim_{n→∞} d(T^{n}(x), x_{0})

exists and r ≥ 0. Also, since M is compact, the sequence {T^{n}(x)} has a convergent subsequence {T^{n_{k}}(x)}, say lim_{k→∞} T^{n_{k}}(x) = z ∈ M. Since {T^{n}(x)} is decreasing,

r = d(z, x_{0}) = lim_{k→∞} d(T^{n_{k}}(x), x_{0}) = lim_{k→∞} d(T^{n_{k}+1}(x), x_{0}) = d(T (z), x_{0}).

But if z ≠ x_{0} then d(T (z), x_{0}) = d(T (z), T (x_{0})) < d (z, x_{0}) . This proves that any convergent subsequence of {T^{n}(x)} converges to x_{0}, so it must be the case that

lim_{n→∞} T^{n}(x) = x_{0}.

■

3. Further extensions of Banach’s principle

The strength of the Contraction Mapping Principle lies in the fact that the underlying space is quite general (complete metric) while the conclusion is very strong, including even error estimates. There have been numerous extensions of a milder form of Banach’s principle which asks only that the fixed point be unique and that the Picard iterates of the mapping always converge to this fixed point.. We discuss some of the more well known of these, especially from a historical perspective, in this section.

The first such generalization to receive significant attention is the following result of Rakotch [98].

Theorem 3.1 Let M be a complete metric space and suppose f : M → M satisfies

d (f (x) , f (y)) ≤ α (d (x, y)) d (x, y) for each x, y ∈ M,

where α : ℝ^{+} → [0, 1) is monotonically decreasing. Then f has a unique fixed point, x̄, and {f^{n} (x)} converges to x̄ for each x ∈ M.

Subsequently Boyd and Wong [8] obtained a more general result. In this theorem it is assumed that ψ : ℝ^{+} → ℝ^{+} is upper semicontinuous from the right (that is,

r_{n} ↓ r ≥ 0 ⇒ lim sup_{n→∞}ψ(r_{n}) ≤ ψ(r)).

Theorem 3.2 Let M be a complete metric space and suppose f : M → M satisfies

d (f (x) , f (y)) ≤ ψ (d (x, y)) for each x, y ∈ M,

where ψ : ℝ^{+} → [0, ∞) is upper semi-continuous from the right and satisfies 0 ≤ ψ (t) < t for t > 0. Then f has a unique fixed point, x̄, and {f^{n} (x)} converges to x̄ for each x ∈ M.

Proof. Fix x ∈ M and let x_{n} = f^{n}(x), n = 1, 2, · · ·. We break the argument into two steps.

\underline{Step} 1. lim_{n→∞} d(x_{n}, x_{n+1}) = 0.

Proof. Since f is contractive the sequence {d(x_{n}, x_{n+1})} is monotone decreasing and bounded below so lim_{n→∞} d(x_{n}, x_{n+1}) = r ≥ 0. Assume r > 0. Then

d(x_{n+1}, x_{n+2}) ≤ ψ (d (x_{n}, x_{n+1})) ⇒ r ≤ ψ (r) ⇒ r = 0.

\underline{Step} 2. \{x_{n}\} is a Cauchy sequence.

Proof. Suppose not. Then there exists ε > 0 such that for any k ∈ ℕ, there exist

m_{k} > n_{k} ≥ k

such that

d (x_{m_{k}}, x_{n_{k}}) ≥ ε.  (3.1)

Furthermore, assume that for each k, m_{k} is the smallest number greater than n_{k} for which (3.1) holds. In view of Step 1 there exists k_{0} such that k ≥ k_{0} ⇒ d (x_{k}, x_{k+1}) ≤ ε. For such k we have

ε ≤ d (x_{m_{k}}, x_{n_{k}}) ≤ d (x_{m_{k}}, x_{m_{k}−1}) + d (x_{m_{k}−1}, x_{n_{k}})
≤ d (x_{m_{k}}, x_{m_{k}−1}) + ε ≤ d (x_{k}, x_{k−1}) + ε

This proves lim_{k→∞} d (x_{m_{k}}, x_{n_{k}}) = ε. On the other hand,

d (x_{m_{k}}, x_{n_{k}}) ≤ d (x_{m_{k}}, x_{m_{k}+1}) + d (x_{m_{k}+1}, x_{n_{k}+1}) + d (x_{n_{k}+1}, x_{n_{k}})
≤ 2d (x_{k}, x_{k−1}) + ψ (d (x_{m_{k}}, x_{n_{k}})) .

It follows that ε ≤ ψ (ε) — a contradiction.

The proof is completed by observing that since {f^{n}(x)} is a Cauchy sequence and M is complete, lim_{n→∞}f^{n}(x) = z ∈ M. Since f is continuous, f(z) = z. Uniqueness of z follows from the contractive condition. ■

REMARK. Boyd and Wong also show in [8] that if the space M is metrically convex, then the upper semicontinuity assumption on ψ can be dropped. Matkowski has extended this fact even further in [77] by showing that it suffices to assume that ψ is continuous at 0 and that there exists a sequence t_{n} ↓ 0 for which ψ (t_{n}) < t_{n}.

Since it is the explicit control over the error term that contributes so much to the wide-spread usefulness of Banach’s principle, the following variant of the Boyd-Wong theorem due to Browder [11] is also of interest.

Theorem 3.3 Let X be a complete metric space and M a bounded subset of X. Suppose f : M → M satisfies

d (f (x) , f (y)) ≤ ψ (d (x, y)) for each x, y ∈ M,

where ψ : [0, ∞) → [0, ∞) is monotone nondecreasing and continuous from the right, such that ψ (t) < t for all t > 0. Then there is a unique element x̄ ∈ M such that {f^{n} (x)} converges to x̄ for each x ∈ M. Moreover, if d_{0} is the diameter of M, then

d (f^{n} (x) , x̄) ≤ ψ^{n} (d_{0})

and ψ^{n} (d_{0}) → 0 as n → ∞.

Another variant is due to Matkowski [76]. In this result the continuity condition on ψ is replaced with another condition.

Theorem 3.4 Let M be a complete metric space and suppose f : M → M satisfies

d (f (x) , f (y)) ≤ ψ (d (x, y)) for each x, y ∈ M,

where ψ : (0, ∞) → (0, ∞) is monotone nondecreasing and satisfies lim_{n→∞} ψ^{n} (t) = 0 for t > 0. Then f has a unique fixed point x̄, and lim_{n→∞}d (f^{n} (x) , x̄) = 0 for every x ∈ M.

Proof. Fix x ∈ M and let x_{n} = f^{n}(x), n = 1, 2, · · ·. As before we break the argument into two steps.

\underline{Step} 1. lim_{n→∞} d(x_{n}, x_{n+1}) = 0.

Proof. 0 ≤ lim sup_{n→∞}d (x_{n}, x_{n+1}) ≤ lim sup_{n→∞}ψ^{n} (d (x, x_{1})) = 0.

\underline{Step} 2. \{x_{n}\} is a Cauchy sequence.

Proof. Since ψ^{n} (f) → 0 for f > 0, ψ (ε) < ε for any ε > 0. In view of Step 1 given any ε > 0 it is possible to choose n so that

d (x_{n+1}, x_{n}) ≤ ε − ψ (ε) .

Now let

K (x_{n}, ε) = {x ∈ M : d (x, x_{n}) ≤ ε} .

Then if z ∈ K (x_{n}, ε),

d (f (z) , x_{n}) ≤ d (f (z) , f (x_{n})) + d (f (x_{n}) , x_{n})
≤ ψ (d (z, x_{n})) + d (x_{n+1}, x_{n})
≤ ψ (ε) + (ε − ψ (ε)) = ε.

Therefore f : K (x_{n}, ε) → K (x_{n}, ε) and it follows that d (x_{m}, x_{n}) ≤ ε for all m ≥ n. This completes Step 2.

The conclusion of the proof follows as in Theorem 3.2. ■

A somewhat different approach which has also received substantial attention is the following formulation due to Meir and Keeler [78].

Theorem 3.5 Let (M, d) be a complete metric space and suppose f : M → M satisfies the condition: Given ε > 0 there exists δ > 0 such that

ε ≤ d (x, y) ≤ ε + δ ⇒ d (f (x) , f (y)) < ε.

Then f has a unique fixed point x̄, and lim_{n→∞} f^{n} (x) = x̄ for each x ∈ M.

Clearly the Meir-Keeler condition implies that f is contractive

(x ≠ y ⇒ d (f (x) , f (y)) < d (x, y)).

Thus f is continuous, and if f has a fixed point it must be unique. Also it is easy to see that the Meir-Keeler condition implies d (f^{n} (x) , f^{n+1} (x)) ↓ 0 as n → ∞. It only remains to show that in fact {f^{n} (x)} is a Cauchy sequence and this is easily accomplished by assuming the contrary and obtaining a contradiction.

For a recent variant of the Meir-Keeler theorem in ordered Banach spaces see [22]. Also, following in the spirit of the Boyd-Wong approach, T. C. Lim [70] has recently characterized the Meir-Keeler condition in terms of a function ψ.

Finally we take up a variant of Rakotch’s approach due to Geraghty [38]. In this case we also present the details.

Let S denote the class of those functions α : ℝ^{+} → [0, 1) which satisfy the simple condition α(t_{n}) → 1 ⇒ t_{n} → 0.

Theorem 3.6 Let (M, d) be a complete metric space, let f : M → M, and suppose there exists α ∈ S such that for each x, y ∈ M,

d(f(x), f(y)) ≤ α(d(x, y))d(x, y).

Then f has a unique fixed point z ∈ M, and {f^{n}(x)} converges to z, for each x ∈ M.

Proof. Fix x ∈ M and let x_{n} = f^{n}(x), n = 1, 2, · · ·. Yet again we break the argument into two steps.

\underline{Step} 1. lim_{n→∞} d(x_{n}, x_{n+1}) = 0.

Proof. Since f is contractive the sequence {d(x_{n}, x_{n+1})} is monotone decreasing and bounded below, so lim_{n→∞} d(x_{n}, x_{n+1}) = r ≥ 0. Assume r > 0. Then by the contractive condition

\frac{d(x_{n+1}, x_{n+2})}{d(x_{n}, x_{n+1})} ≤ α(d(x_{n}, x_{n+1})), n = 1, 2, · · ·.

Letting n → ∞ we see that 1 ≤ lim_{n→∞} α(d(x_{n}, x_{n+1})), and since α ∈ S this in turn implies r = 0. This contradiction establishes Step 1.

\underline{Step} 2. \{x_{n}\} is a Cauchy sequence.

Proof. Assume lim sup_{m,n→∞}d(x_{n}, x_{m}) > 0. By the triangle inequality

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

so by the contractive condition

d(x_{n}, x_{m}) ≤ (1 − α(d(x_{n}, x_{m}))^{−1}[d(x_{n}, x_{n+1}) + d(x_{m+1}, x_{m})].

Under the assumption lim sup_{m,n→∞}d(x_{n}, x_{m}) > 0, Step 1 now implies

lim sup_{m,n→∞}(1 − α(d(x_{n}, x_{m}))^{−1} = +∞

from which

lim sup_{m,n→∞}α(d(x_{n}, x_{m})) = 1.

But since α ∈ S this implies lim sup_{m,n→∞}d(x_{n}, x_{m}) = 0 — again a contradiction.

The proof is completed as in the previous results. ■

The key step in proving the existence of a fixed point in each of the proofs just given involved showing that given x ∈ M, {f^{n}(x)} is a Cauchy sequence (and then invoking continuity of f). It is possible to carry this idea much further. First we need some notation. For any mapping F : M → M we use k(F) to denote the Lipschitz constant of F; thus

k(F) = sup\{\frac{d(F (x), F (y))}{d(x, y)} : x, y ∈ M, x ≠ y\}.

Note in particular that if F, G : M → M are two lipschitzian mappings, then

k(F ∘ G) ≤ k(F)k(G).

Now let (M, d) be a complete metric space and suppose T : M → M is lipschitzian. Fix x ∈ M, and let x_{n} = T^{n}(x), n = 1, 2, · · ·. By the triangle inequality, if m > n, then

d(x_{n}, x_{m}) ≤ ∑_{i=n}^{m} d(x_{i}, x_{i+1}).

Consequently {x_{n}} is a Cauchy sequence if

∑_{i=1}^{∞} d(x_{i}, x_{i+1}) < ∞,

and since

d(x_{i}, x_{i+1}) = d(T^{i}(x), T^{i+1}(x)) ≤ k(T^{i})d(x, T (x))

it follows that

∑_{i=1}^{∞} k(T^{i}) < ∞ ⇒ ∑_{i=1}^{∞} d(x_{i}, x_{i+1}) < ∞.

Also

k(T^{m+n}) ≤ k(T^{n})k(T^{m}).

Specifically [k(T^{n})]^{1/n} ≤ k(T) and so

k_{∞}(T) := lim sup_{n→∞} [k(T^{n})]^{1/n}

exists. This is all we really need at this point. However it is possible to say more. Replacing T with T^{p} in [k(T^{n})]^{1/n} ≤ k(T) and taking the pth root of both sides we obtain

[k(T^{pn})]^{1/pn} ≤ [k(T^{p})]^{1/p} , p = 1, 2, · · ·.

Also, a simple calculation shows that

lim_{n→∞} \begin{matrix}[k(T^{n})] & 1/n \\ [k(T^{n+1})] & 1/n+1 \end{matrix} = 1.

These two facts lead to the conclusion:

k_{∞}(T) = lim_{n→∞} [k(T^{n})]^{1/n} = inf{[k(T^{n})]^{1/n} : n = 1, 2, ⋯}.

Now, by the Root Test for convergence of series, if k_{∞}(T) < 1 then ∑_{i=1}^{∞} k(T^{i}) < ∞. This leads to the following theorem.

Theorem 3.7 Let M be a complete metric space and let T : M → M be a lipschitzian mapping for which k_{∞}(T) < 1. Then T has a unique fixed point z ∈ M, and for each x ∈ M the sequence {T^{n}(x)} converges to z.

Proof. In view of what was shown just prior to the statement of the theorem, all that remains is to show that the fixed point of T is unique. However this follows from the fact that if k_{∞}(T) < 1 then for n sufficiently large, k(T^{n}) < 1. ■

There is a point to the previous development. One might ask whether qualitatively, Theorem 3.7 result is stronger than Banach’s contraction principle, and indeed the answer is no. To see this we introduce the concept of equivalent metrics.

Two metrics, ρ and d on a space M are said to be equivalent if there exist positive numbers a and b such that for each x, y ∈ M

ad(x, y) ≤ ρ(x, y) ≤ bd(x, y).

From this it follows that if T : M → M then

k_{d}(T) < ∞ ⇔ k_{ρ}(T) < ∞.

Moreover,

d(T (x), T (y)) ≤ \frac{1}{a}ρ(T (x), T (y)) ≤ \frac{1}{a}k_{ρ}(T)ρ(x, y) ≤ \frac{b}{a}k_{ρ}(T)d(x, y).

This implies k_{d}(T) ≤ \frac{b}{a}k_{ρ}(T). Similarly,

ρ(T (x), T (y)) ≤ bd(T (x), T (y)) ≤ bk_{d}(T)d(x, y) ≤ \frac{b}{a}k_{d}(T)ρ(x, y);

hence k_{ρ}(T) ≤ \frac{b}{a}k_{d}(T). Consequently

\frac{a}{b}k_{ρ}(T) ≤ k_{d}(T) ≤ \frac{b}{a}k_{ρ}(T),

and since lim_{n→∞} (\frac{b}{a})^{1/n} = lim_{n→∞} (\frac{a}{b})^{1/n} = 1 we conclude

lim_{n→∞} [k_{d}(T^{n})]^{1/n} = lim_{n→∞} [k_{ρ}(T^{n})]^{1/n} .

Hence (k_{d})_{∞} (T) = (k_{ρ})_{∞}(T), that is, k_{∞}(T) is the same for all equivalent metrics on M.

Now suppose (M, d) is a complete metric space and let T : M → M be a mapping for which k_{∞}(T) < 1. Then if λ ∈ [0, 1/k_{∞}(T)),

λ^{n}d(T^{n}(x), T^{n}(y)) ≤ λ^{n}k(T^{n})d(x, y)

with

lim_{n→∞} [λ^{n}k(T^{n})]^{1/n} = λk_{∞}(T) < 1.

Therefore

r_{λ}(x, y) := ∑_{n=0}^{∞} λ^{n}d(T^{n}(x), T^{n}(y)) < ∞,

and moreover

d(x, y) ≤ r_{λ}(x, y) ≤ [∑_{n=0}^{∞} λ^{n}k(T^{n})] d(x, y).

This proves that r_{λ} and d are equivalent metrics on M.

Finally, for x, y ∈ M

r_{λ}(T (x), T (y)) = ∑_{n=0}^{∞} λ^{n}d(T^{n+1}(x), T^{n+1}(y))

= (1/λ) ∑_{n=0}^{∞} λ^{n+1}d(T^{n+1}(x), T^{n+1}(y))

= (1/λ) [r_{λ}(x, y) − d(x, y)]

≤ (1/λ)r_{λ}(x, y).

Thus k_{r_{λ}}(T) ≤ \frac{1}{λ} < 1. This proves that T is a contraction mapping on the metric space (M, r_{λ}). Also, since r_{λ} and d are equivalent metrics, (M, r_{λ}) is a complete space. It is now possible to invoke Banach’s original theorem to conclude that T has a unique fixed point x_{0} (with lim_{n→∞} d(T^{n}(x), x_{0}) = 0 for each x ∈ M).

The preceding ideas lead to the following.

Theorem 3.8 Suppose (M, d) is a metric space and suppose T : M → M is a mapping for which (k_{d})_{∞}(T) < 1. Suppose also that T is continuous relative to a metric ρ on M for which (M, ρ) is complete, and suppose ρ(x, y) ≤ d(x, y) for each x, y ∈ M. Then T has a unique fixed point x_{0}, and moreover lim_{n→∞} T^{n}(x) = x_{0} for each x ∈ M.

Proof. There exists a metric d′ on M which is equivalent to d and such that T : (M, d′) → (M, d′) is a contraction mapping. Therefore, for each x ∈ M, {T^{n}(x)} is Cauchy sequence in (M, d′); hence {T^{n}(x)} is a Cauchy sequence in (M, d) and, since ρ ≤ d, {T^{n}(x)} is in fact a Cauchy sequence in (M, ρ) as well. Therefore, relative to ρ, lim_{n→∞} T^{n}(x) = x_{0} for some x_{0} ∈ M and the conclusion follows because T is continuous on (M, ρ). ■

We now turn to a principle of a different kind. In this result the contractive condition is imposed only at the first step. This paves the way for the result discussed in the next section.

Theorem 3.9 Suppose M is a complete metric space and suppose T : M → M is a continuous mapping which satisfies for some φ : M → ℝ^{+},

d(x, T (x)) ≤ φ(x) − φ(T (x)),  x ∈ M.  (*)

Then {T^{n}(x)} converges to a fixed point of T for each x ∈ M.

Proof. This is a piece of the argument used in the proof of Banach’s contraction principle. The condition (*) implies that {φ(T^{n}(x))} is monotone decreasing and hence lim_{n→∞} φ(T^{n}(x)) = r ≥ 0. By the triangle inequality, if m, n ∈ ℕ and m > n then

d(T^{n}(x), T^{m}(x)) ≤ ∑_{i=n}^{m−1} d(T^{i}(x), T^{i+1}(x)) ≤ φ(T^{n}(x)) − φ(T^{m}(x))

so lim_{m,n→∞} d(T^{n}(x), T^{m}(x)) = 0. Since M is complete there exists z ∈ M such that lim_{n→∞} T^{n}(x) = z and by continuity of T, z = T (z). ■

REMARK. In the above result, one can obtain an estimate on the rate of convergence of {T^{n}(x)} by referring back to the inequality

∑_{i=n}^{m−1} d(T^{i}(x), T^{i+1}(x)) ≤ φ(T^{n}(x)) − φ(T^{m}(x)).

This yields

d(T^{n}(x), T^{m}(x)) ≤ φ(T^{n}(x)) − φ(T^{m}(x)),

and if T (z) = z, upon letting m → ∞ one has

d(T^{n}(x), z) ≤ φ(T^{n}(x)) − φ (z) .

FURTHER REMARKS. In [53] Jachymski gives a detailed comparison of the relationship between Theorems 3.2 and 3.4, as well as several related contractive conditions. In particular it is shown that a number of mutually equivalent fixed point principles are methodologically reducible to Matkowski ’s condition of Theorem 3.4, and that Theorem 3.2 of Boyd and Wong essentially improves on Theorem 3.3 of Browder.

4. Caristi’s theorem

We only mention Caristi’s theorem in passing here because the relationship between this theorem and order-theoretic principles is taken up in detail in the article by J. Jachymski elsewhere in this volume. On the other hand it also can be viewed as an extension of the contraction mapping principle.

In view of the fact that continuity of T was essential to the proof of Theorem 3.9 it is remarkable to find that the result remains true without such an assumption if a mild continuity assumption is placed on the mapping φ. This observation is an outgrowth of Caristi’s study [18] of mappings satisfying inwardness conditions. In its original and traditional formulation, Caristi’s theorem stated as follows. (A function φ : M → ℝ is said to be lower semicontinuous at x if for any sequence {x_{n}} ⊂ M,

lim_{n→∞} x_{n} = x ∈ M ⇒ φ (x) ≤ lim inf_{n→∞}φ(x_{n}).)

Theorem 4.1 Let M be a complete metric space, suppose φ : M → ℝ is lower semicontinuous and bounded below, and suppose g : M → M satisfies:

d(x, g(x)) ≤ φ(x) − φ(g(x)), x ∈ M.

Then g has a fixed point.

Shortly after the appearance of Caristi’s Theorem, which actually follows from a variational principle formulated earlier by Ekeland [34], numerous papers were published devoted to various proofs. Caristi’s original proof involved an intricate transfinite induction argument, an argument Wong [123] was able to considerably simplify. One of the shortest proofs is a straightforward Zorn’s Lemma argument (e.g., [10], [61]) based on Brøndsted’s partial order. Proofs which invoke weaker set-theoretic premises were discovered by Browder [12], Brezis-Browder [9], Penot [95], Siegel [110], among others. Numerous papers have been published which are devoted to related and equivalent formulations of the Caristi-Ekeland principle, for example Kasahara [60], Park [90], [91], Takahashi [114]. A proof based solely on the basic axioms of Zermelo and Fraenkel has been given by Mańka [74].

An elegant and direct proof of Caristi’s theorem is found in Deimling [29], § 11. Another elementary and straightforward approach is due to Brezis and Browder [9] via a general principle on ordered sets which itself has a simple mathematical induction proof. A recent paper of Oettli and Théra [85] provides yet another order-theoretic approach to Caristi’s theorem.

We remark that in Caristi’s theorem, the mapping φ above need only be assumed to be lower semicontinuous relative to sequences x_{n} → x ∈ M for which φ (x_{n+1}) ≤ φ (x_{n}) , n ≥ 1.

5. Set-valued contractions

Banach’s Contraction Mapping Principle extends nicely to set-valued mappings, a fact first noticed by S. Nadler [84] (also see [75]). The key idea is the following. If A and B are nonempty closed bounded subsets of a metric space and if x ∈ A, then given ϵ > 0 there must exist a point y ∈ B such that

d(x, y) ≤ H(A, B) + ϵ,

where H(A, B) denotes the Hausdorff distance between A and B. This is because the definition of Hausdorff distance assures that for any μ > 0

A ⊆ N_{ρ+μ}(B)
= {x : dist(x, B) < ρ + μ}

where ρ = H(A, B).

Theorem 5.1 Let (M, d) be a complete metric space, and let 𝔐 be the collection of all nonempty bounded closed subsets of M endowed with the Hausdorff metric H. Suppose T : M → 𝔐 is a contraction mapping in the sense that for some k < 1 :

H(T (x), T (y)) ≤ k d(x, y), x, y ∈ M.

Then there exists a point x ∈ M such that x ∈ T (x).

Proof. Select x_{0} ∈ M and x_{1} ∈ T (x_{0}). By the observation immediately preceding the statement of the theorem there must exist x_{2} ∈ T (x_{1}) such that

d(x_{1}, x_{2}) ≤ H(T (x_{0}), T (x_{1})) + k.

Similarly, there exists x_{3} ∈ T (x_{2}) such that

d(x_{2}, x_{3}) ≤ H(T (x_{1}), T (x_{2})) + k^{2}.

An induction argument yields a sequence {x_{n}} in M with the property that x_{i+1} ∈ T (x_{i}) for each i ∈ ℕ and for which

d(x_{i}, x_{i+1}) ≤ H(T (x_{i−1}), T (x_{i})) + k^{i}
≤ k d(x_{i−1}, x_{i}) + k^{i}
≤ k[H(T (x_{i−2}), T (x_{i−1})) + k^{i−1}] + k^{i}
≤ k^{2} d(x_{i−2}, x_{i−1}) + 2k^{i}
≤ ⋯
≤ k^{i} d(x_{0}, x_{1}) + ik^{i}.

Therefore

∑_{i=0}^{∞} d(x_{i}, x_{i+1}) ≤ d(x_{0}, x_{1}) (∑_{i=0}^{∞} k^{i}) + ∑_{i=0}^{∞} ik^{i} < ∞.

This proves that {x_{n}} is a Cauchy sequence, so since M is complete there exists x ∈ M such that lim_{n→∞} x_{n} = x. Also, since T is continuous,

lim_{n→∞} H(T (x_{n}), T (x)) = 0.

Since x_{n} ∈ T (x_{n−1}),

lim_{n→∞} dist(x_{n}, T (x)) = lim inf_{n→∞}{d(x_{n}, y) : y ∈ T (x)} = 0.

This implies that

inf{d(x, y) : y ∈ T (x)} = 0,

and since T (x) is closed it must be the case that x ∈ T (x). ■

In contrast to Banach’s theorem, the preceding theorem does not assert that the fixed point x is unique. Indeed, it need not be. In [106] an example in ℝ^{2} is given of a multivalued contraction mapping whose values are compact and connected yet the mapping has a disconnected fixed point set. It is also shown in [106] that if x is a fixed point of a multivalued contraction mapping T defined on a closed convex subset of a Banach space and if T (x) is not a singleton, then T always has at least one additional fixed point distinct from x. On the other hand, Ricceri [103] has shown that the fixed point set is an absolute retract if M is a closed and convex subset of a Banach space and T has closed convex values.

There is an interesting stability result (due to T. C. Lim [69]) that holds for set-valued contractions (hence ordinary contractions as well). Such results find applications, for example, in the study of iterated function systems ([19], [35]). We begin with a technical lemma.

Lemma 5.2 Suppose M and 𝔐 are as in the preceding theorem, and let T_{i} : M → 𝔐, i = 1, 2, be two contraction mappings each having Lipschitz constant k < 1. Then, if F (T_{1}) and F (T_{2}) denote the respective fixed point sets of T_{1} and T_{2},

H(F (T_{1}), F (T_{2})) ≤ \frac{1}{1 − k} sup_{x∈M} H(T_{1}(x), T_{2}(x)).

Proof. Let ϵ > 0, choose c > 0 so that c ∑_{n=1}^{∞} nk^{n} < 1, and set

ϵ_{1} = \frac{cϵ}{(1 − k)}.

Select x_{0} ∈ F (T_{1}), and then select x_{1} ∈ T_{2}(x_{0}) so that

d(x_{0}, x_{1}) ≤ H(T_{1}(x_{0}), T_{2}(x_{0})) + ϵ_{1}.

Since H(T_{2}(x_{1}), T_{2}(x_{0})) ≤ k d(x_{1}, x_{0}) there exists x_{2} ∈ T_{2}(x_{1}) such that

d(x_{2}, x_{1}) ≤ k d(x_{1}, x_{0}) + kϵ_{1}.

Now define {x_{n}} inductively so that x_{n+1} ∈ T_{2}(x_{n}) and

d(x_{n+1}, x_{n}) ≤ k d(x_{n}, x_{n−1}) + k^{n}ϵ_{1}, n = 1, 2, · · ·.

Then

d(x_{n+1}, x_{n}) ≤ k d(x_{n}, x_{n−1}) + k^{n}ϵ_{1}
≤ k(k d(x_{n−1}, x_{n−2}) + k^{n−1}ϵ_{1}) + k^{n}ϵ_{1}
= k^{2} d(x_{n−1}, x_{n−2}) + 2k^{n}ϵ_{1}.

Continuing in this fashion we obtain

d(x_{n+1}, x_{n}) ≤ k^{n} d(x_{1}, x_{0}) + nk^{n}ϵ_{1}.

Therefore

∑_{n=m}^{∞} d(x_{n+1}, x_{n}) ≤ k^{m}(1 − k)^{−1}d(x_{1}, x_{0}) + ∑_{n=m}^{∞} nk^{n}ϵ_{1}.

Since the right side of the above tends to 0 as m → ∞, this proves that {x_{n}} is a Cauchy sequence with limit, say z. Since T_{2} is continuous, lim_{n→∞} H(T_{2}(x_{n}), T_{2}(z)) = 0. Also, since x_{n+1} ∈ T_{2}(x_{n}) it must be the case that z ∈ T_{2}(z), that is, z ∈ F (T_{2}). Furthermore

d(x_{0}, z) ≤ ∑_{n=0}^{∞} d(x_{n+1}, x_{n})

≤ (1 − k)^{−1}d(x_{1}, x_{0}) + ∑_{n=1}^{∞} nk^{n}ϵ_{1}

< (1 − k)^{−1}(d(x_{1}, x_{0}) + ϵ)

≤ (1 − k)^{−1}(H(T_{1}(x_{0}), T_{2}(x_{0})) + 2ϵ).

Reversing the roles of T_{1} and T_{2} and repeating the argument just given leads to the conclusion that for each y_{0} ∈ F (T_{2}) there exist y_{1} ∈ T_{1}(y_{0}) and w ∈ F (T_{1}) such that

d(y_{0}, w) ≤ (1 − k)^{−1}(H(T_{1}(y_{0}), T_{2}(y_{0})) + 2ϵ).

Since ϵ > 0 is arbitrary, the conclusion follows. ■

Theorem 5.3 Suppose M and 𝔐 are as in the preceding theorem, and let T_{i} : M → 𝔐, i = 1, 2, ··· be a sequence of contraction mappings each having Lipschitz constant k < 1. If lim_{n→∞} H(T_{n}(x), T_{0}(x)) = 0 uniformly for x ∈ M, then

lim_{n→∞} H(F (T_{n}), F (T_{0})) = 0.

Proof. Let ϵ > 0. Since lim_{n→∞} H(T_{n}(x), T_{0}(x)) = 0 uniformly it is possible to choose N ∈ ℕ so that for n ≥ N, sup_{x∈M} H(T_{n}(x), T_{0}(x)) < (1 − k)ϵ. By the lemma, H(F (T_{n}), F (T_{0})) < ϵ for all such n. ■

6. Generalized Contractions

There is a vast amount of literature dealing with technical extensions and generalizations of Banach’s theorem . Most of these results involve a common underlying strategy. One assumes that a self-mapping f of a complete metric space M satisfies some general (and frequently quite complex) contractive type condition (C) which implies that (1) the sequence of Picard iterates of the mapping, or some related sequence is Cauchy, and (2) the limit of such a sequence is always a fixed point of the mapping. The condition (C) usually involves a relationship between the six distances {d(x, y), d(f(x), f(y)), d(x, f(y)), d(f(x), y), d(x, f(x)), d(y, f(y))} for each pair x, y ∈ M, and continuity of the mapping may or may not be assumed. People who want to fully acquaint themselves with this literature are directed to the survey of Rhoades [102] which covers the period up through the mid-seventies, a paper by Hegedüs [42], a subsequent survey by Park and Rhoades [92], an analysis of [102] by Collaço and Silva [25], as well as references found in these sources. Further escalations in the level of complexity can be found in a paper by Park [89] and in Liu’s recent observations [72] involving Park’s conditions.

Here we describe an approach which is reasonably elegant, yet sufficiently general to include many of the interesting cases in the work alluded to above. As before we assume (M, d) is a metric space with T : M → M. For x ∈ M let

O(x) = {x, T (x), T^{2}(x), ⋯},

and let O(x, y) denote O(x) ∪ O(y) for x, y ∈ M. Let ϕ be a contractive gauge function on ℝ^{+}. This means ϕ : ℝ^{+} → ℝ^{+} is continuous, nondecreasing, and satisfies ϕ(s) < s for s > 0.

Clearly if ϕ(s) = ks for s ∈ ℝ^{+} and fixed k ∈ [0, 1), then a mapping T : M → M satisfying

d(T (x), T (y)) ≤ ϕ(d(x, y))

for all x, y ∈ M is a contraction mapping in the sense of Banach and thus if M is complete T has a unique fixed point z ∈ M. It is a far reaching extension of this approach inspired by Felix Browder that we take up here. We begin with the following fact due to Walter [122].

Theorem 6.1 Let M be a complete metric space and suppose T : M → M has bounded orbits and satisfies the following condition. For each x ∈ M there exists n(x) ∈ ℕ such that for all n ≥ n(x) and y ∈ M,

d(T^{n}(x), T^{n}(y)) ≤ ϕ(diam(O(x, y))).  (6.1)

Then there exists z ∈ M such that lim_{k→∞} T^{k}(x) = z for each x ∈ M.

Proof. This is essentially the proof of Browder [13]. There are four steps. For x ∈ M we use the notation x^{k} = T^{k}(x), k = 0, 1, 2, · · ·.

\underline{Step} 1. If m = max\{n(x), n(y)\}, then diam(O(x^{m}, y^{m})) ≤ ϕ(diam(O(x, y))).

Proof. Suppose n ≥ m and r ≥ 0. Then any two elements (u, v) of O(x^{m}, y^{m}) are of one of the forms: (x^{n}, y^{n+r}), (x^{n+r}, y^{n}), (x^{n}, x^{n+r}), or (y^{n}, y^{n+r}). In the first case we have

d(u, v) = d(T^{n}(x), T^{n}(y^{r})) ≤ ϕ(diam(O(x, y^{r}))) ≤ ϕ(diam(O(x, y))).

The other three cases follow by similar inequalities.

Next we define sequences {k(i)} ⊂ ℕ and A_{i} ⊂ M by

k(0) = 0; k(i + 1) = k(i) + max{n(x^{k(i)}), n(y^{k(i)})}

and

A_{i} = O(x^{k(i)}, y^{k(i)}), i = 0, 1, 2, · · ·.

\underline{Step} 2. diam(A_{i+1}) ≤ ϕ(diam(A_{i})) for i = 0, 1, 2, · · ·.

Proof. For i = 0 this is just a restatement of (1). Now let i be arbitrary and let ξ = x^{k(i)}, η = y^{k(i)}, and μ = max{n(x^{k(i)}), n(y^{k(i)})}. Applying Case (1) we have

diam(O(ξ^{μ}, η^{μ})) ≤ ϕ(diam O(ξ, η)).  (6.2)

However ξ^{μ} = x^{k(i)+μ} = x^{k(i)+max{n(x^{k(i)}),n(y^{k(i)})}} = x^{k(i+1)}. Similarly, η^{μ} = y^{k(i)+μ} = y^{k(i+1)}. Thus diam(O(ξ^{μ}, η^{μ})) = diam(A_{i+1}) and (6.2) coincides with (2).

Now let a_{i} = diam(A_{i}).

\underline{Step} 3. lim_{i→∞} a_{i} = 0.

Proof. From (2) and the fact that ϕ is decreasing we have a_{i+1} ≤ ϕ(a_{i}) ≤ a_{i}. Thus {a_{i}} is decreasing so there exists a ≥ 0 such that lim_{i→∞} a_{i} = a ≤ ϕ(a). Since ϕ(a) < a if a > 0, it must be the case that a = 0.

\underline{Step} 4. We have shown that lim_{i→∞} diam(A_{i}) = lim_{i→∞} diam(O(x^{k(i)}, y^{k(i)})) = 0. This clearly implies lim_{k→∞} diam(O(x^{k}, y^{k})) = 0. Thus both {x^{k}} and {y^{k}} are Cauchy sequences and have the same limit, say z ∈ M. Since y ∈ M is arbitrary, we conclude that in fact lim_{k→∞} x^{k} = z for each x ∈ M. ■

Corollary 6.2 If in addition to the assumptions of Theorem 6.1 we assume that T is continuous, then T (z) = z.

By strengthening the assumption (6.1) to require that n(x) = 1 for all x ∈ M it is possible to conclude that T has a fixed point without assuming continuity.

Theorem 6.3 Let M be a complete metric space and suppose T : M → M has bounded orbits and satisfies the following condition. For each x, y ∈ M,

d(T (x), T (y)) ≤ ϕ(diam(O(x, y))).  (6.3)

Then T has a unique fixed point z ∈ M and lim_{k→∞} T^{k}(x) = z for each x ∈ M.

Proof. By Theorem 6.1 there exists z ∈ M such that lim_{k→∞} T^{k}(x) = z for each x ∈ M. Assume z ≠ T (z). Then diam(O(z)) = α > 0. From this it is possible to select two sequences {p(k)} and {q(k)} such that

0 ≤ p(k) < q(k) and for which lim_{k→∞} d (z^{p(k)}, z^{q(k)}) = α.

Since lim_{k→∞} z^{k} = z there exists k_{0} ∈ ℕ such that for k, l ≥ k_{0,} d(z^{k}, z^{l}) ≤ α/2. Hence for some p with 0 ≤ p < k_{0}, it must be the case that p(k) ≡ p for infinitely many k. Therefore there is a subsequence {r(k)} of {q(k)} such that lim_{k→∞} d(z^{p}, z^{r(k)}) = α. If r(k) = q infinitely often, then d(z^{p}, z^{q}) = α. Otherwise there exists a subsequence of {s(k)} of {r(k)} with s(k) → ∞ as k → ∞ and this implies d(z^{p}, z) = α. In any case, there exist p, q ≥ 0 such that d(z^{p}, z^{q}) = α. If p, q ≥ 1 then (6.3) implies

d(z^{p}, z^{q}) = d(T (z^{p−1}), T (z^{q−1})) ≤ ϕ(diam(O(z^{p−1}, z^{q−1}))) ≤ ϕ(diam(O(z)).

Since α = d(z^{p}, z^{q}) = diam(O(z)) this gives α ≤ ϕ(α).

On the other hand, if d(z, z^{q}) = α, then since lim_{k→∞} z^{k} = z

α = lim_{k→∞} d(z^{k}, z^{q}) ≤ ϕ(diam(O(z^{k−1}, z^{q−1}))) ≤ ϕ(α).

In either case we have a contradiction since ϕ(α) < α if α > 0. Hence O(z) = {z}. ■

In an attempt to extend the contraction principle in another direction Jachymski and Stein [56] have formulated the following conjecture.

Conjecture 6.4 Let (M, d) be a complete metric space, k ∈ (0, 1), and T : M → M. Let J be a given finite subset of ℕ, and assume T satisfies the condition

min {d (T^{i} (x) , T^{i} (y)) : i ∈ J} ≤ kd (x, y) .

Then T has a fixed point.

The above obviously reduces to Banach’s principle if J = {1} . The conjecture has also been confirmed ([55]) for the sets J = {p, 2p} , J = {p, 3p} , J = {2p, 3p} , p ∈ ℕ. See [113] for further discussion.

7. Probabilistic metrics and fuzzy sets

In an attempt to respond to classical concerns about imprecision in the natural world, K. Menger [79], [80] introduced the concept of a probabilistic metric space. These are spaces in which the distance between points is a probability distribution on ℝ^{+} rather than a real number. A short time later L. A. Zadeh [127] introduced the notion of a fuzzy set in a similar attempt to deal with situations in which the imprecision is not of obvious probabilistic nature. In both settings it is possible to introduce ‘metric’ concepts and ask about the corresponding fixed point theory for ‘contraction’ mappings (along with fixed point theory in a broader sense), as well as applications.

There is no analogue of Banach’s contraction mapping theorem for complete probabilistic metric spaces in general, but a number of positive results are known. In order to describe these we need to introduce precise definitions. As usual, let ℝ^{+} = [0, ∞). A mapping F : ℝ^{+} → [0, 1] is called a (distance) distribution function if it is nondecreasing and left-continuous, with F (0) = 0 and sup_{x∈ℝ} F (x) = 1. We denote the set of all such functions D^{+} and we use ε_{0} to denote the specific distribution function defined by

ε_{0} (x) = \{ \begin{matrix}0 & if x = 0; \\ 1 & if x > 0. \end{matrix}

The definition also entails the notion of a t-norm . A mapping τ : [0, 1] × [0, 1] → [0, 1] is called a t-norm if for any a, b, c, d ∈ [0, 1] :

(i) τ (a, 1) = a;

(ii) τ (a, b) = τ (b, a) ;

(iii) τ (c, d) ≥ τ (a, b) if c ≥ a and d ≥ b;

(iv) τ (τ (a, b) , c) = τ (a, τ (b, c)) .

Let S be a nonempty set. A probabilistic metric space (also often called a PM-space or Menger space) is an ordered triple (S, F, τ) which satisfies the following conditions.

(I) F : S × S → D^{+} is a symmetric function which satisfies (denoting F (p, q) = F_{p,q} for (p, q) ∈ S × S) :

(1) F_{p,q} = ε_{0} if and only if p = q;

(2) F_{p,r} (x) = 1 and F_{r,q} (y) = 1 ⇒ F_{p,q} (x + y) = 1 for all p, q, r ∈ S and all x, y ∈ ℝ^{+}.

(II) τ is a t-norm on (S, F) which satisfies

F_{p,q} (x + y) ≥ τ (F_{p,r} (x) , F_{r,q} (y))

for every p, q, r ∈ S, x, y ∈ ℝ^{+}.

A Hausdorff topology on a probabilistic metric space (S, F, τ) is given by the neighborhood system 𝔘 = {U_{q} (ε, λ)} , q ∈ S, ε, λ > 0, where

U_{q} (ε, λ) = {p ∈ S : F_{p,q} (ε) > 1 − λ} .

If sup_{x∈(0,1)} τ (x, x) = 1, this topology is metrizable. A sequence {p_{n}} in S is said to be τ-convergent to p ∈ S if given ε, λ > 0 there exists N = N (ρ, λ) ∈ ℕ such that F_{p_{n},p} (ε) > 1 − λ whenever n ≥ N; {p_{n}} is τ-Cauchy if given ε, λ > 0 there exists N = N (ρ, λ) ∈ ℕ such that F_{p_{n},p_{m}} (ε) > 1 − λ whenever n, m ≥ N; and (S, F, τ) is said to be complete if every τ-Cauchy sequence has a τ-limit.

The first ‘contraction type’ fixed point theorem of note in the setting described above is due to Sehgal and Bharucha-Reid [111]. This theorem applies to probabilistic metric spaces for which the t-norm τ is the function min. These spaces are metrizable according to the above definition.

Theorem 7.1 Let (S, F, τ) be a complete probabilistic metric space for which the tnorm τ is min. Suppose f : S → S is a continuous mapping for which there exists k ∈ (0, 1) such that for all p, q ∈ S and all u > 0,

F_{fp,fq} (ku) ≥ F_{p,q} (u) .

Then f has a unique fixed point p ∈ S, and f^{n} (q) → p for each q ∈ S.

It is also noted in [111] that every complete metric space easily gives rise to an induced complete probabilistic metric space; thus it is actually possible to derive Banach’s contraction mapping principle from the above result.

Since the appearance of Theorem 7.1 several approaches to the fixed point problem in probabilistic metric spaces have been undertaken. One approach seeks to identify those t-norms which are strong enough to assure that the sequence of Picard iterates of the mapping at a point is a Cauchy sequence (e.g., [40]). Another approach, initiated by Hicks in [44], has been to modify the contractive definition. However it was noted in [97] (also [107]) that a contraction mapping in the sense of [44] is in fact a standard contraction mapping on a related metric space to which Banach’s theorem applies. A recent generalization of the approach of Hicks is given in [88]. Another quite recent approach (Tardiff [118]) imposes growth conditions on the distribution functions and yields the following.

Theorem 7.2 Let (S, F, τ) be a complete probabilistic metric space and τ a continuous t-norm which is stronger than T (x, y) = max {x + y − 1, 0} , x, y ∈ [0, 1] . If for all p, q ∈ S

∫_{1}^{∞} ln u dF_{p,q} (u) ≤ ∞,

then any contraction in the sense of Theorem 7.1 has a unique fixed point.

In concluding our very abbreviated review of literature on this topic, we mention that a comparison of various contractive conditions in probabilistic spaces can be found in Tan [115]. Also a rather technical generalized contraction principle is given in Chang, et al [20], which is then applied to a class of differential equations in probabilistic metric spaces.

We now turn to fuzzy sets. Let (M, d) be a metric space. A fuzzy set in M is a mapping A : M → [0, 1] . For x ∈ M, A (x) denotes the ‘grade of membership’ of x in A. We denote the collection of all fuzzy sets in M by 𝔉 (M) .

For A ∈ 𝔉 (M) and α ∈ [0, 1] the α-level set of A, denoted A_{α}, is defined by

A_{α} = {x ∈ M : A (x) ≥ α} if α ∈ (0, 1]; and
A_{0} = \overline{\{x ∈ M : A (x) > 0\}}.

A number of metrics are used on subspaces of fuzzy sets (e.g., see [30]), and in [59] Kaleva shows how Banach’s contraction mapping theorem can be applied to obtain existence of solutions of fuzzy differential equations for fuzzy set-valued mappings of a real variable whose values are normal, convex, upper semicontinuous compactly supported fuzzy sets in ℝ^{n}.

We now describe the fundamental contraction principle for fuzzy metrics. This result is due to Heilpern [43].

Definition 7.3 A fuzzy subset A of a metric linear space M is an approximate quantity if sup_{x∈M} A (x) = 1 and if its α-level sets are compact convex subsets of X for each α ∈ [0, 1] . The collection of approximate quantities of 𝔉 (M) is denoted 𝔚 (M) .

For A, B ∈ 𝔚 (M) and α ∈ [0, 1] define

p_{α} (A, B) = inf {d (x, y) : x ∈ A_{α}, y ∈ B_{α}};
D (A, B) = sup_{α} H (A_{α}, B_{α}) ,

where H denotes the usual Hausdorff distance between closed subsets of M.

Definition 7.4 Let S be an arbitrary set and M any metric linear space. A mapping F : S → 𝔚 (M) is called a fuzzy mapping .

Theorem 7.5 Let M be a complete metric linear space and let F : M → 𝔚 (M) be a fuzzy mapping. Suppose there exists k ∈ (0, 1) such that for each x, y ∈ M

D (F (x) , F (y)) ≤ kd (x, y) .

Then there exists x^{∗} ∈ M such that {x^{∗}} ⊂ F (x^{∗}) .

Using the above theorem as a point of departure there have been many extension of the standard metric fixed point theorems to a fuzzy setting. For the most part the methods used to obtain these results mimic their non-fuzzy counterparts. The topological theory is another matter. For example in Diamond, et al [30] a direct proof is given which shows that the space of fuzzy sets on a compact metric space with the so-called ‘sendographic’ metric has the fixed point property for continuous maps.

8. Converses to the contraction principle

There are several versions of the ‘converse’ of Banach’s contraction mapping principle, each focusing on different underlying assumptions. The first result of this type, and in some sense the most elegant, is due to Bessaga [5]. One of the most accessible of the several proofs of Bessaga’s result is the adaptation of Wong’s proof of [124] which is found in Deimling’s book [28], pp. 191-192. An application of Bessaga’s converse in which the uniqueness assumption is dropped in exchange for a weaker conclusion is given in [105].

We devote this section to Bessaga’s original proof. Related questions, especially those pertaining to foundational aspects of the converse of Banach’s theorem, are found in [52] and elsewhere in this volume.

Theorem 8.1 Suppose S is an arbitrary nonempty set and suppose f : S → S has the property that f and each of its iterates f^{n} has a unique fixed point. Then for each λ ∈ (0, 1) there is a metric ρ_{λ} on S such that the space (S, ρ_{λ}) is a complete metric space and for which ρ_{λ} (f (x) , f (y)) ≤ λρ_{λ} (x, y) for each x, y ∈ S.

Proof. Define two equivalence relations in S as follows. (1) x ∼ y ⇔ either x = y or f^{n−1} (x) ≠ f^{n} (x) = f^{n} (y) ≠ f^{n−1} (y) for some n ∈ ℕ; (2) x ≈ y ⇔ f^{p} (x) = f^{q} (y) for some p, q ∈ ℕ. Clearly x ∼ y ⇒ x ≈ y. For x ∈ S let

[x] = {y ∈ S : x ∼ y} and [S] = {[x] : x ∈ S} .

Next, for arbitrary [x] ∈ [S] let

[[x]] = {[y] ∈ [S] : ∃ x_{1} ∈ [x] , y_{1} ∈ [y] such that x_{1} ≈ y_{1}} .

Similarly, set

[[S]] = {[[x]] : [x] ∈ [S]} .

Observe that for each u, v ∈ S either [[u]] = [[v]] or [u] ∉ [[v]] . Finally define

[x] ≤ [y] ⇔ ∃ x_{1} ∈ [x] , y_{1} ∈ [y] such that f^{k} (x_{1}) = y_{1} for some k ≥ 0.

Then ≤ assigns an order type to each of the sets [[x]] similar to one of the following: some natural number n ≥ 1, the set ω of all natural numbers, the set ω^{∗} of all negative integers, or the set ω^{∗} + ω of all integers. Consequently it is possible to ‘label’ each set [[x]] according to its order type in a natural way. Observe that the case ω^{∗} + ω requires the Axiom of Choice^{1}. For [y] ∈ [[x]] , select y_{0} ∈ [y], set ξ (y_{0}) = 0, and define

ξ (u) = \{ \begin{matrix}1 if u ∈ [y_{0}]^{+} ; \\ 0 if u ∈ [y_{0}] ; \\ −1 if y_{0} ∈ [u]^{+} , \end{matrix}

where [y]^{+} denotes the successor of [y] relative to ≤.

The convention just described defines a function ξ : S → ℤ with the properties

x ∈ [y] ⇒ ξ (y) = ξ (x)
x ∈ [y]^{+} ⇒ ξ (y) = ξ (x) + 1,

For every x ∈ S set f^{∞} (x) = x̄, where x̄ is the unique fixed point of f. Now define a metric ρ on S × S by setting

ρ (x, x′) = ∑_{i=1}^{p} λ^{ξ(x)+i} + ∑_{i=1}^{q} λ^{ξ(x′)+i},

where p and q are the smallest nonnegative numbers for which f^{p} (x) = f^{q} (x′) . (Apply the usual convention ∑_{i=1}^{0} λ^{ξ(x)+i} = 0.)

It is obvious that ρ (T (x) , T (x′)) ≤ λρ (x, x′) for each x, x′ ∈ S. Also if x ∈ S and x ≠ x̄, then ξ (f^{n} (x)) → ∞ and

ρ (f^{n} (x) , x̄) = ∑_{i=1}^{∞} λ^{ξ(f^{n}(x))+i} → 0.

Next observe that if x ≠ x′ then either p ≥ 1 or q ≥ 1 and consequently

ρ (x, x′) ≥ min {λ^{ξ(x)+1}, λ^{ξ(x′)+1}} .

Now suppose {x_{n}} is a Cauchy sequence in (S, ρ) and suppose ξ (x_{n}) ↛ ∞. Then (by passing to a subsequence) we may suppose that ξ (x_{n}) ≤ N < ∞ for all n ≥ 1. Since λ ∈ (0, 1) ,this implies

λ^{ξ(x_{n})+1} ≥ λ^{N+1};

hence ρ (x_{n}, x_{m}) ≥ λ^{N+1} for all x_{n} ≠ x_{m} which contradicts the assumption that {x_{n}} is Cauchy. Therefore if {x_{n}} is a Cauchy sequence in (S, ρ) then ξ (x_{n}) → ∞, and it follows that {x_{n}} converges to x̄. This proves that (S, ρ) is complete. ■

REMARK. For the conclusion of Theorem 8.1 it suffices only to assume that f^{n} has at least one fixed point for n ≥ 1 and that some f^{n} has a unique fixed point. (This is the formulation given in [28].) Under this assumption it is possible to apply Theorem 8.1 to f^{n} and obtain a complete metric relative to which f^{n} is a contraction, apply Theorem 2.4 to conclude that f has a unique fixed point, then apply Theorem 8.1 to f and obtain another complete metric relative to which f is a contraction.

Another question arises. Instead of starting with an abstract set, suppose one has a mapping of a metric space into itself which has a unique fixed point. Then when

1In fact Bessaga notes in [5] that Theorem 8.1 implies this form of the Axoim of Choice.

does an equivalent metric exists relative to which the mapping is a contraction? The following theorem is due to Janos [48].

Theorem 8.2 Suppose (M, ρ) is a compact metric space, and suppose f : M → M is continuous and satisfies

∩_{n=0}^{∞}f^{n} (M) = {ξ} .

Then for each λ ∈ (0, 1) there exists a metric ρ_{λ} on M such that the space (M, ρ_{λ}) is a compact metric space and for which ρ_{λ} (f (x) , f (y)) ≤ λρ_{λ} (x, y) for each x, y ∈ M.

In [81] Meyers modified the ideas in Janos’s proof to obtain another version of the converse to Banach’s theorem by considering continuous self-mappings of a metrizable topological space X. Such a map f is said to be contractifiable if f is a contraction mapping relative to an appropriate metrization of X. If f is a contraction mapping on X then there is a point ξ ∈ X and an open neighborhood U of ξ such that

f (ξ) = ξ;  (8.1)
f^{n} (x) → ξ for each x ∈ X;  (8.2)
f^{n} (U) → {ξ} .  (8.3)

The explicit meaning of the last assertion is that for each neighborhood V of ξ there is an integer n (V) > 0 such that f^{n} (U) ⊂ V for all n ≥ n (V) . In [81] (also see [82]) Meyers proved that if f is continuous and satisfies (8.1) - (8.3) for some ξ ∈ X and some open neighborhood U of ξ, then f is contractifiable. Completeness of X is not assumed. This result, in essence, was subsequently rediscovered by Leader in [67]. The following is an explicit statement of Leader’s result.

Theorem 8.3 Suppose T maps a metric space (M, ρ) into itself. Then there exists a metric Σ which is topologically equivalent to ρ and for which T : (M, Σ) → (M, Σ) is a contraction mapping with fixed point p if and only if:

(a) lim_{n→∞} T^{n} (x) = p for each x ∈ M; and

(b) the limit in (a) holds uniformly in some neighborhood V of p.

9. Notes and remarks

1. It would be difficult to overestimate the number of variations on the contraction mapping theme which appear in the literature. Some are attempts to unify underlying principles; others represent specific adjustments designed for particular applications.

A recent example is an article of Chen [23]. The point of departure is the following result found in [66]. Let M be a complete metric space, let T : M → M, and

(C) suppose for each 0 < a < b there exists L (a, b) ∈ (0, 1) such that

d (T (x) , T (y)) ≤ L (a, b) d (x, y)

for all x, y ∈ M.

Then T has a unique fixed point z, and lim_{n} T^{n} (x) = z for each x ∈ M.

Since T satisfies C it is possible to set,

L (a) = sup {d (T (x) , T (y)) /d (x, y) : d (x, y) = a} ,

and observe that if a′ < a then L (a) ≤ L (a′, a) ∈ (0, 1) . In particular

d (T (x) , T (y)) ≤ L (d (x, y)) d (x, y)

and it is possible to reach the desired conclusion, for example, via Theorem 3.6. (It suffices to select a number b > 0 for which d (u, T (u)) < b for some u ∈ M and then replace M with the space

M′ = {x ∈ M : d (x, T (x)) ≤ b} .

Under these circumstances, if L (a_{n}) → 1 and if a_{n} ↛ 0 then by passing to a subsequence we may suppose there exists 0 < a < b such that a ≤ a_{n} ≤ b and reach a contradiction.)

2. Often in the study of contraction mappings assumptions which are not fully needed are made out of habit. For example many theorems which invoke continuity actually hold under the weaker assumption that the mapping f : (M, d) → (M, d) in question has a close graph. (This means that for {x_{i}} ⊂ M the conditions lim_{i} x_{i} = x and lim_{i} f (x_{i}) = y imply f (x) = y.). This observation applies to the contractive condition as well. For example the assumption d (f (x) , f^{2} (x)) ≤ kd (x, f (x)) for x ∈ M, k ∈ (0, 1) suffices to assure {f^{n} (x)} is a Cauchy sequence. (See [45] for an early example of this line of thinking.)

3. (Set valued contractions) Extensions of set-valued contractions in the spirit of some of the early extension of Banach’s theorem have also been undertaken. Let (M, d) be a complete metric space, and let CB (M) and K (M) denote, respectively, the space of all nonempty closed bounded subsets and all nonempty compact subsets of M endowed with the Hausdorff metric. It is known that if T : M → K (M) satisfies

H (T (x) , T (y)) ≤ k (d (x, y)) d (x, y) for x, y ∈ M, x ≠ y,

where k : (0, ∞) → [0, 1) satisfies lim sup_{s→∞} k (s) < 1 for each t > 0, then T has a fixed

point. S. Reich ([100], [101]) has asked whether K (M) can be replaced with CB (M) in this result. A partial affirmative answer has recently been given in [51]; also see [26]. For a variation on this approach, see [21].

4. (Topological extensions) In 1971, Cain and Nashed [17] extended the contraction mapping theorem to Hausdorff locally convex topological vector spaces (𝔼, {|·|_{α}}_{α∈A}) (where {|·|_{α}}_{α∈A} is a family of seminorms generating the topology of 𝔼) as follows: For X ⊂ 𝔼, a mapping f : X → X is said to be a contraction mapping if for every α ∈ A, there exists k_{α} < 1 such that

|f (x) − f (y)|_{α} ≤ k_{α} |x − y|_{α} for every x, y ∈ X.

They showed that the Banach contraction principle is still valid for such mappings defined on sequentially complete subspaces of X.

There have been a number of extensions of the contraction mapping theorem and related results from a metric setting to a uniform space setting. Among the first were extensions given by Knill [62] and Tarafdar [116]. Those interested in pursuing this aspect of the theory further might want to check the survey by Lee [68], the papers [1], [41], [83], and certainly the book by Hadžić [41] and citations therein. A fixed point theorem for generalized contractions defined in guage spaces has recently been given by Frigon [37]. This result is obtained via an application of the set-valued theorem of of Nadler [84].

5. (Structure of fixed point sets) As noted above, a multivalued contraction mapping whose values are compact and connected may have a disconnected fixed point set. With sufficiently strong additional assumptions this is not the case. A nonempty closed subset P of a Banach space X is called α-paraconvex, α ∈ [0, 1] , if for every r > 0 and every open ball D of radius r such that D∩P ≠ ∅, it is the case that dist (q, P) ≤ αr for every q ∈ conv {D ∩ P } . It is shown in [109] that if F : X → 2^{X} is a contraction mapping with Lipschitz constant γ, where α + γ < 1, and if F takes values in the collection of α-paraconvex subsets of X, then F ix (F) is a (continuous single-valued) retract of X.

6. (Ultrametric spaces) Ultrametric spaces are metric spaces for which a much stronger version of the triangle inequality holds.

Definition 9.1 A metric space (M, d) is an ultrametric space if, in addition to the usual metric axioms, the following property holds for each x, y, z ∈ M :

d(x, z) ≤ max{d(x, y), d(y, z)}.

It is immediate from the definition that if d(x, y) ≠ d(y, z) then in fact

d(x, z) = max{d(x, y), d(y, z)}.

Therefore each three points of an ultrametric spaces represent vertices of an isosceles triangle. This leads to an anomaly.

(1) If B(a; r_{1}) and B(b; r_{2}) are two closed balls in an ultrametric space, with r_{1} ≤ r_{2}, then either B(a; r_{1}) ∩ B(b; r_{2}) = ∅ or B(a; r_{1}) ⊆ B(b; r_{2}). In particular if a ∈ B(b; r_{2}), then B(a; r_{1}) ⊆ B(b; r_{2}).

An ultrametric space M is said to be spherically complete if every descending sequence of closed balls in M has nonempty intersection. Thus a spherically complete ultrametric space is always complete (where only sequences of balls whose radii tend to 0 are considered).

The following is now an immediate consequence of (1).

(2) If 𝔉 is a family of closed balls in a spherically complete ultrametric space and if each two members of 𝔉 intersect, then ∩𝔉 ≠ ∅.

Another consequence of (1).

(3) If B(a; r_{1}), B(b; r_{2}) are closed balls in an ultrametric space, if B(a; r_{1}) ⊆ B(b; r_{2}), and if b ∉ B(a; r_{1}), then d(b, a) = d(b, z) for each z ∈ B(a; r_{1}).

Proof. Since b ∉ B(a; r_{1}) and z ∈ B(a; r_{1}), d(b, a) > d(z, a). Hence d(b, a) = d(b, z).

■

The following fixed point result is due to Priess-Crampe [96].

Theorem 9.2 An ultrametric space M is spherically complete if and only if every strictly contractive mapping T : M → M has a (unique) fixed point.

7. (Applications in logic and programming languages) For an excellent non-technical account of how fixed-point theorems, and Banach’s theorem in particular, come in to play in the study of denotational semantics in programming languages, see de Bakker and de Vink [27]. It is interesting to note that the metric involved in this case is also an ultrametric. Another variation on the metric theme is found in Seda [108] where the author investigates the role of quasi-metrics (non-symmetric metrics) and uses the Banach contraction principle as a substitute for the Knaster-Tarski theorem in the semantics of logic programs.

8. (Remetrization) Banach’s theorem obviously holds in any metric space which is completely metrizable, but the following fact is somewhat surprising. In [36] it is shown that any separable metric space (M, d) has an equivalent metric ρ which has the property that every contraction mapping of (M, ρ) → (M, ρ) has unique fixed point. The approach in [36] has a deep topological flavor.

9. (Hybrid extensions) A view to applications has motivated numerous extensions of Banach’s theorem. An early example is a result of Krasnoselskii [63] which combines the metric theory with the topological.

Theorem 9.3 Let K be a closed convex nonempty subset of a Banach space X, and suppose that U and V are mappings of K into X which satisfy:

(i) if x, y ∈ K, then U (x) + V (y) ∈ K;

(ii) U is continuous and \overline{U (K)} is compact;

(iii) V is a contraction mapping.

Then there exists x ∈ K such that x = U (x) + V (x) .

(See [15] for a very recent extension of this approach.)

Krasnoselskii’s approach can be thought of as a very early precursor to the study of k-set contractions (k < 1) and condensing mappings taken up elsewhere in this volume.

10. (Local contractions) A mapping f : (M, d) → (M, d) is said to be a local contraction (with constant k ∈ (0, 1)) if for each x ∈ M there exists a neighborhood N (x) of x such that for each u, v ∈ N (x) , d (f (u) , f (v)) ≤ kd (u, v) ; if it is assumed only that d (f (u) , f (x)) ≤ kd (u, x) for each u ∈ N (x) , then f is called a local radial contraction. These are two of the standard localizations of the contraction mapping condition (cf., Rakotch [99] and Holmes [46] respectively).

In [99] it is shown that if (M, d) is complete and if f : (M, d) → (M, d) is a local radial contraction with the property that x_{0} and f (x_{0}) are joined by a path of finite length for some x_{0} ∈ M, then f has a fixed point. In [47] it is shown that this fact actually is a direct consequence of Banach’s theorem. In [46] Holmes proves that if (M, d) is connected and locally connected, and if f : (M, d) → (M, d) is a homeomorphism of M onto M which is also a local radial contraction on M, then in fact there exists a metric δ on M which is equivalent to d and for which f : (M, δ) → (M, δ) is a global contraction. However, as noted in [47], the assertion in [46] that (M, δ) is complete is false. (It is noted in [58] that because of another incorrect assertion in [46] the proof of [47] requires minor adjustments.)

Additional comments on the local theory appear elsewhere in this volume.

11. (Continuous mappings). There is even a contraction mapping link to the fixed point problem for continuous mappings. In [57] it is shown that a continuous mapping f of a complete metric space (M, d) into itself has a fixed point if and only if there exists α ∈ (0, 1) and a mapping g : M → M which commutes with f and satisfies the conditions: g (M) ⊆ f (M) and d (g (x) , g (y)) ≤ αd (f (x) , f (y)) for all x, y ∈ M. This of course reduces to the Banach contraction principle if f is the identity map.

12. (The converse problem) Some other variations and extensions of Janos’s result are given in Opoitsev [86]. The following topological variant is proved in [117]. A mapping f : X → 2^{X} (X a topological space) is said to be a topological contraction if f is upper semicontinuous with closed values having the property that f (A) = A for a nonempty closed subset A of X implies A is a singleton.

Theorem 9.4 Let X be a compact Hausdorff topological space and let f : X → 2^{X} be a topological contraction with nonempty closed values. Then there is a unique point x_{0} ∈ X such that {x_{0}} = f (x_{0}) = ∩_{n=0}^{∞}f^{n} (X) .

13. (Random theory). Contraction mappings also enter into the study of random fixed point theory. This theory has its roots in a paper by Bharucha-Reid [4]. Let (M, d) be a complete separable metric space and let (Ω, Σ) be a measureable space (i.e., Σ is a sigma-algebra of subsets of Ω.) A mapping T : Ω × M → M is said to be a random operator if, for any x ∈ M, T_{x} := T (·, x) : Ω → M is measurable (T_{x}^{−1} (B) ∈ Σ for each open subset B of M.) The fixed point set of T (ω, ·) is the set

{x ∈ M : x = T (ω, x)} .

A random fixed point of T is a measurable function x : Ω → M such that x (ω) = T (ω, x (ω)) for all ω ∈ Ω. If T is a set-valued mapping then a random fixed point of T is a measurable selection x of the mapping F defined by

F (ω) = {x ∈ M : x ∈ T (ω, x)} .

In [126] it is shown that if T is a suitably defined random set-valued contraction then the function F is measurable (and hence T has a random fixed point). This result is also an application of Nadler’s fixed point theorem [84] for set-valued contraction mappings. For additional results see the citations in [125].

References

[1] V. G. Angelov, A converse to a contraction mapping theorem in uniform spaces, Nonlinear Anal. 12(1988), 989–996.

[2] J. S. Bae and S. Park, Remarks on the Caristi-Kirk fixed point theorem, Bull. Korean Math. Soc. 19(1983), 57–60.

[3] S. Banach, Sur les opérations dans les ensembles abstraits et leurs applications aux équations intégrales, Fund. Math. 3(1922), 133–181.

[4] A. T. Bharucha-Reid, Fixed point theorems in probabilistic analysis, Bull. Amer. Math. Soc. 82(1976), 641–657.

[5] C. Bessaga, On the converse of the Banach “fixed-point principle”, Colloq. Math. VII(1959), 41–43.

[6] A. Bielecki, Une remarque sur la méthode de Banach-Caccioppoli-Tikhonov dans la théorie des équations differentielles ordinaires, Bull. Acad. Polon Sci. Cl. III, 4(1956), 261–264.

[7] L. M. Blumenthal, Distance Geometry, Oxford Univ. Press, London, 1953.

[8] D. W. Boyd and J. S. W. Wong, On nonlinear contractions, Proc. Amer. Math. Soc. 20(1969), 458–464.

[9] H. Brezis and F. E. Browder, A general principle on ordered sets in nonlinear functional analysis, Advances in Math. 21(1976), 355–364.

[10] A. Brøndsted, Fixed points and partial orders, Proc. Amer. Math. Soc. 60(1976), 365–366.

[11] F. E. Browder, On the convergence of successive approximations for nonlinear functional equations, Nederl. Akad. Wetensch. Ser. A71=Indag. Math. 30(1968), 27–35.

REFERENCES 29

[12] F. E. Browder, On a theorem of Caristi and Kirk, Fixed Point Theory and its Applications (S. Swaminathan, ed.), Academic Press, New York, 1976, pp. 23–27.

[13] F. E. Browder, Remarks on fixed point theorems of contractive type, Nonlinear Anal. 3(1979), 657–661.

[14] T. A. Burton, Integral equations, implicit functions and fixed points, Proc. Amer. Math. Soc. 124(1996), 2383–2390.

[15] T. A. Burton and C. Kirk, A fixed point theorem of Krasnoselskii-Shaefer type, Math. Nachr. 189(1998), 23–31.

[16] R. Caccioppoli, Una teorema generale sull’esistenza di elementi uniti in una transformazione funzionale, Ren. Accad. Naz Lincei 11(1930), 794–799.

[17] G. L. Cain, Jr., and M. Z. Nashed, Fixed points and stability for a sum of two operators in locally convex spaces, Pacific J. Math. 39(1971), 581–592.

[18] J. Caristi, Fixed point theorems for mappings satisfying inwardness conditions, Trans. Amer. Math. Soc. 215(1976), 241–251.

[19] P. M. Centore and E. R. Vrscay, Continuity of attractors and invariant measures for iterated function systems, Canad. Math. Bull. 37(1994), 315–329.

[20] S. S. Chang, B. S. Lee, Y. J. Cho, Y. Q. Chen, S. M. Kang and S. M. Jung, Generalized contraction mapping principle and differential equations in probabilistic metric spaces, Proc. Amer. Math. Soc. 124(1996), 2367–2376.

[21] M. P. Chen and M-H. Shih, Fixed point theorems for point-to-point and point-to-set maps, J. Math. Anal. Appl. 71(1979), 516–524.

[22] Y.-Z. Chen, A variant of the Meir-Keeler type theorem in ordered Banach spaces, J. Math. Anal. Appl. 236(1999), 585–593.

[23] Y-Z. Chen, Inhomogeneous iterates of contraction mappings and nonlinear ergodic theorem, Nonlinear Anal. 39(2000), 1–10.

[24] S. Chu and J. B. Diaz, A fixed point theorem for “in the large” application of the contraction principle, Accad. delle Sci. Torino 999(1965), 351–363.

[25] P. Collaço and J. C. E. Silva, A complete comparison of 25 contraction conditions, Nonlinear Anal. 30(1997), 471–476.

[26] P. Z. Daffer, H. Kaneko, and W. Li, On a conjecture of S. Reich, Proc. Amer. Math. Soc. 124(1996), 3159–3162.

[27] J. W. de Bakker and E. P. de Vink, Denotational models for programming languages: applications of Banach’s fixed point theorem, 8th Prague Topological Symposium on General Topology and its Relations to Modern Analysis and Algebra (1996), Topology Appl 85(1998), 35–52.

[28] K. Deimling, Nonlinear Functional Analysis, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1980.

[29] K. Deimling, Multivalued Differential Equations, Walter de Gruyter, Berlin, New York, 1992.

[30] P. Diamond, P. Kloeden, and A. Pokrovskii, Absolute retracts and a general fixed point theorem for fuzzy sets, Fuzzy Sets and Systems 86(1977), 377–380.

[31] D. Downing and W. A. Kirk, A generalization of Caristi’s theorem with applications to nonlinear mapping theory in Banach spaces, Pacific J. Math. 69(1977), 339–346.

[32] D. Downing and W. A. Kirk, Fixed point theorems for set valued mappings in metric and Banach spaces, Math. Japonica 22(1977), 89–112.

[33] J. Dugundji and A. Granas, Weakly contractive maps and elementary domain invariance theorems, Gull. Greek Math. Soc. 19(1978), 141–151.

[34] I. Ekeland, Nonconvex minimization problems, Bull. Amer. Math. Soc. 1(1979), 443–474.

[35] B. Forte and E. Vrscay, Solving the inverse problem for function/image approximation using iterated function systems I. Theoretical Basis, Fractals 2(1994), 325–334.

[36] A. A. Florinskii, On the existence of connected extensions of metric spaces and Banach’s theorem on contraction mappings (Russian), Vestnik Leningrad. Univ. Mat. Mekh. Astronom. 1991, OVYR vyp. 4, 91(1992), 18–22; translation in Vestnik Leningrad Univ. Math. 24(1991), 17–20.

[37] M. Frigon, Fixed point results for generalized contractions and applications, Proc. Amer. Math. Soc. 128(2000), 2957–2965.

[38] M. Geraghty, On contractive mappings, Proc. Amer. Math. Soc. 40(1973), 604–608.

[39] K. Goebel and W. A. Kirk, Topics in Metric Fixed Point Theory, Cambridge Univ. Press, Cambridge, 1990.

[40] O. Hadžić, A generalization of the contraction principle in PM spaces, in Review of research Faculty of Science”, Zb. Rad. (Kragujevac)10(1980), 13–21.

[41] O. Hadžić, Fixed Point Theory in Probabilistic Metric Spaces, University of Novi Sad, Institute of Mathematics, Novi Sad, 1995.

[42] M. Hegedüs, New generalizations of Banach’s contraction principle, Acta Sci. Math. (Szeged) 42(1980), 87–89.

[43] S. Heilpern, Fuzzy mappings and fixed point theorems, J. Math. Anal. Appl. 83(1981), 566–569.

[44] T. L. Hicks, Fixed point theory in probabilistic metric spaces, in “Review of research Faculty of Science”, 13, Univ. of Novi Sad, Novi Sad, 1983, pp. 63–72.

[45] T. L. Hicks and B. E. Rhoades, A Banach type fixed point theorem, Math. Japonica 24(1979), 327–330.

[46] R. D. Holmes, Fixed points for local radial contractions, in Fixed Point Theory and its Applications (S. Swaminathan, ed.), Academic Press, New York, 1976, pp. 79–89.

[47] T. Hu and W. A. Kirk, Local contractions in metric spaces, Proc. Amer. Math. Soc. 68(1978), 121–124.

[48] L. Janos, A converse of Banach’s contraction theorem, Proc. Amer. Math. Soc. 18(1967), 287– 289.

[49] L. Janos, An application of combinatorial techniques to a topological problem, Bull. Austral. Math. Soc. 9(1973), 439–443.

[50] J. Jachymski, An iff fixed point criterion for continuous self-mappings on a complete metric space, Aeq. Math. 48(1994), 163–170.

[51] J. Jachymski, On Reich’s open question concerning fixed points of multimaps, Boll. Un. Math. Ital. (7) 9-A(1995), 453–460.

[52] J. Jachymski, An extension of A. Ostrowski’s theorem on the round-off stability of iterations, Aeq. Math. 53(1997), 242–253.

[53] J. Jachymski, Equivalence of some contractivity properties over metrical structures, Proc. Amer. Math. Soc. 125(1997), 2327–2335.

[54] J. Jachymski, A short proof of the converse to the contraction principle, and some related results, preprint.

[55] J. Jachymski, B. Schröder and J. D. Stein, Jr., A connection between fixed-point theorems and tiling problems, J. Combin. Theory Ser. A (1999), to appear.

[56] J. Jachymski and J. D. Stein, Jr., A minimum condition and some related fixed-point theorems, J. Austral. Math. Soc. (Series A) 66(1999), 224–243.

[57] G. Jungck, Commuting mappings and fixed points, Amer. Math. Monthly 83(1976), 261–263.

[58] G. Jungck, Local radial contractions – a counter-example, Houston J. Math. 8(1982), 501–506.

[59] O. Kaleva, Fuzzy differential equations, Fuzzy Sets and Systems 24(1987), 301–317.

[60] S. Kasahara, On fixed points in partially ordered sets and Kirk-Caristi theorem, Math. Sem. Notes, Kobe Univ. 3(1975), 229–232.

[61] W. A. Kirk, Caristi’s fixed point theorem and metric convexity, Colloq. Math. 36(1976), 81–86.

[62] R. J. Knill, Fixed points of uniform contractions, J. Math. Anal. Appl. 12(1965), 449–455.

[63] M. A. Krasnoselskii, Some problems of nonlinear analysis (Russian), Uspehi Math. Nauk (N.S.) 9(1961); Amer. Math. Soc. Translations 10(1958), 345–409.

[64] M. A. Krasnoselskii and V. J. Stetsenko, About the theory of equations with concave operators, Sib. Mat. Zh. 10(1969), 565–572 (Russian).

[65] M. A. Krasnoselskii and G. M. Vainikko, et al., Approximate solutions of operator equations, Wolters Noordhoff, Groningen, 1972.

[66] M. A. Krasnoselskii and P. P. Zabrieko, Geometrical Methods of Nonlinear Analysis, Springer-Verlag, Berlin, 1994.

[67] S. Leader, A topological characterization of Banach contractions, Pacific J. Math. 69(1977), 461–466.

[68] C. M. Lee, A development of contraction mapping principles on Hausdorff uniform spaces, Trans. Amer. Math. Soc. 226(1977), 147–159.

REFERENCES 31

[69] T. C. Lim, On fixed point stability for set-valued mappings with applications to generalized differential equations, J. Math. Anal. Appl. 110(1985), 436–441.

[70] T. C. Lim, On characterizations of Meir-Keeler contractive maps, Nonlinear Anal. (to appear).

[71] M. Lindelöf, Sur l’application des méthodes d’approximation successives l’étude des intégrales réeles des équations différentielles ordinaires, J. Math. Pures et Appl. (1894), 117–128.

[72] Z. Liu, On Park’s open questions and some fixed point theorems for general contractive type mappings, J. Math. Anal. Appl. 234(1999), 165–182.

[73] M. G. Maia, Un’Osservazione sulle contrazioni metriche, Rend. Sem. Mat. Univ. Padova 40(1968), 139–143.

[74] R. Mańka, Some forms of the axiom of choice, Jahrb. Kurt Gödel Ges. vol. 1, Wien, 1988, pp. 24–34.

[75] J. T. Markin, A fixed point theorem for set-valued mappings, Bull. Amer. Math. Soc. 74(1968), 639–640.

[76] J. Matkowski, Integrable solutions of functional equations, Diss. Math. 127, Warsaw, 1975.

[77] J. Matkowski, Nonlinear contractions in metrically convex spaces, Publ. Math. Debrecen 45/1-2(1994), 103–114.

[78] A. Meir and E. Keeler, A theorem on contraction mappings, J. Math. Anal. Appl. 28(1969), 326–329.

[79] K. Menger, Statistical metrics, Proc. Nat. Acad. Sci. 37(1951), 178–180.

[80] K. Menger, Probabilistic geometry, Proc. Nat. Acad. Sci. 37(1951), 226–229.

[81] P. R. Meyers, A converse to Banach’s contraction theorem, J. Research Nat. Bureau of Standards - B. Math. and Math. Physics, 71B(1967), 73–76.

[82] P. R. Meyers, On contractifiable self-mappings, Nonlinear Analysis (Th. M. Rassias, ed.), World Scientific Publ. Co., Singapore, 1987, pp. 407–432.

[83] N. Mizoguchi, A generalization of Brøndsted’s results and its applications, Proc. Amer. Math. Soc. 108(1990), 707–714.

[84] S. B. Nadler, Jr., Multivalued contraction mappings, Pacific J. Math. 30(1969), 475–488.

[85] W. Oetlli and M. Théra, Equivalents of Ekeland’s principle, Bull. Aust. Math. Soc. 48(1993), 385–392.

[86] V. I. Opoitsev, A converse to the principle of contracting maps, Russian Math. Surveys 31(1976), 175–204; (from Uspekhi Mat. Nauk 31(1976), 169–198).

[87] A. M. Ostrowski, The round off stability of iterations, Z. Angew. Math. Mech. 47(1967), 77–81.

[88] E. Pap, O Hadžić, and R. Mesiar, A fixed point theorem in probabilistic metric spaces and an application, J. Math. Anal. Appl. 202(1996), 433–449.

[89] S. Park, On general contractive type conditions, J. Korean Math. Soc. 17(1980), 131–140.

[90] S. Park, On extensions of the Caristi-Kirk fixed point theorem, J. Korean Math. Soc. 19(1983), 143–151.

[91] S. Park, Equivalent formulations of Ekeland’s variational principle for approximate solutions of minimization problems and their applications, Operator Equations and Fixed Point Theorems (S. P. Singh, et al., eds.), MSRI-Korea Publ., vol 1, 1986, pp. 55–68.

[92] S. Park and B. E. Rhoades, Meir-Keeler type contractive conditions, Math. Japon. 26(1981), 13–20.

[93] L. Pasicki, A short proof of the Caristi theorem, Ann. Soc. Polon. Series I: Comm. Math. 22(1978), 427–428.

[94] G. Peano, Sull’integrabilita delle equazioni differenziali del primo ordine, Atti R. Accad. Sci. Torino 21(1885-86), 677–685.

[95] J. P. Penot, A short constructive proof of Caristi’s fixed point theorem, Publ. Math. Univ. Paris 10(1976), 1–3.

[96] S. Priess-Crampe, Der Banachsche Fixpunktzatz für ultrametrische Räume, Results in Math. 18(1990), 178–186.

[97] V. Radu, Some fixed point theorems in probabilistic metric spaces, in: Lecture Notes in Math. vol. 1233, Springer Verlag, New York, Berlin, 1987, pp. 125–133.

[98] E. Rakotch, A note on contractive mappings, Proc. Amer. Math. Soc. 13(1962), 459–465.

[99] E. Rakotch, A note on α-locally contractive mappings, Bull. Res. Council Israel 40 (1962), 188–191.

[100] S. Reich, Some fixed point problems, Atti. Accad. Naz. Lincei Rend. Cl. Sci. fix. Mat. Natur. 57(1974), 194–198.

[101] S. Reich, Some problems and results in fixed point theory, in Topological Methods in Nonlinear Functional Analysis (S. P. Singh, S. Thormeier, and B. Watson, eds.), Contemporary Math. 21(1980), 179–187.

[102] B. E. Rhoades, A comparison of various definitions of contractive mappings, Trans. Amer. Math. Soc. 226(1970), 257–290.

[103] B. Ricceri, Une proprité topologique de l’esemble des points fixes d’une contraction multivoque à valuers convexes, Atti. Acc. Lincei Rend. Fis. 81(1987), 283–286.

[104] I. Rosenholtz, Evidence of a conspiracy among fixed point theorems, Proc. Amer. Math. Soc. 53(1976), 213–216.

[105] I. A. Rus, Weakly Picard mappings, Comment. Math. Univ. Carolinae 34(1993), 769–773.

[106] J. Saint Raymond, Multivalued contractions, Set-Valued Anal. 2(1994), 559–571.

[107] B. Schweizer, H. Sherwood, and R. Tardiff, Comparing two contraction notions on probabilistic metric spaces, Stochastica 12(1988), 5–17.

[108] A. K. Seda, Quasi-metrics and the semantics of logic programs, Fund. Inform. 29(1997), 97–117.

[109] P. V. Semenov, The structure of the fixed-point set of paraconvex-valued contraction mappings (Russian), Tr. Mat. Inst. Steklova 212(1996), 188–12.

[110] J. Siegel, A new proof of Caristi’s fixed point theorem, Proc. Amer. Math. Soc. 66(9177), 54–56.

[111] V. M. Sehgal and A. T. Bharucha-Reid, Fixed points of contraction mappings on probabilistic metric spaces, math. Systems Theory 6(1972), 97–102.

[112] H. Sherwood, Complete probabilistic metric spaces, Z. Wahrsch. Verw. Geb. 29(1971), 117–128.

[113] J. D. Stein, Jr., A systematic generalization procedure for fixed-point theorems, Rocky Mountain J. Math., to appear.

[114] W. Takahashi, Existence theorems and fixed point theorems for multivalued mappings, Fixed Point Theory and Applications (J. B. Baillon and M. Théra, eds.), Longman Sci. Tech., Essex, 1991, pp. 397–406.

[115] D. H. Tan, A classification of contractive mappings in probabilistic metric spaces, Acta Math. Vietnam.23(1998), 295–302.

[116] E. Tarafdar, An approach to fixed-point theorems on uniform spaces, Trans. Amer. Math. Soc. 191(1974), 209–225.

[117] E. Tarafdar and X. -Z. Yuan, Set-valued topological contractions, Appl. Math. Lett. 8(1995), 79–81.

[118] R. M. Tardiff, Contraction maps on probabilistic metric spaces, J. Math. Anal. Appl. 165(1992), 517–523.

[119] M. Tasković, A monotone principle of fixed points, Proc. Amer. Math. Soc. 94(1985), 427–432.

[120] F. Tricomi, Una teorema sulla convergenza delle successioni formate delle successive iterate di una funzione di una variabile reale, Giorn. Mat. Bataglini 54(1916), 1–9.

[121] M. Turinici, The monotone principle of fixed points: a correction, Proc. Amer. Math. Soc. 122(1994), 643–645.

[122] W. Walter, Remarks on a paper by F. Browder about contraction, Nonlinear Anal., 5(1981), 21–25.

[123] C. S. Wong, On a fixed point theorem of contractive type, Proc. Amer. Math. Soc. 57(1976), 283–284.

[124] J. S. W. Wong, Generalizations of the converse of the contraction mapping principle, Canad. J. Math. 18(1966), 1095–1104.

[125] H. K. Xu, Random fixed point theorems for nonlinear uniformly Lipschitzian mappings, Nonlinear Anal. 26(1996), 1301–1311.

[126] H. K. Xu and I. Beg, Measurability of fixed point sets of multivalued random operators, J. Math. Anal. Appl. 225(1998), 62–72.

[127] L. A. Zadeh, Fuzzy sets, Information and Control 8(1965), 338–353.

Index

Approximate quantities

collection of, 22 Approximate quantity, 22 Banach’s Contraction Mapping Principle, 1–4, 6, 21

converse of, 22 Bessaga, 22 Janos, 24 Leader, 24 Meyers, 24 topological variant, 28

extensions, 7, 13 Boyd and Wong, 7 Browder, 8 Caristi’s theorem, 14 for continuous mappings, 28 for local contractions, 27 for mappings with k_{∞} < 1, 11, 13 for random operators, 28 for set-valued mappings, 14–17, 25,, for topological vector spaces, 25 Geraghty, 9 Hybrid, 27 Matkowski, 8 Meir and Keeler, 9 Rakotch, 7 uniform space setting, 25

generalizations, 17, 19, 25 for fuzzy settings, 22, for probabilistic metric spaces, 20–21 Jachymski and Stein, 19 Walter, 18

Caristi’s theorem, 14 Contractive gauge function, 17 Convex

α-paraconvex, 26 metrically, 8

Distribution function, 20–21 Equivalent metrics, 11–13 Fuzzy set, 20–21

collection of, 21 Grade of membership, 21 Hausdorff

distance, 15, 22 metric, 15, 25

Lipschitz constant, 3–4, 10, 26 k_{∞}, 11–13 for set-valued mappings, 15–17

Mapping k-set contraction, 27 t-norm, 20–21 continuous, 21 closed graph, 25 condensing, 27 contractifiable, 24 contraction, 1, 3–5, 13, 18, 21, 26

generalized, 18,,,–19

local radial, 27

local, 27

on separable metric spaces, 27 on topological vector spaces, 25 topological, 28 contractive, 6, 9, 27

on probabilistic metric spaces, 21 fuzzy, 22 lipschitzian, 3, 5, 10–11 lower semicontinuous, 14 random operator, 28

random fixed point of, 28 set-valued contraction, 28

set-valued, 14, 28 contraction, 15–17, 26, fuzzy, 21

upper semicontinuous, 7,–8 Mappings

contraction

generalized, 26 Maximum Value Theorem, 5 Meir-Keeler condition, 9 Meir-Keeler condition, 9

Picard iterates, 2, 7, 17, 21 sequence, 1

error estimates, 1

rate of convergence of, 2, 13 Probabilistic metric space, 20–21

complete, 20–21

Hausdorff topology on, 20 Quasi-metrics, 27 Root Test for convergence, 11 Set

α-level, 21

fixed point, 16, 28 disconnected, 16 structure of, 26 Ultametric space, 27 Ultrametric space, 26

spherically complete, 26–27 Volterra integral equation, 2