ORDER-THEORETIC ASPECTS OF METRIC FIXED POINT THEORY

JACEK JACHYMSKI

Introduction

This chapter is intended to present connections between two branches of fixed point theory: The first, using metric methods which is the main subject of this Handbook, and the second, involving partial ordering techniques. We shall concentrate here on the following problem: Given a space with a metric structure (e.g., uniform space, metric space or Banach space) and a mapping satisfying some geometric conditions, define a partial ordering (depending on a structure of a space and/or a mapping) so that one of fundamental ordering principles – the Knaster-Tarski Theorem, Zermelo’s Theorem or the Tarski-Kantorovitch Theorem – could be applied to deduce the existence of a fixed point. We emphasize that all the above principles are independent of the Axiom of Choice (abbr., AC) so the above approach to metric fixed point theory is wholly constructive. It seems that such studies were initiated by H. Amann [5] and B. Fuchssteiner [33] in 1977. Subsequently, they were continued among others by S. Hayashi [37], R. Mańka ([59], [60]), R. Lemmert&P. Volkmann [58], A. Baranga [8], T. Büber&W. A. Kirk [20] and J. Jachymski ([41], [42], [43], [44], [46], [47]). On the other hand, some authors have also studied a reciprocal of the above problem: Given a partially ordered set and a mapping on it, define a metric depending on this order so that some theorems of metric fixed point theory could be applied. That was done recently by Y.-Z. Chen [22], who used Thompson’s [81] metric generated by an order. However, in this chapter, we shall not discuss these problems.

The outline of this chapter is as follows. In Section 1 we study consequences of the Knaster-Tarski Theorem. We present here Amann’s [5] proof of a fixed point theorem for diametric contractions, and Jachymski’s [42] proofs of the Angelov [6] theorem for j-contractive mappings on a uniform space, and of the Nadler [64] theorem for set-valued contractions. Section 2 is devoted to the famous theorem of Zermelo. We give here a proof of some version of Caristi’s [21] theorem, another proof of Nadler’s [64] theorem (via selection methods), and an extension of Zermelo’s Theorem with applications. We also establish a common fixed point theorem for two mappings on a partially ordered set. This result yields the fundamental theorem for nonexpansive mappings in a version of W. A. Kirk [49]. Section 3 deals with the Tarski-Kantorovitch Theorem. First we revisit here a proof of Angelov’s [6] theorem. Next we give an ordering proof of the Hutchinson-Barnsley ([38], [9]) theorem – a fundamental result in the theory of iterated function systems.

1991 Mathematics Subject Classification. Primary 06A06, 47H09, 47H10, 54C60, 54C65, 54E40, 54H25. Secondary 04A25, 39B72, 54D30, 54E15, 54E50.

Key words and phrases. Fixed point, partial ordering, progressive mapping, isotone mapping, chain, Axiom of Choice, metric space, uniform space, Banach space, Banach contraction, φ-contraction, set-valued contraction, nonexpansive mapping, iterated function system.

Finally, we wish to call the reader’s attention to yet another important ordering principle (not discussed in this chapter), due to Brézis&Browder [14]. In particular, this principle yields Caristi’s [21] fixed point theorem (see also Goebel&Kirk [35, pp. 13-14]), some results of the theory of nonlinear semigroups (also cf. I. Ekeland [30]) and the famous Nash-Moser theorem (cf. W. O. Ray [71]). For further literature in this topic, see, e.g., M. Altmann [4], M. Turinici ([84], [85]) and references therein.

1. The Knaster-Tarski Theorem

A partially ordered set is a pair (P, ⪯), where P is a nonempty set and ⪯ is a relation in P which is reflexive (p ⪯ p for all p ∈ P), weakly antisymmetric (for p, q ∈ P, p ⪯ q and q ⪯ p imply p = q) and transitive (for p, q, r ∈ P, p ⪯ q and q ⪯ r imply p ⪯ r). A nonempty subset C of P is said to be a chain if given p, q ∈ C, either p ⪯ q or q ⪯ p. If every chain in (P, ⪯) has a supremum, then (P, ⪯) is called chain-complete (see, e.g., Markowsky [61]). A mapping F : P ↦ P is said to be isotone or increasing if it preserves ordering, i.e., given p, q ∈ P, p ⪯ q implies that F p ⪯ F q.

We start with recalling the following theorem which is one of fundamental results in fixed point theory. We shall use the abbreviation ‘the K-T Theorem’ for ‘the Knaster-Tarski Theorem’.

Theorem 1 (Knaster-Tarski). Let (P, ⪯) be a partially ordered set in which every chain has a supremum. Assume that F : P ↦ P is isotone and there is an element p_{0} ∈ P such that p_{0} ⪯ F p_{0}. Then F has a fixed point.

This theorem was proved in 1927 by Knaster [51] for increasing - under set-inclusion - mappings, on and to the family of all subsets of a set. In 1939 Tarski extended Knaster’s result to increasing mappings on a complete lattice and he gave its applications in set theory and topology, but his result was unpublished until 1955 (cf. Tarski [80, footnote no. 2]). The version of the K-T Theorem presented here is due to Abian&Brown [2] and, independently, Pelczar [66], and was established in 1961. This is the reason for which, in a literature, this result is also called the Abian-Brown-Pelczar theorem (see, e.g., Schröder [72]). Following Dugundji&Granas [27, p. 14] we incline, however, to the opinion that this theorem should be attributed to Knaster and Tarski, because Knaster initiated a development of fixed point theory on ordered structures, whereas Tarski not only extended Knaster’s ideas, but he also found important applications of theorems of this type in other areas of mathematics. Finally, we wish to notice that the K-T Theorem is also called the Amann theorem (cf. Zeidler [89, p. 506]) which is, however, causeless.

By substituting an inverse ordering ⪰ for ⪯ in Theorem 1, we obtain the following dual version of the K-T Theorem.

Theorem 2. Let (P, ⪯) be a partially ordered set in which every chain has an infimum. Assume that F : P ↦ P is isotone and there is an element p_{0} ∈ P such that F p_{0} ⪯ p_{0}. Then F has a fixed point.

In the sequel we shall show how Theorems 1 and 2 can be used to derive some results of metric fixed point theory. We start with presenting Amann’s [5] proof (see also Zeidler [89, p. 512]) of a fixed point theorem for the so-called diametric contractions. In fact, we shall extend his argument by considering a more general class of mappings: A selfmap f of a bounded metric space is said to be a diametric φ-contraction if there is a non-decreasing function φ : ℝ_{+} ↦ ℝ_{+} (ℝ_{+} denotes the set of all nonnegative reals) such that lim_{n→∞} φ^{n}(t) = 0 for all t > 0 (see Matkowski [62] or Dugundji&Granas [27, p. 12]) and

diam f(A) ≤ φ(diam A)  (1)

for all nonempty, closed and f-invariant subsets A of X.

A more realistic special case here is the following Walter’s contraction [86], i.e., a mapping f which satisfies the inequality

d(fx, fy) ≤ φ (diam (O_{f}(x) ∪ O_{f}(y))) for all x, y ∈ X,

where O_{f}(x) := {f^{n−1}x : n ∈ ℕ} is an orbit of f at a point x and a function φ is nondecreasing, right continuous and such that φ(t) < t for t > 0 (then lim_{n→∞} φ^{n}(t) = 0; cf. Browder [16]). That such an f satisfies (1), follows immediately from the fact that x ∈ A implies O_{f}(x) ⊆ A if A is f-invariant.

Theorem 3. Let (X, d) be a complete bounded metric space and f be a diametric φ-contraction on X. Then f has a unique fixed point.

We shall precede a proof of Theorem 3 with establishing some new related results in a more general setting. Let (X, τ) be a topological space and f be an arbitrary (not necessarily continuous) selfmap of X. Let cl denote the closure operator. Define

C_{f}(X) := {A ⊆ X : A ≠ ∅, A = cl A and f(A) ⊆ A},

and for A, B ∈ C_{f}(X),

A ⪯_{∗} B if A ⊆ cl f(B).

Proposition 1. The relation ⪯_{∗} is weakly antisymmetric and transitive in C_{f}(X).

Proof. If A ⪯_{∗} B, then A ⊆ cl f(B) ⊆ cl B = B so A ⊆ B. If, moreover, B ⪯_{∗} A, then B ⊆ A. Consequently, we get that A = B.

Now assume that A ⪯_{∗} B and B ⪯_{∗} C. Then A ⊆ B and B ⊆ cl f(C) which yields A ⊆ cl f(C), i.e., A ⪯_{∗} C. □

For A, B ∈ C_{f}(X), define

A ⪯ B if A = B or A ⊆ cl f(B).

Then Proposition 1 let us infer that ⪯ is a partial ordering in C_{f}(X) which is said to be Amann’s ordering (cf. Zeidler [89, p. 512]). Following Amann we define a mapping F by

F (A) := cl f(A) for A ∈ C_{f}(X).

Proposition 2. F is an isotone selfmap of C_{f}(X) with respect to Amann’s ordering ⪯. Moreover, F (A) ⪯ A for all A ∈ C_{f}(X).

Proof. To show that F (A) ∈ C_{f}(X) for A ∈ C_{f}(X), it suffices to prove that F (A) is f-invariant. Since cl f(A) ⊆ cl A = A, we get f(F (A)) ⊆ f(A) ⊆ F (A). To prove the monotonicity of F we may assume, without loss of generality, that A ⪯_{∗} B. Then A ⊆ cl f(B) so f(A) ⊆ f(cl f(B)) = f(F (B)) and hence cl f(A) ⊆ cl f(F (B)), i.e., F (A) ⪯_{∗} F (B).

Finally, the trivial inclusion cl f(A) ⊆ cl f(A) means that F (A) ⪯_{∗} A; in particular, F (A) ⪯ A. □

Proposition 3. Let C be a chain in (C_{f}(X), ⪯). Then C has an infimum if and only if the set A_{0} := ⋂_{C∈C} cl f(C) is nonempty. Moreover, if C has no minimum and A_{0} ≠ ∅, then inf C = A_{0}.

Proof. We start with part ‘only if’. Let C_{0} := inf C. If C ∈ C and C_{0} ≠ C, then C_{0} ⪯_{∗} C, i.e., C_{0} ⊆ cl f(C). Hence if C_{0} ∉ C, then C_{0} ⊆ A_{0}. If C_{0} ∈ C, then we may infer that A_{0} = cl f(C_{0}) since C_{0} ⊆ C for C ∈ C and thus cl f(C_{0}) ⊆ cl f(C) for such C. In both cases A_{0} is nonempty.

To prove part ‘if’, assume that A_{0} ≠ ∅. Then A_{0} ∈ C_{f}(X) since it is closed and

f(A_{0}) ⊆ ⋂_{C∈C C C} f(cl f(C)) ⊆ ⋂_{C∈C C C} f(C) ⊆ A_{0}.

By the definition of A_{0}, A_{0} ⪯_{∗} C for all C ∈ C, i.e., A_{0} is a lower bound of C. Suppose, on the contrary, that A_{0} is not the greatest lower bound of C. Then there is B ∈ C_{f}(X) such that B ≠ A_{0}, A_{0} ⪯_{∗} B and B ⪯ C for all C ∈ C. Without loss of generality we may assume that C has no minimum. Then B ≠ C so B ⪯_{∗} C for all C ∈ C. Therefore,

A_{0} ⊆ cl f(B) ⊆ B and B ⊆ A_{0} for all C ∈ C

which yields that A_{0} = B, a contradiction. Thus A_{0} = inf C if C has no minimum. In each case C has an infimum. □

The following example shows that we cannot drop the assumption ‘C has no minimum’ in the last statement of Proposition 3.

Example 1. Set X := [0, 1], fx := x/2 for x ∈ X and endow X with the Euclidean metric. Define C := {X, f(X)}. Then C is a chain in C_{f}(X) and f(X) = min C. However, A_{0} = f^{2}(X) ≠ min C.

As an immediate consequence of Propositions 1, 2 and 3, and Theorem 2, we obtain the following

Theorem 4. Let (X, τ) be a topological space and f be a selfmap of X (not necessarily continuous). If for every chain C in C_{f}(X) endowed with Amann’s ordering

⋂_{C∈C C C} cl f(C) ≠ ∅,  (2)

then there exists a set A_{∗} ∈ C_{f}(X) such that cl f(A_{∗}) = A_{∗}.

Proof of Theorem 3. We shall apply Theorem 2. Let C be a chain in (C_{f}(X), ⪯). We show that (2) holds. If C has a minimum, then by Proposition 3, we are done. So assume C has no minimum. Since for A, B ∈ C_{f}(X), A ⪯ B implies that A ⊆ B, C is also a chain with respect to set-inclusion. Therefore, given C_{1}, ⋯, C_{n} ∈ C we have

∅ ≠ cl f ( ⋂_{i=1}^{n} C_{i}) ⊆ cl ⋂_{i=1}^{n} f(C_{i}) ⊆ ⋂_{i=1}^{n} cl f(C_{i})

so the family {cl f(C) : C ∈ C} has the finite intersection property. We show that given ε > 0 there is a set C ∈ C with diam f(C) < ε and then the Kuratowski theorem (see, e.g., Engelking [31, Theorem 4.3.10]) let us infer that (2) holds. By hypothesis, given ε > 0, there is a p ∈ ℕ such that φ^{p}( diam X) < ε. Without loss of generality we may assume that p ≥ 2. Since C has no minimum, there exist sets C_{1}, ⋯, C_{p} ∈ C such that C_{p} ⪯_{∗} ⋯ ⪯_{∗} C_{1}, i.e., C_{i} ⊆ cl f(C_{i−1}) for i = 2, ⋯, p. Hence and by (1) we get

diam C_{p} ≤ diam f(C_{p−1}) ≤ φ(diam C_{p−1}) ≤ ⋯ ≤ φ^{p−1}(diam C_{1})

which yields that diam f(C_{p}) ≤ φ^{p}(diam X) < ε. By Theorem 4, there is an A_{∗} ∈ C_{f}(X) for which cl f(A_{∗}) = A_{∗}. By (1)

diam f(A_{∗}) ≤ φ(diam A_{∗}) = φ(diam f(A_{∗}))

which implies that f(A_{∗}) is a singleton since φ(t) < t for t > 0 (cf. [27, p. 12]). Therefore A_{∗} = {a_{∗}} for some a_{∗} ∈ X, and then a_{∗} = fa_{∗} since A_{∗} is f-invariant. To prove the uniqueness assume that a_{1}, a_{2} are fixed points of f. Then the set A := {a_{1}, a_{2}} belongs to C_{f}(X) and f(A) = A. Hence and by (1), we may conclude that diam A = 0, i.e., a_{1} = a_{2}. □

Remark 1. The above proof depends on the countable form of the AC since we used the Kuratowski theorem.

Remark 2. We emphasize that in the above proof a contractive condition is used only to show that every chain has an infimum. (Compare with Remarks 4 and 5.)

The above proof also shows that the K-T theorem implies the Banach Contraction Principle for mappings on a bounded metric space. In the sequel we shall give another proof using a completely different partial ordering introduced by Jachymski [42]. The advantage of this proof is that the boundedness condition can be dropped here and, moreover, it shows the K-T theorem also yields some extensions of the Contraction Principle for mappings on uniform spaces, given by K.-K. Tan [78], Tarafdar [79], D. H. Tan [77] and Angelov [6].

Let (X, P) be a complete Hausdorff uniform space with the uniformity generated by a family P of pseudometrics, P = {p_{α} : α ∈ A}, where A is an index set (see, e.g., Engelking [31]). Let ℝ_{+}^{A} denote the family of all nonnegative real functions on the set A. We define the following relation in the Cartesian product X × ℝ_{+}^{A}:

(x, φ) ⪯ (y, ψ) iff p_{α}(x, y) ≤ φ(α) − ψ(α) for all α ∈ A,  (3)

where x, y ∈ X and φ, ψ ∈ ℝ_{+}^{A}. Clearly this relation is reflexive. Since the family P is separated because of the Hausdorff condition, the above relation is antisymmetric. It is also transitive which is a simple consequence of the triangle inequality. Thus (X × ℝ_{+}^{A}, ⪯) is a partially ordered set. Let us notice that if A is a singleton {d}, i.e., (X, d) is a metric space, then the above definition takes the form

(x, a) ⪯ (y, b) iff d(x, y) ≤ a − b,  (4)

where a, b ∈ ℝ_{+}. This ordering was introduced by Ekeland [29] in a proof of his variational principle. On the other hand, recently, Frigon [32] slightly modified definition (4) and she used such an ordering to prove that the property of having a fixed point is invariant by homotopy for set-valued contractions.

Now the completeness of (X, P) is crucial in a proof of the following

Proposition 4. Every chain C in (X × ℝ_{+}^{A}, ⪯) has a supremum.

Proof. We use a similar idea as in Kirk [50]. If σ ∈ C, then σ = (x_{σ}, φ_{σ}) for some x_{σ} ∈ X and φ_{σ} ∈ ℝ_{+}^{A}. Consider the net {(x_{σ}, φ_{σ})}_{σ∈C}. Obviously this net is increasing, i.e.,

if σ_{1} ⪯ σ_{2}, then p_{α}(x_{σ_{1}}, x_{σ_{2}}) ≤ φ_{σ_{1}}(α) − φ_{σ_{2}}(α) for all α ∈ A. (5)

Therefore the net {φ_{σ}(α)}_{σ∈C} is decreasing in ℝ_{+}, hence convergent. Denote

φ_{0}(α) := lim_{σ∈C} φ_{σ}(α) for all α ∈ A.

By (5), since for each α ∈ A {φ_{σ}(α)}_{σ∈C} is Cauchy, so is the net {x_{σ}}_{σ∈C}. By completeness, there is an x_{0} ∈ X such that x_{0} = lim_{σ∈C} x_{σ}. Taking the limit in (5) with respect to σ_{2} yields

p_{α}(x_{σ}, x_{0}) ≤ φ_{σ}(α) − φ_{0}(α) for α ∈ A and σ ∈ C

which means the pair (x_{0}, φ_{0}) is an upper bound of C. If a pair (x, φ) is another upper bound, i.e., for all α ∈ A and σ ∈ C, p_{α}(x_{σ}, x) ≤ φ_{σ}(α)−φ(α), then, taking the limit with σ, we obtain that p_{α}(x_{0}, x) ≤ φ_{0}(α) − φ(α) for all α ∈ A, i.e., (x_{0}, φ_{0}) ⪯ (x, φ). That means (x_{0}, φ_{0}) is the least upper bound of C. □

Now let f be a selfmap of a uniform space (X, P) and j be a selfmap of the index set A. Following D. H. Tan [77] and Angelov [6] f is said to be a j-Lipschitzian mapping if

p_{α}(fx, fy) ≤ h_{α} p_{j(α)}(x, y) for all x, y ∈ X and α ∈ A,

where h_{α} ≥ 0. If, moreover, h_{α} < 1 for all α ∈ A, then we say that f is j-contractive. The introduction of a mapping j is motivated by applications in the theory of neutral functional differential equations (cf. Angelov [6], [7] and Tsachev&Angelov [82]). Define

F (x, φ) := (fx, h · (φ ∘ j)) for all (x, φ) ∈ X × ℝ_{+}^{A},  (6)

where (h · (φ ∘ j))(α) := h_{α} φ(j(α)) for α ∈ A. Clearly F is a selfmap of X × ℝ_{+}^{A}.

Proposition 5. Let f be a j-Lipschitzian selfmap of (X, P). Let F be an associated map on X × ℝ_{+}^{A} defined by (6). Then F is isotone with respect to the ordering ⪯ defined by (3).

Proof. Let (x, φ) ⪯ (y, ψ). Then for all α ∈ A, we have

p_{α}(fx, fy) ≤ h_{α} p_{j(α)}(x, y) ≤ h_{α} φ(j(α)) − h_{α} ψ(j(α))

which means that F (x, φ) ⪯ F (y, ψ). □

We show that the K-T Theorem yields the following result obtained independently by K.-K. Tan [78] and Tarafdar [79]. In particular, the Banach Contraction Principle is obtainable via the K-T Theorem.

Theorem 5 (Tan, Tarafdar). Let f be a j-contractive selfmap of (X, P) with j :=id, the identity mapping on A. Then f has a fixed point.

Proof. We consider the ordering ⪯ in X ×ℝ_{+}^{A} and the mapping F, defined by (3) and (6), respectively. We show that there exists a pair (x_{0}, φ_{0}) such that (x_{0}, φ_{0}) ⪯ F (x_{0}, φ_{0}). Let x_{0} ∈ X be chosen arbitrarily. It suffices to set

φ_{0}(α) := p_{α}(x_{0}, fx_{0})/(1 − h_{α}) for all α ∈ A.

By Propositions 4 and 5, the rest assumptions of the K-T Theorem are also satisfied. □

We emphasize that the above proof does not depend on the AC. It does not use any iterative methods either.

Now we consider the following extension of the above theorem, due to Angelov [6] (see also D. H. Tan [77]).

Theorem 6 (Angelov). Let f be a j-contractive selfmap of (X, P) such that

sup{h_{j^{n−1}(α)} : n ∈ ℕ} < 1 for all α ∈ A.

Assume that there is an x_{0} ∈ X such that

sup{p_{j^{n−1}(α)}(x_{0}, fx_{0}) : n ∈ ℕ} ≤ C_{α} for all α ∈ A,

where C_{α} ≥ 0. Then f has a fixed point.

To derive this result from the K-T Theorem applied to the mapping F on (X × ℝ_{+}^{A}, ⪯), it is enough to show in view of Propositions 4 and 5 that there exists a function φ_{0} ∈ ℝ_{+}^{A} such that (x_{0}, φ_{0}) ⪯ F (x_{0}, φ_{0}). This problem leads to the following functional inequality

φ(α) ≥ g(α) + h(α) φ(j(α)),  (7)

where g(α) := p_{α}(x_{0}, fx_{0}). This inequality can be considered on any jinvariant subsets of A, in particular, on orbits of the mapping j and we just start with such a case.

Lemma 1. Under the assumptions of Theorem 6, given β ∈ A, inequality (7) has a solution φ_{β} : O_{j}(β) ↦ ℝ_{+}.

Proof. Let β ∈ A and ĥ_{β} := sup{h_{α} : α ∈ O_{j}(β)}. Then ĥ_{β} < 1. We shall use a similar argument as in Kuczma, Choczewski&Ger [54, p. 149]. Let Φ_{β} denote the family of all functions φ : O_{j}(β) ↦ ℝ_{+} which are bounded. Equip Φ_{β} with the sup norm so that it becomes a complete metric space, and define an operator T_{β} by

T_{β} := g|_{O_{j}(β)} + ĥ_{β} (φ ∘ j|_{O_{j}(β)}) for all φ ∈ Φ_{β}.

Since g|_{O_{j}(β)} is bounded, T_{β} is a selfmap of Φ_{β}. Moreover, given φ_{1}, φ_{2} ∈ Φ_{β}, we easily get that

||T_{β}φ_{1} − T_{β}φ_{2}|| ≤ ĥ_{β} ||φ_{1} − φ_{2}||.

Now we are allowed to apply the Contraction Principle since it is subsumed by the K-T Theorem as shown earlier. Thus T_{β} has a fixed point φ_{β} and then φ_{β} is also a desired solution of (7) since ĥ_{β} ≥ h_{α} for α ∈ O_{j}(β). □

To show that (7) has a global solution, we shall apply a Hahn-Banach type argument. Instead of functionals on linear subspaces, we shall consider solutions of (7) on j-invariant subsets of A. Then orbits of a mapping j (i.e., minimal, with respect to the set-inclusion, j-invariant subsets of A) correspond to one-dimensional subspaces (i.e., minimal, with respect to the set-inclusion, nontrivial linear subspaces). Thus a counterpart of Lemma 1 is a result saying that for each one-dimensional subspace, there exists a nonvanishing continuous linear functional on it. Our proof depends on the AC because of a use of Zorn’s Lemma in it. We slightly modify a formulation of Jachymski [42, Lemma 3] and we simplify the last part of its proof.

Proposition 6. Let j be a selfmap of an abstract set A, g : A ↦ ℝ_{+} and h : A ↦ ℝ_{+}. Let A_{0} be a j-invariant subset of A and φ_{0} : A_{0} ↦ ℝ_{+} be a solution of (7). If for each β ∈ A, functional inequality (7) has a solution φ_{β} : O_{j}(β) ↦ ℝ_{+}, then there exists an extension φ̃_{0} : A ↦ ℝ_{+} of φ_{0}, satisfying (7) on A.

Proof. Consider the following family of solutions of (7):

Φ := {φ : D_{φ} ↦ ℝ_{+} | A_{0} ⊆ D_{φ} ⊆ A, j(D_{φ}) ⊆ D_{φ}, φ|_{A_{0}} = φ_{0}
and φ satisfies (7) on D_{φ}}.

We equip Φ with the partial ordering ⪯:

φ_{1} ⪯ φ_{2} iff D_{φ_{1}} ⊆ D_{φ_{2}} and φ_{2}|_{D_{φ_{1}}} = φ_{1}.

If C is a chain in (Φ, ⪯), then there is a unique function ψ : D_{ψ} ↦ ℝ_{+} such that D_{ψ} = ⋃_{φ∈C} D_{φ} and ψ|_{D_{φ}} = φ for all φ ∈ C. By Zorn’s Lemma, there exists a maximal element φ_{∗} : D_{∗} ↦ ℝ_{+} in Φ. It suffices to prove that D_{∗} = A. Suppose, on the contrary, that there is an α_{0} ∈ A \ D_{∗}. We show that O_{j}(α_{0}) ∩ D_{∗} ≠ ∅. Suppose that these sets are disjoint. By hypothesis, there exists a solution φ_{α_{0}} : O_{j}(α_{0}) ↦ ℝ_{+} of (7). Clearly the set O_{j}(α_{0})∪D_{∗} is j-invariant and the function φ_{α_{0}} ∪ φ_{∗} is well-defined, it belongs to Φ and it extends φ_{∗} which yields a contradiction. Thus we may define an integer

m := min{n ∈ ℕ : j^{n}(α_{0}) ∈ D_{∗}}.

Then j^{m−1}(α_{0}) ∉ D_{∗}. Set D := D_{∗} ∪ {j^{m−1}(α_{0})}. Then j(D) ⊆ D_{∗} ⊂ D. We define a function φ : D ↦ ℝ_{+} as follows:

φ|_{D_{∗}} := φ_{∗} and φ(j^{m−1}(α_{0})) := g(α_{0}) + h(α_{0}) φ_{∗}(j^{m}(α_{0})).

It is easily seen that φ ∈ Φ and φ_{∗} ⪯ φ ≠ φ_{∗}, a contradiction. Therefore we may infer that φ_{∗} is a global solution of (7) and it suffices to set φ̃_{0} := φ_{∗}. □

Remark 3. Proposition 6 extends [42, Lemma 3] in which a function h is assumed to take values from [0, 1].

Corollary 1. Under the assumptions of Theorem 6, functional inequality (7), with g(α) := p_{α}(x_{0}, fx_{0}) and h(α) := h_{α}, has a solution on A. Hence the K-T Theorem implies Angelov’s theorem.

Proof. Let α_{0} ∈ A. By Lemma 1, there is a solution φ_{α_{0}} : O_{j}(α_{0}) ↦ ℝ_{+} of (7). By Lemma 1 and Proposition 6, φ_{α_{0}} can be extended to a global solution φ̃_{α_{0}} of (7) on A. Then (x_{0}, φ̃_{α_{0}}) ⪯ F (x_{0}, φ̃_{α_{0}}) and by Propositions 4 and 5, all the assumptions of the K-T Theorem are satisfied. Thus there exists a fixed point (x_{∗}, φ_{∗}) of F and then x_{∗} = fx_{∗}. □

Remark 4. We emphasize that in the above proof a contractive condition is used only to show the existence of an element b ∈ X × ℝ_{+}^{A} such that b ⪯ F b (compare with Remarks 2 and 5).

Finally, we want to discuss relations between theorems of Angelov and Tan-Tarafdar. In particular, Czesaw Bessaga [11] posed a question whether the latter theorem yields Angelov’s result. He suggested that given a jcontractive (with respect to P) mapping f, it could be possible to find another family P’ of pseudometrics such that f would satisfy the assumptions of the Tan-Tarafdar theorem on a uniform space (X, P′). However, the following example settles in the negative the above question even if a space (X, P) is metrizable.

Example 2. Let X := C(ℝ_{+}^{o}), the set of all real continuous functions on the open interval ℝ_{+}^{o} := (0, ∞). Let K(ℝ_{+}^{o}) denote the family of all nonempty compact subsets of ℝ_{+}^{o}. Endow X with the uniform structure generated by the family of pseudonorms {p_{A} : A ∈ K(ℝ_{+}^{o})}, where p_{A}(φ) := max_{t∈A} |φ(t)| for φ ∈ X. Let a, b be positive reals such that 0 < a < 1 < b. Define an operator F by

(F φ)(t) := a φ(bt) for φ ∈ X and t > 0.

Then F is a linear selfmap of X and p_{A}(F φ) = a p_{j(A)}(φ), where j(A) := b A. Thus F is a j-contractive mapping with h_{A} := a. It can be verified that the condition sup{p_{j^{n}(A)}(φ_{0} − F φ_{0}) : n ∈ ℕ} < ∞ is satisfied if, e.g., φ_{0} is a nonnegative and nonincreasing function. Thus the assumptions of Angelov’s theorem are fulfilled. Suppose, on the contrary, that there is a family P’ of pseudometrics inducing some Hausdorff uniform structure on X and such that F satisfies the assumptions of the Tan-Tarafdar theorem on (X, P′). Then F has a unique fixed point. On the other hand, it is easily seen that the set of all fixed points of F coincides with the family of all solutions of the Schröder functional equation

φ(t/b) = a φ(t) for t > 0.

The latter family, however, is not a singleton according to, e.g., the Kordylewski&Kuczma theorem (cf. [53, Theorem 2.1]). This yields a contradiction.

In the sequel we shall derive Nadler’s [64] extension of the Contraction Principle from a set-valued version of the K-T Theorem, due to Smithson [73]. A set-valued mapping F on a partially ordered set (P, ⪯) (that is, F : P ↦ 2^{P} \ {∅}) is said to be order preserving if given p_{1}, p_{2} ∈ P with p_{1} ⪯ p_{2}, for each r_{1} ∈ F p_{1}, there is an r_{2} ∈ F p_{2} such that r_{1} ⪯ r_{2}.

Theorem 7 (Smithson). Let (P, ⪯) be a partially ordered set in which every chain has a supremum. Let F be an order preserving set-valued mapping on P such that given a chain C ⊆ P and an isotone single-valued mapping ω : C ↦ P satisfying ω(c) ∈ F c for all c ∈ C, there exists d ∈ F (sup C) such that ω(c) ⪯ d for all c ∈ C. If there exist elements p_{0} ∈ P and r_{0} ∈ F p_{0} such that p_{0} ⪯ r_{0}, then F has a fixed point.

It is easily seen that if F is an isotone single-valued selfmap of a chaincomplete (P, ⪯) with p_{0} ⪯ F p_{0} for some p_{0} ∈ P, then F satisfies the assumptions of the above theorem. We also emphasize that whereas the K-T Theorem does not depend on the AC, Smithson’s [73] proof relies on the AC.

Following Jachymski [42], we shall give a new proof of Nadler’s [64] theorem using partial ordering techniques. Let (X, d) be a metric space and Cl(X) denote the family of all nonempty closed subsets of X (not necessarily bounded). For A, B ∈Cl(X), set

H(A, B) := max{sup{d(a, B) : a ∈ A}, sup{d(b, A) : b ∈ B}},

where d(a, B) := inf{d(a, b) : b ∈ B}. Then H is said to be a generalized Hausdorff metric since it may have infinite values. We recall a more general form of Nadler’s theorem established by Covitz&Nadler [23].

Theorem 8 (Nadler). Let (X, d) be a complete metric space and f : X ↦ Cl (X). Assume there is an h ∈ [0, 1) such that

H(fx, fy) ≤ h d(x, y) for all x, y ∈ X.

Then f has a fixed point.

Proof. Let P := X × ℝ_{+} and endow P with Ekeland’s ordering (4). By Proposition 4, every chain in P has a supremum. Define a set-valued mapping F on P by

F (x, a) := fx × {h a} for (x, a) ∈ P.

We shall show that F satisfies the assumptions of Smithson’s theorem. Without loss of generality we may assume, eventually replacing h by (1 + h)/2, that

H(fx, fy) < d(x, y) for all x, y ∈ X with x ≠ y.

We show that F is order preserving. Let (x_{1}, a_{1}) ⪯ (x_{2}, a_{2}) and (y_{1}, b_{1}) ∈ F (x_{1}, a_{1}), i.e., y_{1} ∈ fx_{1} and b_{1} = h a_{1}. Let b_{2} := h a_{2}. If x_{1} = x_{2}, then set y_{2} := y_{1}. If x_{1} ≠ x_{2}, then

d(y_{1}, fx_{2}) ≤ H(fx_{1}, fx_{2}) < h d(x_{1}, x_{2}) ≤ h (a_{1} − a_{2}).

Hence there exists y_{2} ∈ fx_{2} such that d(y_{1}, y_{2}) ≤ h (a_{1} − a_{2}). In both cases (y_{1}, b_{1}) ⪯ (y_{2}, b_{2}).

Now let C be a chain in P and ω : C ↦ P an isotone mapping such that ω(σ) ∈ F σ for σ ∈ C. Then σ = (x_{σ}, a_{σ}) and the net {(x_{σ}, a_{σ})}_{σ∈C} is increasing. Hence following the proof of Proposition 4, we may infer by completeness of (X, d) that both nets {x_{σ}}_{σ∈C} and {a_{σ}}_{σ∈C} are convergent, say to x_{0} ∈ X and a_{0} ∈ ℝ_{+}, respectively. Moreover, (x_{0}, a_{0}) is the supremum of C. Denote (y_{σ}, b_{σ}) := ω(x_{σ}, a_{σ}). Then b_{σ} = h a_{σ} and y_{σ} ∈ fx_{σ}. Since ω is isotone and the net {(x_{σ}, a_{σ})}_{σ∈C} is increasing, so is the net {(y_{σ}, b_{σ})}_{σ∈C}. Again we may infer that the net {y_{σ}}_{σ∈C} converges to some y_{0} ∈ X and (y_{σ}, b_{σ}) ⪯ (y_{0}, h a_{0}), i.e., ω(x_{σ}, a_{σ}) ⪯ (y_{0}, h a_{0}). We only need to show that (y_{0}, h a_{0}) ∈ F (x_{0}, a_{0}), i.e., y_{0} ∈ fx_{0}. For σ ∈ C, we have

\begin{matrix}d(y_{0}, fx_{0}) ≤ d(y_{0}, y_{σ}) + d(y_{σ}, fx_{0}) ≤ d(y_{0}, y_{σ}) + H(fx_{σ}, fx_{0}) \\ ≤ d(y_{0}, y_{σ}) + h d(x_{0}, x_{σ}). \end{matrix}

Hence taking the limit with σ, we obtain that d(y_{0}, fx_{0}) = 0. Since the set fx_{0} is closed, we infer that y_{0} ∈ fx_{0}.

Finally, we show that there exist (x_{0}, a_{0}) ∈ P and (y_{0}, b_{0}) ∈ F (x_{0}, a_{0}) such that (x_{0}, a_{0}) ⪯ (y_{0}, b_{0}). Choose arbitrarily x_{0} ∈ X and y_{0} ∈ fx_{0}. It suffices to set

a_{0} := d(x_{0}, y_{0})/(1 − h) and b_{0} := h a_{0}.

Thus by Smithson’s theorem, there exists (x_{∗}, a_{∗}) ∈ P such that (x_{∗}, a_{∗}) ∈ F (x_{∗}, a_{∗}), and then x_{∗} is a fixed point of f. □

2. Zermelo’s fixed point theorem

The following fixed point theorem is of great importance.

Theorem 9 (Zermelo). Let (P, ⪯) be a partially ordered set in which every chain has a supremum. Assume that F : P ↦ P is such that

p ⪯ F p for all p ∈ P.  (8)

Then F has a fixed point.

A mapping F satisfying (8) is said to be progressive.

The above theorem is attributed to Zermelo (see, e.g., Dunford&Schwartz [28, p. 5]), though it does not appear explicite in any of his papers. However, a proof of it can be derived from Zermelo’s [90], [91] proofs of the wellordering principle. This observation is due to Bourbaki [12], who was the first to formulate the theorem in the above form. (Actually, Bourbaki used well-ordered subsets of P instead of chains so his assumption is formally weaker than that of Theorem 9, however, it is more convenient for us to work with chains as will be seen in the sequel; in particular, cf. Remark 7.) The proof of Zermelo’s Theorem does not depend on the AC. If, however, we allow to use Zorn’s Lemma, then a proof is straightforward; moreover, the assumption on (P, ⪯) can be weakened then to ‘every chain has an upper bound’. This is Kneser’s [52] fixed point theorem which turns out to be equivalent to the AC as shown by Abian [1]. Let us notice that, in a literature, Zermelo’s Theorem is sometimes called the Bourbaki-Kneser theorem (cf. Zeidler [89, p. 504]).

The fact that Zermelo’s Theorem is independent of the AC is important for a constructive approach to metric fixed point theory. It seems that the basic result in this direction is due to Fuchssteiner [33]. He showed that the fundamental fixed point theorem for nonexpansive mappings can be derived from Zermelo’s Theorem, though Kirk’s [49] original proof of it uses Zorn’s Lemma. Fuchssteiner also observed that Zermelo’s Theorem yields the Banach Contraction Principle and some extensions of it for mappings on a bounded metric space.

Our first purpose is to present a result of Jachymski [44] which improves the latter result of Fuchssteiner by omitting the boundedness condition of a space considered. Moreover, it turns out that also some version of Caristi’s [21] theorem is subsumed directly by Zermelo’s theorem.

Let (X, d) be a metric space and φ be a real function on X. We consider the following relation ⪯_{φ} introduced by Brøndsted [18]: given x, y ∈ X,

x ⪯_{φ} y iff d(x, y) ≤ φ(x) − φ(y).

Proposition 7. The relation ⪯_{φ} is a partial ordering in X. If φ is bounded from below and (X, d) is complete, then every chain C is convergent in (X, d); moreover,

(a) lim C is an upper bound of C in (X, ⪯_{φ}) if φ is lower semicontinuous;

(b) lim C is a supremum of C if φ is continuous.

Proof. That ⪯_{φ} is a partial ordering is straightforward; in particular, the transitivity of ⪯_{φ} follows from the triangle inequality. Let C be a chain. Consider a net {x_{σ}}_{σ∈C}, where x_{σ} := σ. Obviously this net is increasing, i.e.,

if σ_{1} ⪯ σ_{2}, then d(x_{σ_{1}}, x_{σ_{2}}) ≤ φ(x_{σ_{1}}) − φ(x_{σ_{2}}).  (9)

Hence φ(x_{σ_{2}}) ≤ φ(x_{σ_{1}}), i.e., the net {φ(x_{σ})}_{σ∈C} is nonincreasing and thus it is convergent if φ is bounded below. Hence and by (9), we may infer that {x_{σ}}_{σ∈C} satisfies Cauchy’s condition so it converges to some x_{0} ∈ X.

To prove statement (a) it suffices to take the limit with σ_{2} in (9). Then we obtain that

d(x_{σ_{1}}, x_{0}) ≤ φ(x_{σ_{1}}) − lim_{σ_{2}∈C} φ(x_{σ_{2}}) ≤
φ(x_{σ_{1}}) − lim_{x→x_{0}} inf φ(x) ≤ φ(x_{σ_{1}}) − φ(x_{0}).

Hence x_{0} is an upper bound of C. Finally, assume that φ is continuous. Let x′_{0} be an upper bound of C, i.e.,

d(x_{σ}, x′_{0}) ≤ φ(x_{σ}) − φ(x′_{0}) for all σ ∈ C.

Taking here the limit with σ ∈ C yields that x_{0} ⪯_{φ} x′_{0} which means x_{0} is the least upper bound of C. □

One could conjecture that, under the assumptions of Proposition 7 (a), if a chain C has a supremum, then it coincides with lim C. The following example shows that this is not the case.

Example 3. Let X := [0, 1] be endowed with the Euclidean metric. Define a function φ on X by

φ(0) := 0, φ(1) := 1 and φ(x) := x + 2 for x ∈ (0, 1).

Then φ is nonnegative and lower semicontinuous. Since φ(x) ≥ x for all x ∈ X and φ(0) = 0, 0 is the greatest element in (X, ⪯_{φ}). It is easily seen that the sequence (1/(n + 1))_{n=1}^{∞} is ⪯_{φ}-increasing. Hence C := {1/(n + 1) : n ∈ ℕ} is a chain. Clearly lim C = 0. We show that the only upper bounds of C are 0 and 1. Let x_{0} ∈ (0, 1). Then

φ(1/(n + 1)) − φ(x_{0}) = 1/(n + 1) − x_{0} < 0

for sufficiently large n so x_{0} is not an upper bound of C. Moreover, 1/(n + 1) ⪯_{φ} 1 ⪯_{φ} 0 for all n ∈ ℕ. Therefore we may infer that sup C = 1 ≠ lim C.

Theorem 10 (Caristi). Let (X, d) be a complete metric space, φ : X ↦ ℝ_{+} be a lower semicontinuous function and f be a selfmap of X (not necessarily continuous) such that

d(x, fx) ≤ φ(x) − φ(fx) for all x ∈ X.  (10)

Then f has a fixed point.

Caristi’s [21] original proof of this result is sophisticated: It is based on an iterative use of a transfinite induction. An elegant proof involving Brøndsted’s ordering ⪯_{φ} was given by Kirk [50]. Actually, part (a) of Proposition 7 is due to him. Then he applied Zorn’s Lemma to get a maximal element x_{∗} which is a fixed point of f since, by (10), x_{∗} ⪯_{φ} fx_{∗}. Another short proof was given by Pasicki [65]. In fact, his proof is based on the Hausdorff maximal chain theorem. A constructive proof of Caristi’s theorem was a subject of a paper of Browder [17], but, in fact, he used the countable form of the AC as observed by Bell [10]. Another constructive approach was due to Penot [67], [69], who proved the maximality principle (i.e., a theorem on the existence of maximal elements in (X, ⪯_{φ})) with a help of the Cantor intersection theorem. Then a question has arisen whether the maximality principle can be proved without using any weaker forms of the AC. This problem has been settled in the negative by Brunner [19], who showed that this principle is equivalent to the Axiom of Dependent Choices (DC). (Incidentally, the maximality principle is equivalent to Ekeland’s [29] principle.) Despite this fact, it turns out that Caristi’s theorem can be proved wholly without any choice as shown by Mańka [59], [60]. On the other hand, we have the following

Proposition 8. Zermelo’s Theorem implies the restriction of Caristi’s theorem to continuous functions φ. More precisely, if f is a selfmap of a complete metric space (X, d) such that (10) holds with a continuous function φ : X ↦ ℝ_{+}, then (X, ⪯_{φ}) and f satisfy the assumptions of Zermelo’s Theorem. In particular, Zermelo’s Theorem yields the Banach Contraction Principle.

Proof. Clearly (10) means that f is progressive on (X, ⪯_{φ}). By part (b) of Proposition 7, every chain in (X, ⪯_{φ}) has a supremum. To prove the last statement assume that f is a Banach contraction with a constant h ∈ (0, 1). Then, given x ∈ X,

\begin{matrix}d(x, fx) = d(x, fx)/(1 − h) − h d(x, fx)/(1 − h) ≤ \\ d(x, fx)/(1 − h) − d(fx, f^{2}x)/(1 − h) = φ(x) − φ(fx), \end{matrix}

where φ(x) := d(x, fx)/(1 − h). Clearly φ is continuous and thus f satisfies the assumptions of the above restriction of Caristi’s theorem. □

Remark 5. We emphasize that in the above proof a contractive condition is used to show that a mapping f is progressive (compare with Remarks 2 and 4).

Proposition 9. Under the AC, Caristi’s theorem is equivalent to its restriction to Lipschitzian functions φ.

Proof. The above restriction of Caristi’s theorem implies the so-called Drop Theorem of Daneš [24]. The proof of this fact is outlined in Dugundji&Granas [27, p. 20]: It uses a function φ of a form φ(x) := C ||x|| which is Lipschitzian. Further, the Drop Theorem implies the Ekeland [29] Principle as shown by Daneš [25] and, independently, Penot [69]. The latter theorem yields Caristi’s result (see, e.g., Kirk [50]). □

Remark 6. The above proof indeed uses the AC (at least, the DC is necessary here). This follows from the fact that we have shown the implication

Caristi’s theorem for continuous φ ⇒ Ekeland’s principle, whereas the latter theorem implies the DC as shown by Brunner [19], and the former theorem does not depend on any form of the AC.

Question 1. Is it possible to prove Proposition 9 constructively?

Our next purpose is to present another Jachymski’s [44] proof of Nadler’s [64] theorem, this time, via Zermelo’s Theorem. This proof, however, relies on the AC. It uses a similar idea as Takahashi [76].

Theorem 11. Let F be Nadler’s set-valued contraction on a complete metric space (X, d) such that Fx ∈Cl (X) for all x ∈ X. Then there exists a Lipschitzian function φ : X ↦ ℝ_{+} such that F admits a selection F : X ↦ X which is progressive on (X, ⪯_{φ}). Hence Zermelo’s Theorem yields Nadler’s theorem.

Proof. Choose a real h′ such that h < h′ < 1. Then, given x ∈ X, the set

A_{x} := {y ∈ Fx : h′d(x, y) ≤ d(x, Fx)}

is nonempty. By the AC, there is a mapping F : X ↦ X such that F x ∈ A_{x}. Clearly F is a selection of F. By a contractive condition, we get

d(F x, F(F x)) ≤ H(Fx, F(F x)) ≤ h d(x, F x)

which implies that

d(x, F x) = \frac{h′d(x, F x) − h d(x, F x)}{h′ − h} ≤ \frac{d(x, Fx) − d(F x, F(F x))}{h′ − h}.

Therefore F is progressive on (X, ⪯_{φ}) with φ(x) := d(x, Fx)/(h′−h). Moreover, φ is Lipschitzian since given x, y ∈ X,

|φ(x) − φ(y)| ≤ \frac{d(x, y) + H(Fx, Fy)}{h′ − h} ≤ \frac{h + 1}{h′ − h} d(x, y).

By Zermelo’s Theorem, F has a fixed point x_{∗}, and then x_{∗} ∈ Fx_{∗}. □

On the other hand, also Nadler’s [64] original proof depends on some form of the AC. In particular, it seems that, in general, the DC is necessary to define an iterative sequence (x_{n}) satisfying appropriate inequalities and such that x_{n+1} ∈ Fx_{n}. Thus the following question arises.

Question 2. Is it possible to prove Nadler’s theorem constructively?

If the answer is negative, then another problem is worth studying.

Question 3. What form of the AC is necessary to prove Nadler’s theorem?

Finally, we emphasize that it is not possible to prove Nadler’s theorem via the Banach Contraction Principle and a selection method since there exist set-valued contractions having no continuous selections (see, e.g., Jachymski [44, Example 1]).

In the sequel we want to present a constructive proof of Caristi’s theorem given by Jachymski [41]. However, as we have already mentioned, Mańka was the first, who gave a wholly constructive proof. He established a generalization of Zermelo’s Theorem (cf. [60, Proposition 2]) involving a notion of a sup-function. His argument is a development of an idea of Zermelo’s first proof [90]. Our purpose here is to establish the following variant of Zermelo’s Theorem which, in fact, is a weaker result than Mańka’s [60, Proposition 2], but it can be proved in a simpler way and it is strong enough to yield Caristi’s theorem. Another extension of Zermelo’s Theorem was given recently by Lagler&Volkmann [55].

Given a partially ordered set (P, ⪯), the family of all chains in P is denoted by C(P).

Theorem 12. Let (P, ⪯) be a partially ordered set and f be a progressive selfmap of P. Assume that there exists a function Γ : C(P) ↦ P such that for each C ∈ C(P), Γ(C) is an upper bound of C. Then f has a fixed point.

The idea of considering functions assigning to some subsets of a partially ordered set an upper or lower bound of them goes back to Milgram [63]. We shall derive Theorem 12 from the following special form of Zermelo’s Theorem. The family of all subsets of a set P is denoted by 2^{P}.

Theorem 13. Let P be an abstract set, P be a nonempty subset of 2^{P}, and F be a selfmap of P. Endow P with the set-inclusion. If for every chain C in (P, ⊆),

⋃_{C∈C} C ∈ P,  (11)

and F is progressive on (P, ⊆), then F has a fixed point.

Condition (11) is sufficient for the existence of sup C which coincides then with ⋃_{C∈C} C. On the other hand, (11) is not necessary for the existence of sup C as shown in the following Example 4. Let X := [0, 1] be endowed with the Euclidean topology and P := Cl (X). Consider a countable chain C := {[1/n, 1] : n ∈ ℕ} in (P, ⊆). Then ⋃_{C∈C} = (0, 1] ∉ P, but sup C (= [0, 1]) exists.

Proof of Theorem 12. We develop here an idea of Mańka’s [59] proof of Turinici’s [83] fixed point theorem. We shall apply Theorem 13 with P := C(P) and F defined by

F(C) := C ∪ {f(Γ(C))} for all C ∈ P.  (12)

We show that F is a selfmap of P, i.e., F(C) is a chain in (P, ⊆). Since by hypothesis, for all x ∈ C, x ⪯ Γ(C) and Γ(C) ⪯ f(Γ(C)), we infer that f(Γ(C)) is also an upper bound of C. Thus F(C) is a chain. Clearly F is progressive on (P, ⊆). Moreover, if C is a chain in (C(P), ⊆), then it is easily seen that the union ⋃_{C∈C} C is a chain in (P, ⪯). By Theorem 13, F has a fixed point C_{0}. Then it follows from (12) that f(Γ(C_{0})) ∈ C_{0} so, by the property of Γ, f(Γ(C_{0})) ⪯ Γ(C_{0}). Simultaneously Γ(C_{0}) ⪯ f(Γ(C_{0})) since f is progressive. Thus Γ(C_{0}) is a fixed point of f. □

Remark 7. A counterpart of Theorem 12 for W(P), the family of all nonempty well-ordered subsets of P, substituted for C(P), cannot be proved in the above way, since condition ⋃_{C∈C} C ∈ W(P) need not hold for every chain C in (W(P), ⊆) (cf. Example 5). This is the reason for which we used chains in Theorem 12 instead of well-ordered subsets. Incidentally, such a counterpart of Theorem 12 is also true and it corresponds to Mańka’s [60, Proposition 2].

Example 5. Let (P, ⪯) := ([0, 1], ≤) and A_{n} := {1/k : k = 1, ⋯, n} for n ∈ ℕ. Then A_{n} are well-ordered and the family {A_{n} : n ∈ ℕ} is a countable chain in (W(P), ⊆). However, the union ⋃_{n∈ℕ} A_{n} is not well-ordered.

Now we are ready to give a constructive

Proof of Caristi’s theorem. By part (a) of Proposition 7, not only every chain has an upper bound, but we are also able to define, without the AC, a mapping on the family of all chains in (X, ⪯_{φ}) assigning to every chain an upper bound of it. Namely, the limit operator turns out to be such a mapping. By (10), f is progressive and it suffices to apply Theorem 12 with (P, ⪯) := (X, ⪯_{φ}) to complete the proof. □

Finally, let us notice that Theorem 12 can also be applied to give a constructive proof of a recent result due to Khamsi&Kreinovich [48], who established, with a help of Zorn’s Lemma, a fixed point theorem for the so-called dissipative mappings on probabilistic metric spaces. The details of a constructive proof of their theorem are given in Jachymski [41].

In the sequel we want to present another proof of the Browder-Göhde-Kirk [15], [36], [49] theorem, using an ordering argument. Fuchssteiner [33] was the first, who gave a constructive proof of this result with a help of his iteration theorem derived from Zermelo’s Theorem. A minor variant of Fuchssteiner’s proof is given in Goebel&Kirk [35, pp. 42-43]. (Also, there is another constructive proof, in a uniformly convex setting, due to Goebel [34] which relies on the Cantor intersection theorem; an order is not used here.) We shall derive here the Browder-Göhde-Kirk theorem, in a version of Kirk [49], from the following common fixed point theorem for two progressive mappings on a partially ordered set (cf. Jachymski [47]).

Theorem 14. Let (P, ⪯) be a partially ordered set and P_{0} ⊆ P be nonempty and such that every chain in P_{0} has a supremum in P_{0}. Let F : P_{0} ↦ P_{0} and G : P ↦ P be progressive mappings. If G(Fix F) ⊆ P_{0}, then F and G have a common fixed point.

We precede a proof of Theorem 14 by the following extended formulation of Zermelo’s Theorem, containing a constructive formula for a fixed point which, exceptionally, is indispensable here. This formula was given by Bourbaki [12].

Theorem 15. Under the assumptions of Zermelo’s theorem, given p ∈ P, denote

Hp := sup ⋂{A ⊆ P : p ∈ A, f(A) ⊆ A and for every chain C ⊆ A, sup C ∈ A}.

Then H is well-defined, Hp is a fixed point of F and p ⪯ Hp.

Proof of Theorem 14. By Theorem 15, there exists – independently of the AC – a progressive mapping H : P_{0} ↦ Fix F. Then the mapping G ∘ H is progressive and G ∘ H is a selfmap of P_{0} since G(Fix F) ⊆ P_{0}. By Zermelo’s Theorem, G ∘ H has a fixed point p_{∗}. Then

p_{∗} ⪯ Hp_{∗} ⪯ G(Hp_{∗}) = p_{∗}

which gives p_{∗} = Hp_{∗}. Hence Gp_{∗} = G(Hp_{∗}) = p_{∗} so p_{∗} is fixed under G. (Actually, Fix (G ∘ H) = Fix G ∩ Fix H for any progressive mappings G and H.) Since F ∘ H = H, p_{∗} is a fixed point of F ∘ H. Repeating the above argument yields p_{∗} = F p_{∗}, i.e., p_{∗} is a common fixed point of F and G. □

We recall Kirk’s [49] version of the fundamental fixed point theorem for nonexpansive mappings. We refer the reader to Goebel&Kirk [35, Chapter 4] for a terminology used below. Throughout this section the letter X denotes a Banach space.

Theorem 16 (Kirk). Let K be a nonempty, weakly compact, convex subset of X and assume K has normal structure. Then every nonexpansive mapping f : K ↦ K has a fixed point.

Given a nonempty, weakly compact, convex subset K of X and an arbitrary mapping f : K ↦ K, set

M := {A ⊆ K : A ≠ ∅ and A = cl (conv A)}

and

M_{f} := {A ∈ M : f(A) ⊆ A}.

The mapping A ↦ C(A) (A ∈ M), where C(A) stands for the Chebyshev center of A, is said to be the Chebyshev operator and will be denoted by C. It is well-known that C is a selfmap of M (see, e.g., Goebel&Kirk [35, p. 38]). Moreover, given A ∈ M_{f}, if A = cl (convf(A)) and f is nonexpansive, then C(A) is f-invariant (see, e.g., Goebel&Kirk [35, proof of Theorem 4.1]).

Now an idea of a proof of Kirk’s theorem via Theorem 14 is as follows. We consider the operator F defined by

F (A) := cl (conv f(A)) for A ∈ M_{f}.  (13)

Then it straightforward that f has a fixed point if and only if there exists a singleton in the family Fix F. Zermelo’s Theorem ensures that Fix F ≠ ∅. To show Fix F contains a singleton, it suffices to prove that F has a common fixed point with an operator on M which has the property that every fixed point of it is a singleton. In particular, the Chebyshev operator has such a property if the set K has normal structure.

Proof of Kirk’s Theorem 16. We apply Theorem 14 setting P := M, P_{0} := M_{f}, ⪯:=⊇, G := C and F defined by (13).

Step 1. It follows from the definition of the Chebyshev operator that C(A) ⊆ A for A ∈ M which means C is progressive on (M, ⊇). Let A ∈ M_{f}. Since f(A) ⊆ A, we may conclude that cl (convf(A)) ⊆ cl (convA) = A, i.e., F (A) ⊆ A. Hence f(F (A)) ⊆ f(A) ⊆ F (A). Thus we have shown that F is a selfmap of M_{f} and F is progressive on (M_{f}, ⊇). Consider a chain C in (M_{f}, ⊇). Then the family C has the finite intersection property so, by weak compactness, the set ⋂ C is nonempty. Moreover, it is closed, convex and f-invariant so it belongs to M_{f}. It is easily seen that ⋂ C = sup C in (M_{f}, ⊇).

Now Zermelo’s Theorem implies the existence of a set A_{0} ∈ M_{f} such that A_{0} = cl (convf(A_{0})). In fact, such a set exists for an arbitrary mapping f: We used neither nonexpansive condition, nor continuity of f in Step 1.

Step 2. Since f is nonexpansive, we know that if A ∈ M_{f} and A = cl (convf(A)), then C(A) ∈ M_{f}. That means condition C(Fix F) ⊆ M_{f} is satisfied. By Theorem 14, C and F have a common fixed point A_{∗} ∈ M_{f}, i.e., A_{∗} = C(A_{∗}) = F (A_{∗}).

Step 3. Since A_{∗} = C(A_{∗}) and K has normal structure, we obtain that A_{∗} = {a_{∗}} for some a_{∗} ∈ K. Then F (A_{∗}) = {f(a_{∗})} and since A_{∗} = F (A_{∗}), we get that a_{∗} is a fixed point of f. □

Finally, let us notice that Zermelo’s Theorem 15 can also be applied to prove more abstract formulations of Kirk’s theorem dealing with nonexpansive mappings on a metric space which possesses the so-called convexity structure, a notion introduced by Penot [68]. In this setting Büber and Kirk [20] gave a constructive proof of Soardi’s [74] fixed point theorem. We emphasize that a success of their approach is due to the fact that, under the assumptions of Zermelo’s Theorem, there exists – independently of the AC (!) – a retraction from a set P onto the set of all fixed points of a mapping considered.

3. The Tarski-Kantorovitch Theorem

A selfmap F of a partially ordered set (P, ⪯) is said to be ⪯-continuous if for every countable chain C having a supremum, the image F (C) has a supremum and sup F (C) = F (sup C). It is easily seen that a ⪯-continuous mapping is isotone. (P, ⪯) is said to be ⪯-complete if every countable chain has a supremum. (In a literature (P, ⪯) is also called then chain ω-complete; cf. Markowsky [61].) Following Dugundji&Granas [27, p. 15], we recall the Tarski-Kantorovitch Theorem (abbr., ‘the T-K Theorem’).

Theorem 17 (Tarski-Kantorovitch). Let (P, ⪯) be a ⪯-complete partially ordered set and a mapping F : P ↦ P be ⪯-continuous. If there exists p_{0} ∈ P such that p_{0} ⪯ F p_{0}, then F has a fixed point; moreover, p_{∗} := sup{F^{n}p_{0} : n ∈ ℕ} is fixed under F.

A similar fixed point theorem is known in a literature as Kleene’s fixed point theorem (see, e.g., Baranga [8]) in which increasing sequences are substituted for chains in the definitions of ⪯-continuity and ⪯-completeness. It turns out that the assumptions of both theorems are equivalent according to the following

Proposition 10. Let (P, ⪯) be a partially ordered set and F : P ↦ P. Then

(a): (P, ⪯) is ⪯-complete if and only if every strictly increasing sequence

in P has a supremum; (b): F is ⪯-continuous if and only if F is isotone and for every strictly

increasing sequence (p_{n}) having a supremum, there exists sup{F p_{n} : n ∈ ℕ} and it coincides with F (sup{p_{n} : n ∈ ℕ}).

Proof. Parts ‘only if’ of both statements are trivial. We prove part ‘if’ of (a). Let C be a countable chain, C = {c_{n} : n ∈ ℕ}. If max C exists, then we are done. Otherwise, we may define by induction a subsequence (c_{k_{n}}) setting

k_{1} := 1 and k_{n+1} := min{m > k_{n} : c_{k_{n}} ⪯ c_{m} and c_{k_{n}} ≠ c_{m}}

Then (c_{k_{n}}) is strictly increasing so by hypothesis, there exists c_{0} := sup{c_{k_{n}} : n ∈ ℕ}. Since for each n ∈ ℕ and k_{n} ≤ m < k_{n+1}, c_{m} ⪯ c_{k_{n}}, we may conclude that c_{0} = sup C. A similar argument can be used to prove part ‘if’ of (b). □

Our first purpose is to show, following Jachymski [43], that the T-K Theorem yields Angelov’s theorem in a little more general setting: It suffices to assume that a uniform space X is only sequentially complete. Moreover, thanks to a constructive formula for a fixed point in the T-K Theorem, it will be possible to prove the convergence of successive approximations of a mapping f, the fact non-obtainable via the Knaster-Tarski Theorem. We also emphasize that this time all our proofs are independent of the AC. We consider the same partially ordered set (X × ℝ_{+}^{A}, ⪯) as in Section 1. We start with two results on completeness (cf. Jachymski [43]).

Proposition 11. Let (X, P) be a Hausdorff uniform space with a family of pseudometrics P := {p_{α} : α ∈ A}. The following statements are equivalent.

(i): Every sequence (x_{n}) in X such that

∑_{n=1}^{∞} p_{α}(x_{n}, x_{n+1}) < ∞ for all α ∈ A  (14)

is convergent. (ii): Every increasing sequence ((x_{n}, φ_{n}))_{n=1}^{∞} in (X ×ℝ_{+}^{A}, ⪯) is such that

(x_{n}) converges to some x_{0} ∈ X, (φ_{n}) converges pointwisely to some φ_{0} ∈ ℝ_{+}^{A} and (x_{0}, φ_{0}) = sup{(x_{n}, φ_{n}) : n ∈ ℕ}.

(iii): (X × ℝ_{+}^{A}, ⪯) is ⪯-complete.

In particular, if (X, P) is sequentially complete, then (X × ℝ_{+}^{A}, ⪯) is ⪯- complete.

Proof. (i) ⇒ (ii): Assume that ((x_{n}, φ_{n}))_{n=1}^{∞} is increasing, i.e.,

p_{α}(x_{n}, x_{n+1}) ≤ φ_{n}(α) − φ_{n+1}(α) for α ∈ A and n ∈ ℕ.  (15)

Summing up with respect to n yields

∑_{n=1}^{m−1} p_{α}(x_{n}, x_{n+1}) ≤ φ_{1}(α) − φ_{m}(α) ≤ φ_{1}(α) for all m ≥ 2

which implies (14). By (i), (x_{n}) converges to some x_{0} ∈ X. Moreover, by (15), φ_{n+1}(α) ≤ φ_{n}(α) and since functions φ_{n} are nonnegative, the sequence (φ_{n}) converges pointwisely to some φ_{0} ∈ ℝ_{+}^{A}. Let m, n ∈ ℕ and m > n. By (15), we get

p_{α}(x_{n}, x_{m}) ≤ ∑_{k=n}^{m−1} p_{α}(x_{k}, x_{k+1}) ≤ φ_{n}(α) − φ_{m}(α) for α ∈ A.

Hence letting m → ∞ we obtain that p_{α}(x_{n}, x_{0}) ≤ φ_{n}(α) − φ_{0}(α) which means (x_{0}, φ_{0}) is an upper bound of the set {(x_{n}, φ_{n}) : n ∈ ℕ}. Let (x, φ) be another upper bound of this set, i.e., p_{α}(x_{n}, x) ≤ φ_{n}(α) − φ(α) for α ∈ A and n ∈ ℕ. Letting n → ∞ we get that (x_{0}, φ_{0}) ⪯ (x, φ). Thus (x_{0}, φ_{0}) is the least upper bound of the sequence ((x_{n}, φ_{n}))_{n=1}^{∞}.

(ii) ⇒ (iii): Since (ii) implies, in particular, that every increasing sequence in (X × ℝ_{+}^{A}, ⪯) is convergent, we may apply part (a) of Proposition 10 to deduce (iii).

(iii) ⇒ (i): Assume that (14) holds. Define

φ_{n}(α) := ∑_{k=n}^{∞} p_{α}(x_{k}, x_{k+1}).

Since p_{α}(x_{n}, x_{n+1}) = φ_{n}(α) − φ_{n+1}(α), the sequence ((x_{n}, φ_{n}))_{n=1}^{∞} is increasing. By (iii), this sequence has a supremum (x_{0}, φ_{0}). Then

p_{α}(x_{n}, x_{0}) ≤ φ_{n}(α) − φ_{0}(α)

which implies that 0 ≤ φ_{0}(α) ≤ φ_{n}(α). Since φ_{n}(α) → 0, we get that φ_{0}(α) = 0. Thus p_{α}(x_{n}, x_{0}) ≤ φ_{n}(α) which yields that x_{0} = lim x_{n}.

Finally, if (X, P) is sequentially complete, then condition (i) holds since every sequence satisfying (14) is Cauchy, hence convergent. The ⪯-completeness follows from (i) ⇒ (ii). □

In a metric setting a more pellucid result can be established. We use here Ekeland’s ordering defined by (4). Part ‘only if’ of the following theorem was proved by Baranga [8, Corollary 3].

Proposition 12. Let (X, d) be a metric space. Then (X, d) is complete if and only if (X × ℝ_{+}, ⪯) is ⪯-complete.

Proof. Part ‘only if’ follows from Proposition 11. To prove part ‘if’ observe that every Cauchy sequence (x_{n}) has a subsequence (x_{k_{n}}) such that ∑_{n=1}^{∞} d(x_{k_{n}}, x_{k_{n+1}}) < ∞. By implication (iii) ⇒ (i) of Proposition 11, this subsequence converges to some x_{0} ∈ X. Then x_{0} is also the limit of (x_{n}). □

Lemma 2. Let (X, P) be a Hausdorff uniform sequentially complete space with P := {p_{α} : α ∈ A}. Let f : X ↦ X be a j-Lipschitzian mapping and F be an associated mapping on X × ℝ_{+}^{A} defined by (6). Then F is ⪯-continuous.

Proof. We apply part (b) of Proposition 10. Let ((x_{n}, φ_{n}))_{n=1}^{∞} be increasing in (X × ℝ_{+}^{A}, ⪯). By Proposition 11, (x_{n}) converges to some x_{0} ∈ X and (φ_{n}) converges pointwisely to some φ_{0} ∈ ℝ_{+}^{A}, and (x_{0}, φ_{0}) = sup{(x_{n}, φ_{n}) : n ∈ ℕ}. By Proposition 5, F is isotone and hence (F (x_{n}, φ_{n}))_{n=1}^{∞} is increasing. Again by Proposition 11, there exists (y_{0}, ψ_{0}) := sup{F (x_{n}, φ_{n}) : n ∈ ℕ}; moreover, y_{0} = lim fx_{n} = fx_{0} since f is continuous, and ψ_{0}(α) = lim h_{α} φ_{n}(j(α)) = h_{α}φ_{0}(j(α)). Thus

(y_{0}, ψ_{0}) = (fx_{0}, h · (φ_{0} ∘ j)) = F (x_{0}, φ_{0})

which means F is ⪯-continuous. □

We are ready to prove the convergence of successive approximations in the Tan-Tarafdar theorem and Angelov’s theorem via the T-K Theorem. We assume in Theorems18 and 19 given below that a uniform space (X, P) is sequentially complete (not necessarily complete).

Theorem 18. Under the assumptions of Theorem 5, f has a fixed point x_{∗} and f^{n}x → x_{∗} for all x ∈ X.

Proof. By Proposition 11 and Lemma 2, (X × ℝ_{+}^{A}, ⪯) is ⪯-complete and a mapping F is ⪯-continuous. Fix an x ∈ X. If we set

φ(α) := p_{α}(x, fx)/(1 − h_{α}) for all α ∈ A,

then (x, φ) ⪯ F (x, φ). By the T-K Theorem, (x_{∗}, φ_{∗}) := sup{F^{n}(x, φ) : n ∈ ℕ} is a fixed point of F. Then x_{∗} = fx_{∗}. By monotonicity of (F^{n}(x, φ))_{n=1}^{∞} and Proposition 11, (x_{∗}, φ_{∗}) = (lim f^{n}x, lim h^{n}φ); in particular, x_{∗} = lim f^{n}x. □

Theorem 19. Under the assumptions of Theorem 6, f has a fixed point. Moreover, lim f^{n}x_{0} is a fixed point of f.

Proof. We show there exists a function φ_{0} ∈ ℝ_{+}^{A} such that (x_{0}, φ_{0}) ⪯ F (x_{0}, φ_{0}). Then φ_{0} should be a solution of functional inequality (7). First we use a similar argument as in the proof of Lemma 1. Under the notations of this proof, we slightly change a definition of T_{β} by setting

T_{β} := g + h · (φ ∘ j) for all φ ∈ Φ_{β}.

(Actually, we consider here the restrictions of g, h and j to an orbit O_{j}(β).) Then T_{β}(Φ_{β}) ⊆ Φ_{β} and T_{β} is a Banach contraction with a contractive constant ĥ_{β}. Hence it has a fixed point φ_{β}. This time we can use the convergence of successive approximations of T_{β}, the fact covered by the T-K Theorem in view of Theorem 18. Thanks to that we shall be able to circumvent the AC. In particular, consider the sequence (T_{β}^{n}0). Then φ_{β} = lim_{n→∞} T_{β}^{n}0 and hence we obtain

φ_{β}(α) = g(α) + ∑_{n=1}^{∞} ( ∏_{p=0}^{n−1} h(j^{p}(α))) g(j^{n}(α)) for α ∈ O_{j}(β).

Set φ_{0}(β) := φ_{β}(β) for β ∈ A. It can easily be verified that φ_{0} is a solution of (7) on A. By the K-T Theorem, the pair (x_{∗}, φ_{∗}) := sup{F^{n}(x_{0}, φ_{0}) : n ∈ ℕ} is a fixed point of F. Since F^{n}(x_{0}, φ_{0}) = (f^{n}x_{0}, φ_{n}), where φ_{n}(α) := h_{α} φ_{n−1}(j(α)) for n ∈ ℕ, and (F^{n}(x_{0}, φ_{0}))_{n=1}^{∞} is increasing, we may conclude by Proposition 11 that x_{∗} = lim f^{n}x_{0}. □

A number of authors studied a class of mappings which satisfy a nonlinear contractive condition. Namely, given a function φ : ℝ_{+} ↦ ℝ_{+} such that φ(t) < t for t > 0 and φ(0) = 0, we say that a selfmap f of a metric space (X, d) is φ-contractive if

d(fx, fy) ≤ φ(d(x, y)) for all x, y ∈ X.

It seems that the theory of such mappings was initiated by Rakotch [70] and subsequently it was developed, e.g., by Browder [16], Zitarosa [92], Boyd&Wong [13], Matkowski [62], Dugundji&Granas [26], Jachymski ([39], [40], [45]) and Alber, Guerre-Delabriere&Zelenko [3]. In [43] we examined possibilities of deriving fixed point theorems for φ-contractive mappings from the T-K Theorem restricted to Ekeland’s ordering ⪯_{E} in X × ℝ_{+} and a mapping F of the following form:

F (x, a) := (fx, T a) for x ∈ X and a ∈ ℝ_{+},

where T : ℝ_{+} ↦ ℝ_{+}. Then it is natural to assume that the set {a ∈ ℝ_{+} : T a < a} is nonempty; otherwise, the above restriction of the T-K Theorem would be trivial since the condition (x_{0}, φ_{0}) ⪯ F (x_{0}, φ_{0}) implied then that x_{0} = fx_{0}. It is rather surprising that our previous methods turn out to be ineffective in a setting of φ-contractive mappings. In particular, Rakotch’s [70] fixed point theorem involving a function φ such that t ↦ φ(t)/t (t > 0) is non-increasing (this forces subadditivity of φ, i.e., φ(s + t) ≤ φ(s) + φ(t) for s, t ∈ ℝ_{+}) cannot be derived from the T-K Theorem in the above way, according to the following result (for a proof, cf. Jachymski [43]).

Theorem 20. Let a function φ : ℝ_{+} ↦ ℝ_{+} be nondecreasing, subadditive and such that φ(t) < t for t > 0. The following statements are equivalent.

(i): There is an h ∈ (0, 1) such that φ(t) ≤ h t for all t ∈ ℝ_{+}.

(ii): Given a complete metric space (X, d) and a φ-contractive mapping f : X ↦ X, there exists a function T : ℝ_{+} ↦ ℝ_{+} such that T (a_{0}) < a_{0} for some a_{0} ∈ ℝ_{+}, and the mapping (f, T) is ⪯_{E}-continuous on X × ℝ_{+}.

Speaking more briefly, if a function φ has the property that for every φcontractive mapping the T-K Theorem can be used in the above way, then every such a mapping is a Banach contraction. Thus, in some sense, the T-K Theorem can be applied only to a class of mappings satisfying a linear contractive condition.

Finally, we want to present how some results of the theory of iterated function systems (IFS) can be derived from the T-K Theorem. The theory of IFS deals with fixed points of the folowing Hutchinson-Barnsley operator (cf. Hutchinson [38] and Barnsley [9, p. 80]).

F (A) := ⋃_{i=1}^{N} f_{i}(A) for A ⊆ X,  (16)

where X is a set and f_{1}, ⋯, f_{N} are selfmaps of X. The fundamental Hutchinson-Barnsley theorem says that if (X, d) is a complete metric space and all the maps f_{i} are Banach contractions, then F has a unique fixed point A_{∗} in K(X), the family of all nonempty, compact subsets of X. A set A_{∗} is called then a fractal in the sense of Barnsley. There are at least two different proofs of the above result based on the Banach Contraction Principle. The first, due to Hutchinson [38], uses a fact that every finite composition

f_{i_{1}···i_{p}} := f_{i_{1}} ∘ ⋯ ∘ f_{i_{p}} for p ∈ ℕ and i_{1}, ⋯, i_{p} ∈ {1, ⋯, N}

is also a Banach contraction so it has a fixed point. Then it can be shown that A_{∗} coincides with the closure of the set of fixed points of all finite compositions f_{i_{1}···i_{p}}. The second proof uses a well-known theorem, a proof of which is rather technical, saying that completeness of (X, d) implies completeness of K(X) endowed with the Hausdorff metric H (see, e.g., Barnsley [9, Theorem II.7.1]). Next it can be shown that the operator F is a Banach contraction on (K(X), H) and the Contraction Principle yields then the theorem (see, e.g., Barnsley [9, Theorem III.7.1]). Our purpose here is to give yet another proof via partial ordering techniques. Such an idea also appears in papers of Soto-Andrade&Varela [75] and Hayashi [37], however, they considered other versions of Tarski’s fixed point theorem. We start with the following theorem on ⪯-continuity (cf. Jachymski, Gajek&Pokarowski [46, Lemma 1]).

Proposition 13. Let (P, ⪯) be a partially ordered set which is ⪯-complete and such that for any p, q ∈ P, there exists an infimum inf{p, q}. Assume that for any increasing sequences (p_{n}) and (q_{n}) in P,

inf{sup{p_{n} : n ∈ ℕ}, sup{q_{n} : n ∈ ℕ}} = sup{inf{p_{n}, q_{n}} : n ∈ ℕ}. (17)

Let F_{1}, ⋯, F_{N} be ⪯-continuous selfmaps of P and define a mapping F by

F p := inf{F_{1}p, ⋯, F_{N}p} for p ∈ P.

Then F is ⪯-continuous.

Proof. For the sake of simplicity, assume that N = 2; then an easy induction shows that our argument can be extended to the case of an arbitrary N ∈ ℕ. By Proposition 10, it suffices to show that given an increasing sequence (p_{n}) in P, F p = sup_{n∈ℕ} F p_{n}, where p := sup_{n∈ℕ} p_{n}. Since F_{1} and F_{2} are isotone, so is F. Hence the sequence (F p_{n}) is increasing and by hypothesis, it has a supremum. Then by (17) and ⪯-continuity of F_{1} and F_{2},

sup{F p_{n} : n ∈ ℕ} = sup{inf{F_{1}p_{n}, F_{2}p_{n}} : n ∈ ℕ} = inf{sup{F_{1}p_{n} : n ∈ ℕ}, sup{F_{2}p_{n} : n ∈ ℕ}} = inf{F_{1}p, F_{2}p} = F p

which proves the ⪯-continuity of F. □

Corollary 2. Let X be a Hausdorff topological space, f_{1}, ⋯, f_{N} be continuous selfmaps of X. Endow K(X), the family of all nonempty, compact subsets of X, with the set-inclusion ⊇. Then the operator F defined by (16) is ⊇-continuous on K(X).

Proof. Given an increasing sequence (A_{n}) in (K(X), ⊇) (i.e., (A_{n}) is decreasing in the usual sense), the set ⋂_{n=1}^{∞} A_{n} is nonempty by compactness, and it is a supremum of (A_{n}). (Actually, every chain in (K(X), ⊇) has a supremum.) Thus (K(X), ⊇) is ⊇-complete. Set

F_{i}(A) := f_{i}(A) for i = 1, ⋯, N and A ∈ K(X).

By topological continuity, all the F_{i} are selfmaps of K(X). We show each F_{i} is ⊇-continuous. By Proposition 10, it suffices to show that given a decreasing – in the usual sense – sequence (A_{n}) in K(X), f_{i}(⋂_{n=1}^{∞} A_{n}) = ⋂_{n=1}^{∞} f_{i}(A_{n}). This result can be found, e.g., in Polish edition of Engelking [31] published in 1989 – cf. Exercise 3.10.A (c) of this book. For the sake of completeness, we give a proof of it. The inclusion ⊆ is obvious. Let y ∈ ⋂_{n=1}^{∞} f_{i}(A_{n}), i.e., y = f_{i}(x_{n}) for some x_{n} ∈ A_{n}. Set B_{n} := f^{−1}({y})∩A_{n}. Then x_{n} ∈ B_{n} and B_{n} are compact, i.e., B_{n} ∈ K(X). Moreover, B_{n+1} ⊆ B_{n} so, by compactness, ⋂_{n=1}^{∞} B_{n} ≠ ∅. If x ∈ ⋂_{n=1}^{∞} B_{n}, then f_{i}x = y and x ∈ ⋂_{n=1}^{∞} A_{n} which means y ∈ f_{i}(⋂_{n=1}^{∞} A_{n}).

Observe that condition (17) in (K(X), ⊇) means given decreasing – in the usual sense – sequences (A_{n}) and (B_{n}) in K(X),

⋂_{n=1}^{∞} A_{n} ∪ ⋂_{n=1}^{∞} B_{n} = ⋂_{n=1}^{∞}(A_{n} ∪ B_{n}).

This equality holds indeed even if the sets considered are not compact. By Proposition 13, F is ⊇-continuous. □

Now Corollary 2 and the T-K Theorem yield the following

Theorem 21. Let X be a topological space, f_{1}, ⋯, f_{N} be continuous selfmaps of X and F be the Hutchinson-Barnsley operator (16). The following statements are equivalent.

(i): There exists a nonempty, compact set A_{∗} ⊆ X such that

F (A_{∗}) = A_{∗}.

(ii): There exists a nonempty, compact set A_{0} ⊆ X such that

F (A_{0}) ⊆ A_{0}.

Proof. It suffices to show (ii)⇒(i). Apply the T-K Theorem setting (P, ⪯ ) := (K(A_{0}), ⊇). The ⊇-continuity of F on K(A_{0}) follows from Corollary 2 applied to the restrictions f_{i}|_{A_{0}} of the mappings f_{i} to the set A_{0}. Moreover, ⋂_{n=1}^{∞} F^{n}(A_{0}) is a fixed point of F. □

We are ready to give another proof of the Hutchinson-Barnsley theorem as done in Jachymski, Gajek&Pokarowski [46] (also cf. Hayashi [37]). According to Theorem 21, it suffices to show the existence of a nonempty, compact set A_{0} such that F (A_{0}) ⊆ A_{0}. That can be done in a simple way if, e.g., all the mappings f_{i} are Banach contractions and a metric space (X, d) has the Heine-Borel property (see, e.g., Williamson&Janos [88]), i.e., every closed and bounded subset of X is compact. It is worth noticing that many results of the theory of IFS were obtained in the above class of spaces (cf. Lasota&Myjak [56] and Lasota&Yorke [57]).

The following lemma is essentially due to Williams [87]. We give it in a slightly modified form.

Lemma 3. Let (X, d) be a metric space and f : X ↦ X be a Banach contraction. Then given x_{0} ∈ X, there exists r_{0} > 0 such that for all r ≥ r_{0}, the closed ball B(x_{0}, r) is f-invariant. Hence given a finite family f_{1}, ⋯, f_{N} of Banach contractions and x_{0} ∈ X, there exists R > 0 such that F (B(x_{0}, R)) ⊆ B(x_{0}, R), where F denotes the Hutchinson-Barnsley operator (16).

Proof. Let h denote a Lipschitz constant of f. Let x_{0} ∈ X, r > 0 and x ∈ B(x_{0}, r). Then

d(fx, x_{0}) ≤ d(fx, fx_{0}) + d(fx_{0}, x_{0}) ≤ h r + d(fx_{0}, x_{0}).

Hence d(fx, x_{0}) ≤ r if hr+d(x_{0}, fx_{0}) ≤ r, i.e., r ≥ d(x_{0}, fx_{0})/(1−h). Thus it is enough to set r_{0} := d(x_{0}, fx_{0})/(1 − h).

Now it is easily seen that if the mappings f_{i} are Banach contractions with Lipschitz constants h_{1}, ⋯, h_{N}, then it suffices to set

R := max{d(x_{0}, f_{i}x_{0})/(1 − h_{i}) : i = 1, ⋯, N}. □

Now Theorem 21 and Lemma 3 yield the Hutchinson-Barnsley theorem for an appropriate IFS on a Heine-Borel metric space; in particular, on the Euclidean space ℝ^{n}. However, the uniqueness of a fixed point of F is not obtainable via the T-K Theorem.

Finally, we would like to notice that the T-K Theorem can be applied in the theory of IFS in somewhat more general setting because of using conditions involving a suitable behaviour of countable chains only. This is the reason for which countable compactness can be substituted for compactness. In particular, if X is a Hausdorff topological space and C(X) denotes the family of all nonempty, closed subsets of X, then ⊇-completeness of C(X) is equivalent to countable compactness of X (cf. Engelking [31, Theorem 3.10.2]). If, moreover, X is sequential (i.e., every sequentially closed subset of X is closed), then, in case N = 1, the Hutchinson-Barnsley operator F is ⊇-continuous and it maps C(X) into itself if and only if a mapping f is continuous in a topological sense (cf. Jachymski, Gajek&Pokarowski [46, Proposition 5]). (It is interesting that the last equivalence need not hold if we drop the assumption that X is sequential; cf. [46, Example 3].) Therefore for a sequential space X and a mapping f : X ↦ X, the assumptions of the T-K Theorem with (P, ⪯) := (C(X), ⊇) and F (A) := f(A) for A ∈ C(X) are satisfied if and only if X is countably compact and f is continuous with respect to topology.

Acknowledgements

I wish to thank Art Kirk for the invitation to write this chapter and patience as I was writing it. Also, I am grateful to Czesaw Bessaga, Andrzej Granas, Roman Mańka, Janusz Matkowski and Jim Stein, Jr. for fruitful discussions and useful remarks on this stuff. Further, I thank Yakov Alber, Vasil Angelov, Yong-Zhuo Chen, Susumu Hayashi, Ludvik Janos, Wataru Takahashi, Mihai Turinici and Peter Volkmann for providing me with reprints of their papers. However, most of all I owe gratitude to my wife Zofia and children for putting up with my absence at home as I was working on this chapter and my other papers.

References

[1] A. Abian, A fixed point theorem equivalent to the axiom of choice, Arch. Math. Logik 25 (1985), 173-174.

[2] S. Abian and A. B. Brown, A theorem on partially ordered sets, with applications to fixed point theorems, Canad. J. Math. 13 (1961), 78-82.

[3] Ya. Alber, S. Guerre-Delabriere and L. Zelenko, The principle of weakly contractive mappings in metric spaces, Comm. Appl. Nonlinear Anal. 5 (1998), 45-68.

[4] M. Altmann, A generalization of the Brézis-Browder principle on ordered sets, Nonlinear Anal. 6 (1982), 157-165.

[5] H. Amann, Order Structures and Fixed Points. Ruhr-Universität, Bochum, 1977 (mimeographed lecture notes).

[6] V. G. Angelov, Fixed point theorems in uniform spaces and applications, Czech. Math. J. 37 (1987), 19-33.

[7] V. G. Angelov, On the Synge equations in a three-dimensional two-body problem of classical electrodynamics, J. Math. Anal. Appl. 151 (1990), 488-511.

[8] A. Baranga, The contraction principle as a particular case of Kleene’s fixed point theorem, Discrete Math. 98 (1991), 75-79.

[9] M. F. Barnsley, Fractals everywhere. Academic Press, Boston, 1993.

[10] H. Bell, Review of “Proceedings of the Seminar on Fixed Point Theory and its Applications,” Math. Rev. 57 (1976), no. 1459.

[11] C. Bessaga, private communication (November 1999).

[12] N. Bourbaki, Sur le théorème de Zorn, Arch. Math. 2 (1949-50), 434-437.

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

[14] H. Brézis and F. E. Browder, A general principle on ordered sets in nonlinear functional analysis, Advances in Math. 21 (1976), 355-364.

[15] F. E. Browder, Nonexpansive nonlinear operators in a Banach space, Proc. Nat. Acad. Sci. USA 54 (1965), 1041-1044.

[16] F. E. Browder, On the convergence of successive approximations for nonlinear functional equations, Indag. Math. 30 (1968), 27-35.

[17] F. E. Browder, On a theorem of Caristi and Kirk, in “Proceedings of the Seminar on Fixed Point Theory and its Applications,” Dalhousie University, June 1975, pp. 23-27, Academic Press, New York, 1976.

[18] A. Brøndsted, On a lemma of Bishop and Phelps, Pacific J. Math. 55 (1974), 335-341.

[19] N. Brunner, Topologische Maximalprinzipien, Z. Math. Logik Grundlagen Math. 33 (1987), 135-139.

[20] T. Büber and W. A. Kirk, A constructive proof of a fixed point theorem of Soardi, Math. Japon. 41 (1995), 233-237.

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

[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] H. Covitz and S. B. Nadler, Jr., Multi-valued contraction mappings in generalized metric spaces, Israel J. Math. 8 (1970), 5-11.

[24] J. Daneš, A geometric theorem useful in nonlinear functional analysis, Boll. Un. Mat. Ital. 6 (1972), 369-375.

[25] J. Daneš, Equivalence of some geometric and related results of nonlinear functional analysis, Comment. Math. Univ. Carolin. 26 (1985), 443-454.

[26] J. Dugundji and A. Granas, Weakly contractive maps and elementary domain invariance theorem, Bull. Greek Math. Soc. 19 (1978), 141-151.

[27] J. Dugundji and A. Granas, Fixed Point Theory I. Polish Scientific Publishers, Warszawa, 1982.

[28] N. Dunford and J. Schwartz, Linear Operators I: General Theory. Wiley Interscience, New York, 1957.

[29] I. Ekeland, On the variational principle, J. Math. Anal. Appl. 47 (1974), 324-353.

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

[31] R. Engelking, General Topology. Polish Scientific Publishers, Warszawa, 1977.

[32] M. Frigon, On continuation methods for contractive and nonexpansive mappings, in “Recent advances on metric fixed point theory (Seville, 1995)”, pp. 19-30, Ciencias, 48, Univ. Sevilla, Seville, 1996.

[33] B. Fuchssteiner, Iterations and fixpoints, Pacific J. Math. 68 (1977), 73-80.

[34] K. Goebel, An elementary proof of the fixed point theorem of Browder and Kirk, Michigan Math. J. 16 (1969), 381-383.

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

[36] D. Göhde, Zum Prinzip der kontraktiven Abbildung, Math. Nachr. 30 (1965), 251-258.

[37] S. Hayashi, Self-similar sets as Tarski’s fixed points, Publ. Res. Inst. Math. Sci. 21 (1985), 1059-1066.

[38] J. Hutchinson, Fractals and self-similarity, Indiana Univ. Math. J. 30 (1981), 713-747.

[39] J. Jachymski, An extension of A. Ostrovski’s theorem on the round-off stability of iterations, Aequationes Math. 53 (1997), 242-253.

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

[41] J. Jachymski, Some consequences of fundamental ordering principles in metric fixed point theory, Ann. Univ. M. Curie-Skodowska A 51 (1997), 123-134.

[42] J. Jachymski, Fixed point theorems in metric and uniform spaces via the Knaster-Tarski Principle, Nonlinear Anal. 32 (1998), 225-233.

[43] J. Jachymski, Some consequences of the Tarski-Kantorovitch ordering theorem in metric fixed point theory, Quaestiones Math. 21 (1998), 89-99.

[44] J. Jachymski, Caristi’s fixed point theorem and selections of set-valued contractions, J. Math. Anal. Appl. 227 (1998), 55-67.

[45] J. Jachymski, On iterative equivalence of some classes of mappings, Ann. Math. Sil. 13 (1999), 149-165.

[46] J. Jachymski, L. Gajek and P. Pokarowski, The Tarski-Kantorovitch principle and the theory of iterated function systems, Bull. Austral. Math. Soc. 61 (2000), 247-261.

[47] J. Jachymski, Another proof of the Browder-Göhde-Kirk theorem via partial ordering techniques, submitted.

[48] M. A. Khamsi and V. Y. Kreinovich, Fixed point theorems for dissipative mappings in complete probabilistic metric spaces, Math. Japon. 44 (1996), 513-520.

[49] W. A. Kirk, A fixed point theorem for mappings which do not increase distance, Amer. Math. Monthly 72 (1965), 1004-1006.

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

[51] B. Knaster, Un théorème sur les fonctions d’ensembles, Ann. Soc. Polon. Math. 6 (1928), 133-134.

[52] H. Kneser, Eine direkte Ableitung des Zornschen lemmas aus dem Auswahlaxiom, Math. Z. 53 (1950), 110-113.

[53] M. Kuczma, Functional Equations in a Single Variable. Polish Scientific Publishers, Warszawa, 1968.

[54] M. Kuczma, B. Choczewski and R. Ger, Iterative Functional Equations. Encyclopedia of Mathematics and its Applications, Vol. 32. Cambridge University Press, Cambridge, 1990.

[55] M. Lagler and P. Volkmann, Über Fixpunktsätze in geordneten Mengen, Math. Nachr. 185 (1997), 111-114.

[56] A. Lasota and J. Myjak, Semifractals, Bull. Pol. Acad. Sci. Math. 44 (1996), 5-21.

[57] A. Lasota and J. Yorke, Lower bound technique for Markov operators and iterated function systems, Random Comput. Dynamics 2 (1994), 41-77.

[58] R. Lemmert and P. Volkmann, Un théorème de point fixe dans les ensembles, Mathematica (Cluj) 31(54) (1989), 69-73.

[59] R. Mańka, Turinici’s fixed point theorem and the axiom of choice, Rep. Math. Logic 22 (1988), 15-19.

[60] R. Mańka, Some forms of the axiom of choice, Jahrb. Kurt Gödel Ges. 1 (1988), 24-34, Wien.

[61] G. Markowsky, Chain-complete posets and directed sets with applications, Algebra Univ. 6 (1976), 53-68.

[62] J. Matkowski, Integrable solutions of functional equations, Dissertationes Math. 127 (1975).

[63] A. N. Milgram, Partially ordered sets, separating systems, and inductiveness, Rep. Math. Colloq. (2) 1 (1939), 18-30.

[64] S. B. Nadler, Jr., Multi-valued contraction mappings, Pacific J. Math. 30 (1969), 475-488.

[65] L. Pasicki, A short proof of the Caristi theorem, Comment. Math. Prace Mat. 20 (1978), 427-428.

[66] A. Pelczar, On the invariant points of a transformation, Ann. Pol. Math. 11 (1961), 199-202.

[67] J.-P. Penot, A short constructive proof of Caristi’s fixed point theorem, Publ. Math. Pau 10 (1976), 1-3.

[68] J.-P. Penot, Fixed point theorems without convexity, Bull. Soc. Math. France, Memoire 60 (1979), 129-152.

[69] J.-P. Penot, The drop theorem, the petal theorem and Ekeland’s variational principle, Nonlinear Anal. 10 (1986), 813-822.

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

[71] W. O. Ray, A rapidly convergent iteration method and Gâteaux differentiable operators, J. Math. Anal. Appl. 103 (1984), 162-171.

[72] B. S. W. Schröder, Algorithms for the fixed point property, Theoret. Comput. Sci. 217 (1999), 301-358.

[73] R. E. Smithson, Fixed points of order preserving multifunctions, Proc. Amer. Math. Soc. 28 (1971), 304-310.

[74] P. Soardi, Existence of fixed points of nonexpansive mappings in certain Banach lattices, Proc. Amer. Math. Soc. 73 (1979), 25-29.

[75] J. Soto-Andrade and F. J. Varela, Self-reference and fixed points: A discussion and an extension of Lawvere’s theorem, Acta Appl. Math. 2 (1984), 1-19.

[76] W. Takahashi, Existence theorems generalizing fixed point theorems for multivalued mappings, in “Fixed Point Theory and Applications” (J.-B. Baillon and M. Théra, Eds.), Pitman Research Notes in Mathematics, Vol. 252, pp. 397-406. Longman, Harlow, 1991.

[77] D. H. Tan, On the contraction principle in uniformizable spaces, Acta Math. Vietnam. 5 (1980), 88-99.

[78] K.-K. Tan, Fixed point theorems for nonexpansive mappings, Pacific J. Math. 41 (1972), 829-842.

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

[80] A. Tarski, A lattice-theoretical fixpoint theorem and its applications, Pacific J. Math. 5 (1955), 285-309.

[81] A. C. Thompson, On certain contraction mappings in a partially ordered vector space, Proc. Amer. Math. Soc. 14 (1963), 438-443.

[82] Ts. Tsatchev and V. G. Angelov, Fixed points of nonself-mappings and applications, Nonlinear Anal. 21 (1993), 9-16.

[83] M. Turinici, Maximal elements in ordered topological spaces, Bull. Greek Math. Soc. 20 (1979), 141-148.

[84] M. Turinici, A generalization of Altman’s ordering principle, Proc. Amer. Math. Soc. 90 (1984), 128-132.

[85] M. Turinici, Metric variants of the Brézis-Browder ordering principles, Demonstratio Math. 22 (1989), 213-228.

[86] W. Walter, Remarks on a paper by F. Browder about contractions, Nonlinear Anal. 5 (1981), 21-25.

[87] R. F. Williams, Composition of contractions, Bol. Soc. Brasil. Mat. 2 (1971), 55-59.

[88] R. Williamson and L. Janos, Constructing metrics with the Heine-Borel property, Proc. Amer. Math. Soc. 100 (1987), 567-573.

[89] E. Zeidler, Nonlinear Functional Analysis and its Applications I. Springer-Verlag, Berlin, 1986.

[90] E. Zermelo, Beweis, das jede Menge wohlgeordnet werden kann, Math. Ann. 59 (1904), 514-516.

[91] E. Zermelo, Neuer Beweis für die Möglichkeit einer Wohlordnung, Math. Ann. 65 (1908), 107-128.

[92] A. Zitarosa, Una generalizzazione del teorema di Banach sulle contrazioni, Mathematiche 23 (1968), 417-424.

Institute of Mathematics, Technical University of ódź, Żwirki 36, 90-924 ódź, Poland.

   E-mail address: jachym@ck-sg.p.lodz.pl