127
Fixed-Point Theory for Generalized Metric Spaces
In fact, it turns out that the majority of the fixed-point theorems we have
already considered earlier in this chapter can be directly carried over to the
multivalued setting, and indeed our main task now is to carry out this extension. Thus, we present multivalued versions of the Knaster-Tarski theorem, the
Banach contraction mapping theorem, the Rutten-Smyth theorem referred to
in the previous paragraph, and Kleene’s theorem. We do not, however, include
any applications of these results here, although they do indeed have a number
of applications to the semantics of (conventional) disjunctive logic programs,
see [Khamsi et al., 1993, Khamsi and Misane, 1998, Hitzler and Seda, 1999c,
Hitzler and Seda, 2002a].
4.10 Partial Orders and Multivalued Mappings
Throughout, T : X → P(X) will denote a multivalued mapping defined
on X. Furthermore, unless stated to the contrary, T will be assumed to be
non-empty.
We begin by discussing a fixed-point theorem first established by M.A.
Khamsi and D. Misane, see [Khamsi and Misane, 1998]. It can be viewed as a
multivalued version of the Knaster-Tarski theorem, Theorem 1.1.10; a multivalued version of Kleene’s theorem, Theorem 1.1.9 will be presented in Section
4.13.
4.10.1 Definition Let T : X → P(X) be a multivalued mapping defined on
X. An orbit of T is a net (x i ) i∈I in X, where I denotes an ordinal, such that
x i+1 ∈ T (x i ) for all i ∈ I. An orbit (x i ) i∈I of T is called an ω-orbit if I is
the first limit ordinal, ω. An orbit (x i ) i∈I of T will be said to be eventually
constant if there is a tail (x i ) i0≤i of (x i ) i∈I which is constant in that x i = x j
for all i, j ∈ I satisfying i 0 ≤ i, j.
If T : X → P(X) is a multivalued mapping and x is a fixed point of T ,
then we obtain an orbit of T which is eventually constant by setting x =
x 0 = x 1 = x 2 . . .. Conversely, suppose that (x i ) i∈I is an orbit of T with the
property that x i+1 = x i for all i ∈ I satisfying i 0 ≤ i, for some ordinal i 0 ∈ I.
Then x i0 = x i0+1 ∈ T (x i0 ), and we have a fixed point x i0 of T . Thus, having
a fixed point and having an orbit which is eventually constant are essentially
equivalent conditions on T .
4.10.2 Definition Suppose that T is a multivalued mapping defined on a
partially ordered set X. An orbit (x i ) i∈I of T is said to be increasing if we have
x i ≤ x j for all i, j ∈ I satisfying i ≤ j and is said to be eventually increasing
if some tail of the orbit is increasing. Finally, an increasing orbit (x i ) i∈I of T
is said to be tight if, for all limit ordinals j ∈ I, we have x j = {x i | i < j}.
Fixed-Point Theory for Generalized Metric Spaces
In fact, it turns out that the majority of the fixed-point theorems we have
already considered earlier in this chapter can be directly carried over to the
multivalued setting, and indeed our main task now is to carry out this extension. Thus, we present multivalued versions of the Knaster-Tarski theorem, the
Banach contraction mapping theorem, the Rutten-Smyth theorem referred to
in the previous paragraph, and Kleene’s theorem. We do not, however, include
any applications of these results here, although they do indeed have a number
of applications to the semantics of (conventional) disjunctive logic programs,
see [Khamsi et al., 1993, Khamsi and Misane, 1998, Hitzler and Seda, 1999c,
Hitzler and Seda, 2002a].
4.10 Partial Orders and Multivalued Mappings
Throughout, T : X → P(X) will denote a multivalued mapping defined
on X. Furthermore, unless stated to the contrary, T will be assumed to be
non-empty.
We begin by discussing a fixed-point theorem first established by M.A.
Khamsi and D. Misane, see [Khamsi and Misane, 1998]. It can be viewed as a
multivalued version of the Knaster-Tarski theorem, Theorem 1.1.10; a multivalued version of Kleene’s theorem, Theorem 1.1.9 will be presented in Section
4.13.
4.10.1 Definition Let T : X → P(X) be a multivalued mapping defined on
X. An orbit of T is a net (x i ) i∈I in X, where I denotes an ordinal, such that
x i+1 ∈ T (x i ) for all i ∈ I. An orbit (x i ) i∈I of T is called an ω-orbit if I is
the first limit ordinal, ω. An orbit (x i ) i∈I of T will be said to be eventually
constant if there is a tail (x i ) i0≤i of (x i ) i∈I which is constant in that x i = x j
for all i, j ∈ I satisfying i 0 ≤ i, j.
If T : X → P(X) is a multivalued mapping and x is a fixed point of T ,
then we obtain an orbit of T which is eventually constant by setting x =
x 0 = x 1 = x 2 . . .. Conversely, suppose that (x i ) i∈I is an orbit of T with the
property that x i+1 = x i for all i ∈ I satisfying i 0 ≤ i, for some ordinal i 0 ∈ I.
Then x i0 = x i0+1 ∈ T (x i0 ), and we have a fixed point x i0 of T . Thus, having
a fixed point and having an orbit which is eventually constant are essentially
equivalent conditions on T .
4.10.2 Definition Suppose that T is a multivalued mapping defined on a
partially ordered set X. An orbit (x i ) i∈I of T is said to be increasing if we have
x i ≤ x j for all i, j ∈ I satisfying i ≤ j and is said to be eventually increasing
if some tail of the orbit is increasing. Finally, an increasing orbit (x i ) i∈I of T
is said to be tight if, for all limit ordinals j ∈ I, we have x j = {x i | i < j}.