134
Mathematical Aspects of Logic Programming Semantics
λ
n
Since the last summation here is dominated by
d(x 0 , x 1 ), we see that (x n )
1−λ
is a (forward) Cauchy sequence in X and therefore is an ω-orbit of T which
is Cauchy. Since X is complete, (x n ) has a limit x ω . Now, by continuity of T ,
we obtain x ω ∈ T (x ω ), and x ω is a fixed point of T , as required.
(b) Let x 0 ∈ X and x 1 ∈ T (x 0 ) satisfy d(x 0 , x 1 ) = 0. Since T is nonexpanding, there is x 2 ∈ T (x 1 ) with d(x 1 , x 2 ) ≤ d(x 0 , x 1 ) = 0. Inductively,
we obtain a sequence (x n ) such that x n+1 ∈ T (x n ) and d(x n , x n+k ) ≤
o k−1
i=0 d(x n+i , x n+i+1 ) = 0. Hence, (x n ) is an orbit of T which is forward
Cauchy and therefore has a limit x ω . By continuity of T again, we see that
x ω is a fixed point of T .
•
The proof given here of Part (a) of Theorem 4.13.3 is, up to the last
step, exactly the same as the first half of the proof of the multivalued Banach contraction mapping theorem, Theorem 4.11.2, established by Khamsi,
Kreinovich, and Misane, except that we are working with a quasimetric rather
than with a metric and therefore care needs to be taken that no use is made
of symmetry. On the other hand, the proof we give next of Theorem 4.11.2,
which roughly corresponds to the second half of the proof given by Khamsi,
Kreinovich, and Misane, is shorter and technically somewhat simpler than the
proof given by them.
Proof of Theorem 4.11.2 We show that the condition that T (x) is closed
for every x together with that of T being a contraction implies that T is
continuous, and the result then follows from Part (a) of Theorem 4.13.3.
First note that (X, d) being a complete metric space means that (X, d) is
complete as a quasimetric space, and obviously T satisfies Part (a) of Theorem
4.13.3. Now suppose that (x n ) is an orbit of T which is a forward Cauchy
sequence and, hence, a Cauchy sequence; we want to show that x ω ∈ T (x ω ),
where x ω is the limit of (x n ).
Since T is a contraction, for every n there exists y n ∈ T (x ω ) such that
d(x n+1 , y n ) ≤ λd(x n , x ω ). Therefore, d(y n , x ω ) ≤ d(y n , x n+1 ) + d(x n+1 , x ω ) ≤
λd(x n , x ω ) + d(x n+1 , x ω ). Hence, we have y n → x ω . But each y n ∈ T (x ω ),
and T (x) is closed for every x. Consequently, the limit x ω of the sequence y n
also belongs to T (x ω ). So, x ω ∈ T (x ω ), and it follows that T is continuous, as
required.
•
Thus, Theorem 4.13.3 contains, as a consequence, the multivalued Banach
contraction mapping theorem, Theorem 4.11.2, discussed earlier. It also contains a natural extension of Kleene’s theorem to multivalued mappings, Theorem 4.13.6 below, as we show next. Thus, Theorem 4.13.3 gives a unification
of metric and order-theoretic notions in direct analogy with the corresponding
unification given, in the single-valued case, by Theorem 4.6.3.
In order to proceed, we make some preliminary and elementary observations, as follows, concerning partially ordered sets and the quasimetrics they
carry, see Section 4.6. The proofs are straightforward and are omitted.
Mathematical Aspects of Logic Programming Semantics
λ
n
Since the last summation here is dominated by
d(x 0 , x 1 ), we see that (x n )
1−λ
is a (forward) Cauchy sequence in X and therefore is an ω-orbit of T which
is Cauchy. Since X is complete, (x n ) has a limit x ω . Now, by continuity of T ,
we obtain x ω ∈ T (x ω ), and x ω is a fixed point of T , as required.
(b) Let x 0 ∈ X and x 1 ∈ T (x 0 ) satisfy d(x 0 , x 1 ) = 0. Since T is nonexpanding, there is x 2 ∈ T (x 1 ) with d(x 1 , x 2 ) ≤ d(x 0 , x 1 ) = 0. Inductively,
we obtain a sequence (x n ) such that x n+1 ∈ T (x n ) and d(x n , x n+k ) ≤
o k−1
i=0 d(x n+i , x n+i+1 ) = 0. Hence, (x n ) is an orbit of T which is forward
Cauchy and therefore has a limit x ω . By continuity of T again, we see that
x ω is a fixed point of T .
•
The proof given here of Part (a) of Theorem 4.13.3 is, up to the last
step, exactly the same as the first half of the proof of the multivalued Banach contraction mapping theorem, Theorem 4.11.2, established by Khamsi,
Kreinovich, and Misane, except that we are working with a quasimetric rather
than with a metric and therefore care needs to be taken that no use is made
of symmetry. On the other hand, the proof we give next of Theorem 4.11.2,
which roughly corresponds to the second half of the proof given by Khamsi,
Kreinovich, and Misane, is shorter and technically somewhat simpler than the
proof given by them.
Proof of Theorem 4.11.2 We show that the condition that T (x) is closed
for every x together with that of T being a contraction implies that T is
continuous, and the result then follows from Part (a) of Theorem 4.13.3.
First note that (X, d) being a complete metric space means that (X, d) is
complete as a quasimetric space, and obviously T satisfies Part (a) of Theorem
4.13.3. Now suppose that (x n ) is an orbit of T which is a forward Cauchy
sequence and, hence, a Cauchy sequence; we want to show that x ω ∈ T (x ω ),
where x ω is the limit of (x n ).
Since T is a contraction, for every n there exists y n ∈ T (x ω ) such that
d(x n+1 , y n ) ≤ λd(x n , x ω ). Therefore, d(y n , x ω ) ≤ d(y n , x n+1 ) + d(x n+1 , x ω ) ≤
λd(x n , x ω ) + d(x n+1 , x ω ). Hence, we have y n → x ω . But each y n ∈ T (x ω ),
and T (x) is closed for every x. Consequently, the limit x ω of the sequence y n
also belongs to T (x ω ). So, x ω ∈ T (x ω ), and it follows that T is continuous, as
required.
•
Thus, Theorem 4.13.3 contains, as a consequence, the multivalued Banach
contraction mapping theorem, Theorem 4.11.2, discussed earlier. It also contains a natural extension of Kleene’s theorem to multivalued mappings, Theorem 4.13.6 below, as we show next. Thus, Theorem 4.13.3 gives a unification
of metric and order-theoretic notions in direct analogy with the corresponding
unification given, in the single-valued case, by Theorem 4.6.3.
In order to proceed, we make some preliminary and elementary observations, as follows, concerning partially ordered sets and the quasimetrics they
carry, see Section 4.6. The proofs are straightforward and are omitted.