107
Fixed-Point Theory for Generalized Metric Spaces
4.6.3 Theorem (Rutten-Smyth) Let (X, d) be a CS-complete quasimetric
space, and let f : X → X be non-expanding.
(a) If f is CS-continuous and there exists x ∈ X with x ≤ d f (x), then f has
a fixed point, and this fixed point is least above x with respect to ≤ d .
(b) If f is CS-continuous and contractive, then f has a unique fixed point.
Moreover, in both cases the fixed point can be obtained as the limit of the
Cauchy sequence (f
n (x)), where in (a) x is the given point, and in (b) x can
be chosen arbitrarily.
Proof: (a) For all n, k ∈ N and k ≥ 1, we have d(f
n (x), f
n+1 (x)) ≤
d(x, f (x)) = 0 and d(f
n (x), f
n+k (x)) ≤
o k−1
n+i
n+i+1
i=0 d(f
(x), f
(x)) = 0.
Hence, (f
n (x)) is a Cauchy sequence and has a unique limit y, say. Since
f (y) = f (lim f
n (x)) = lim f (f
n (x)) = lim f
n (x) = y, y is a fixed point of f .
Now let z be a fixed point of f with x
n
n
≤
n
d z. Then d(y, z) = lim d(f (x), z) = 0,
since d(f (x), f (z)) ≤ d(x, z) = 0. Hence, y ≤ d z.
(b) The proof given for Theorem 4.2.3 does not depend on condition (M3)
other than implicitly for deriving continuity of f from the fact that it is a
contraction. Since CS-continuity is a hypothesis in statement (b), the proof
of Theorem 4.2.3 can be carried over by simply replacing “Cauchy sequence”
by “forward Cauchy sequence” and “continuous” by “CS-continuous”, etc. •
4.6.4 Example Let (X, ≤) be a partially ordered set. Define a function d ≤
on X × X by
0 if x ≤ y,
d ≤ (x, y) =
1 otherwise.
Then it is easily checked that (X, d ≤ ) is a quasi-ultrametric space; we call d ≤
the discrete quasimetric on X. Note that ≤ d ≤ and ≤ coincide for a given partial order ≤, and moreover (X, d) is totally bounded if and only if X is finite.
By virtue of this definition and the definition of ≤ d for a given quasimetric
d, Part (a) of Theorem 4.6.3 generalizes Kleene’s theorem, Theorem 1.1.9,
and Part (b) of Theorem 4.6.3 generalizes the Banach contraction mapping
theorem, Theorem 4.2.3.
19
4.6.5 Example Note that it is easy to see that a sequence (I n ) in I P,2 is forward Cauchy relative to the discrete quasimetric d if and only if it is eventually
increasing in the sense that there is a natural number k with the property that
I n ⊆ I n+1 whenever k ≤ n, see [Seda, 1997, Proposition 1].
Consider the sequence (I n ) in the power set P(N) of the natural numbers
determined by setting I n = N if n is even and setting I n = {0} otherwise.
Then {0} is the greatest limit, gl(I n ), of (I n ), yet (I n ) is not forward Cauchy
19 For further observations on this point, see [Smyth, 1987, Rutten, 1996].
Fixed-Point Theory for Generalized Metric Spaces
4.6.3 Theorem (Rutten-Smyth) Let (X, d) be a CS-complete quasimetric
space, and let f : X → X be non-expanding.
(a) If f is CS-continuous and there exists x ∈ X with x ≤ d f (x), then f has
a fixed point, and this fixed point is least above x with respect to ≤ d .
(b) If f is CS-continuous and contractive, then f has a unique fixed point.
Moreover, in both cases the fixed point can be obtained as the limit of the
Cauchy sequence (f
n (x)), where in (a) x is the given point, and in (b) x can
be chosen arbitrarily.
Proof: (a) For all n, k ∈ N and k ≥ 1, we have d(f
n (x), f
n+1 (x)) ≤
d(x, f (x)) = 0 and d(f
n (x), f
n+k (x)) ≤
o k−1
n+i
n+i+1
i=0 d(f
(x), f
(x)) = 0.
Hence, (f
n (x)) is a Cauchy sequence and has a unique limit y, say. Since
f (y) = f (lim f
n (x)) = lim f (f
n (x)) = lim f
n (x) = y, y is a fixed point of f .
Now let z be a fixed point of f with x
n
n
≤
n
d z. Then d(y, z) = lim d(f (x), z) = 0,
since d(f (x), f (z)) ≤ d(x, z) = 0. Hence, y ≤ d z.
(b) The proof given for Theorem 4.2.3 does not depend on condition (M3)
other than implicitly for deriving continuity of f from the fact that it is a
contraction. Since CS-continuity is a hypothesis in statement (b), the proof
of Theorem 4.2.3 can be carried over by simply replacing “Cauchy sequence”
by “forward Cauchy sequence” and “continuous” by “CS-continuous”, etc. •
4.6.4 Example Let (X, ≤) be a partially ordered set. Define a function d ≤
on X × X by
0 if x ≤ y,
d ≤ (x, y) =
1 otherwise.
Then it is easily checked that (X, d ≤ ) is a quasi-ultrametric space; we call d ≤
the discrete quasimetric on X. Note that ≤ d ≤ and ≤ coincide for a given partial order ≤, and moreover (X, d) is totally bounded if and only if X is finite.
By virtue of this definition and the definition of ≤ d for a given quasimetric
d, Part (a) of Theorem 4.6.3 generalizes Kleene’s theorem, Theorem 1.1.9,
and Part (b) of Theorem 4.6.3 generalizes the Banach contraction mapping
theorem, Theorem 4.2.3.
19
4.6.5 Example Note that it is easy to see that a sequence (I n ) in I P,2 is forward Cauchy relative to the discrete quasimetric d if and only if it is eventually
increasing in the sense that there is a natural number k with the property that
I n ⊆ I n+1 whenever k ≤ n, see [Seda, 1997, Proposition 1].
Consider the sequence (I n ) in the power set P(N) of the natural numbers
determined by setting I n = N if n is even and setting I n = {0} otherwise.
Then {0} is the greatest limit, gl(I n ), of (I n ), yet (I n ) is not forward Cauchy
19 For further observations on this point, see [Smyth, 1987, Rutten, 1996].