135
Fixed-Point Theory for Generalized Metric Spaces
4.13.4 Proposition Let (X, ≤) be a partial order, and let (X, d) denote the
associated quasimetric space, so that d = d ≤ as in Section 4.6. Then the
following hold.
(a) A non-empty multivalued mapping T : X → P(X) is Hoare monotonic if
and only if it is non-expanding.
(b) A sequence (x n ) in X is eventually increasing in (X, ≤) if and only if it
is a Cauchy sequence in (X, d).
(c) The partially ordered set (X, ≤) is ω-complete if and only if (X, d) is
complete as a quasimetric space. Furthermore, in the presence of either
form of completeness, the limit of any Cauchy sequence is the least upper
bound of any increasing tail of the sequence.
Notice that neither Part (c) of this result nor the next definition assumes
the presence of a bottom element.
4.13.5 Definition Let the partial order (X, ≤) be ω-complete, and let T :
X → P(X) be a non-empty multivalued mapping on X. We say that T is
ω-continuous if T is Hoare monotonic, and for any ω-orbit (x n ) of T which
is eventually increasing, we have (x n ) ∈ T ( (x n )), where the supremum is
taken over any increasing tail of (x n ).
We obtain finally the following form of Kleene’s theorem for multivalued
mappings as an easy corollary of our Theorem 4.13.3. This theorem has been
applied by the present authors to find answer sets for certain classes of disjunctive logic programs, see [Hitzler and Seda, 1999c].
4.13.6 Theorem (Kleene multivalued) Let (X, ≤) be an ω-complete partial order (with bottom element), and let T : X → P(X) be a non-empty,
ω-continuous multivalued mapping on X. Then T has a fixed point.
Proof: Since (X, ≤) is ω-complete, the associated quasimetric space (X, d)
(with d = d ≤ as in Section 4.6) is complete by Proposition 4.13.4. Furthermore,
T is Hoare monotonic, since it is ω-continuous and is therefore non-expanding
by Proposition 4.13.4 again. On taking x 0 = ⊥ and x 1 ∈ T (x 0 ) arbitrarily,
we have x 0 and x 1 satisfying d(x 0 , x 1 ) = 0. The result will therefore follow
from Part (b) of Theorem 4.13.3 as soon as we have established that T is
continuous in the sense of Definition 4.13.2.
Let (x n ) be any ω-orbit of T which is a Cauchy sequence. Then (x n ) is
eventually increasing, and, by ω-continuity of T , we have (x n ) ∈ T ( (x n )),
where the supremum is taken over any increasing tail of (x n ). In other words,
we have lim x n ∈ T (lim x n ), and hence we have the continuity of T that we
require.
•
Kleene’s theorem for single-valued mappings T asserts that the fixed point
produced by the usual proof is the least fixed point of T . This assertion does
Fixed-Point Theory for Generalized Metric Spaces
4.13.4 Proposition Let (X, ≤) be a partial order, and let (X, d) denote the
associated quasimetric space, so that d = d ≤ as in Section 4.6. Then the
following hold.
(a) A non-empty multivalued mapping T : X → P(X) is Hoare monotonic if
and only if it is non-expanding.
(b) A sequence (x n ) in X is eventually increasing in (X, ≤) if and only if it
is a Cauchy sequence in (X, d).
(c) The partially ordered set (X, ≤) is ω-complete if and only if (X, d) is
complete as a quasimetric space. Furthermore, in the presence of either
form of completeness, the limit of any Cauchy sequence is the least upper
bound of any increasing tail of the sequence.
Notice that neither Part (c) of this result nor the next definition assumes
the presence of a bottom element.
4.13.5 Definition Let the partial order (X, ≤) be ω-complete, and let T :
X → P(X) be a non-empty multivalued mapping on X. We say that T is
ω-continuous if T is Hoare monotonic, and for any ω-orbit (x n ) of T which
is eventually increasing, we have (x n ) ∈ T ( (x n )), where the supremum is
taken over any increasing tail of (x n ).
We obtain finally the following form of Kleene’s theorem for multivalued
mappings as an easy corollary of our Theorem 4.13.3. This theorem has been
applied by the present authors to find answer sets for certain classes of disjunctive logic programs, see [Hitzler and Seda, 1999c].
4.13.6 Theorem (Kleene multivalued) Let (X, ≤) be an ω-complete partial order (with bottom element), and let T : X → P(X) be a non-empty,
ω-continuous multivalued mapping on X. Then T has a fixed point.
Proof: Since (X, ≤) is ω-complete, the associated quasimetric space (X, d)
(with d = d ≤ as in Section 4.6) is complete by Proposition 4.13.4. Furthermore,
T is Hoare monotonic, since it is ω-continuous and is therefore non-expanding
by Proposition 4.13.4 again. On taking x 0 = ⊥ and x 1 ∈ T (x 0 ) arbitrarily,
we have x 0 and x 1 satisfying d(x 0 , x 1 ) = 0. The result will therefore follow
from Part (b) of Theorem 4.13.3 as soon as we have established that T is
continuous in the sense of Definition 4.13.2.
Let (x n ) be any ω-orbit of T which is a Cauchy sequence. Then (x n ) is
eventually increasing, and, by ω-continuity of T , we have (x n ) ∈ T ( (x n )),
where the supremum is taken over any increasing tail of (x n ). In other words,
we have lim x n ∈ T (lim x n ), and hence we have the continuity of T that we
require.
•
Kleene’s theorem for single-valued mappings T asserts that the fixed point
produced by the usual proof is the least fixed point of T . This assertion does