118
Mathematical Aspects of Logic Programming Semantics
4.8.11 Proposition Let (X, �) be a complete d-metric space, and let d denote the metric associated with �. Then the metric d is complete. However,
if f is a contraction relative to d, it does not follow that f is necessarily a
contraction relative to �.
Proof: Let (x n ) be a Cauchy sequence in d. If (x n ) eventually becomes constant, then it obviously converges in d. So, assume that this is not the case.
Then the sequence (x n ) must contain infinitely many distinct points; otherwise, it would not be a Cauchy sequence. We define a subsequence (y n ) of (x n )
which is obtained by removing multiple occurrences of points in (x n ). For each
n ∈ N, let y n = x k , where k is minimal with the property that, for all m < n,
we have y m = x k . Since (y n ) is a subsequence of the Cauchy sequence (x n ),
we see that (y n ) is also a Cauchy sequence relative to d. But, for any two
elements y, z in the sequence (y n ), we have that d(y, z) = �(y, z) by definition
of d. Therefore, (y n ) is a Cauchy sequence in � and, hence, converges in � to
some y ω ∈ X. So, (y n ) also converges in d to y ω . We show that (x n ) converges
to y ω in d. Let ε > 0 be chosen arbitrarily. Since (x n ) is a Cauchy sequence
ε
with respect to d, there exists an index n 1 such that d(x k , x m ) < for all
2
k, m ≥ n 1 . Since (y n ) converges to y ω in �, we also know that there is an index
ε
n 2 with y n2 = x n3 for some index n 3 such that n 3 ≥ n 1 and d(y n2 , y ω ) < .
2
For all x n with n ≥ n 3 , we then obtain d(x n , y ω ) ≤ d(x n , x n3 )+d(x n3 , y ω ) < ε,
as required.
Let X = {0, 1}, and define the mapping f : X → X by setting f (x) = 0
for all x ∈ X. Let � be constant and equal to 1. Then � is a complete d-metric,
and f is a contraction relative to d. However, �(f (0), f (1)) = �(0, 0) = �(0, 1),
and so f is not a contraction relative to �.
•
The results we have just established put us in a position to prove Matthews’
theorem, Theorem 4.4.6, by using the Banach contraction mapping theorem,
Theorem 4.2.3, and this we do next.
Proof of Theorem 4.4.6 Let (X, �) be a complete d-metric space, and let f
be a contraction relative to �. Let d be the metric associated with �. Then d is
a complete metric, and f is a contraction relative to d. Hence, f has a unique
fixed point by the Banach contraction mapping theorem, Theorem 4.2.3. •
4.8.2 Domains as GUMS
It is our intention here to cast Scott domains into ultrametric spaces, a
construction we will use later in Chapter 5. Usually, domains are endowed with
the Scott topology, see Section A.6. However, as we will see next, domains can
be endowed with the structure of a spherically complete ultrametric space.
This is not something normally considered in domain theory. However, as
already noted at the beginning of the chapter, one of the objectives of the
chapter is to discuss a variety of distance functions, including (generalized)
Mathematical Aspects of Logic Programming Semantics
4.8.11 Proposition Let (X, �) be a complete d-metric space, and let d denote the metric associated with �. Then the metric d is complete. However,
if f is a contraction relative to d, it does not follow that f is necessarily a
contraction relative to �.
Proof: Let (x n ) be a Cauchy sequence in d. If (x n ) eventually becomes constant, then it obviously converges in d. So, assume that this is not the case.
Then the sequence (x n ) must contain infinitely many distinct points; otherwise, it would not be a Cauchy sequence. We define a subsequence (y n ) of (x n )
which is obtained by removing multiple occurrences of points in (x n ). For each
n ∈ N, let y n = x k , where k is minimal with the property that, for all m < n,
we have y m = x k . Since (y n ) is a subsequence of the Cauchy sequence (x n ),
we see that (y n ) is also a Cauchy sequence relative to d. But, for any two
elements y, z in the sequence (y n ), we have that d(y, z) = �(y, z) by definition
of d. Therefore, (y n ) is a Cauchy sequence in � and, hence, converges in � to
some y ω ∈ X. So, (y n ) also converges in d to y ω . We show that (x n ) converges
to y ω in d. Let ε > 0 be chosen arbitrarily. Since (x n ) is a Cauchy sequence
ε
with respect to d, there exists an index n 1 such that d(x k , x m ) < for all
2
k, m ≥ n 1 . Since (y n ) converges to y ω in �, we also know that there is an index
ε
n 2 with y n2 = x n3 for some index n 3 such that n 3 ≥ n 1 and d(y n2 , y ω ) < .
2
For all x n with n ≥ n 3 , we then obtain d(x n , y ω ) ≤ d(x n , x n3 )+d(x n3 , y ω ) < ε,
as required.
Let X = {0, 1}, and define the mapping f : X → X by setting f (x) = 0
for all x ∈ X. Let � be constant and equal to 1. Then � is a complete d-metric,
and f is a contraction relative to d. However, �(f (0), f (1)) = �(0, 0) = �(0, 1),
and so f is not a contraction relative to �.
•
The results we have just established put us in a position to prove Matthews’
theorem, Theorem 4.4.6, by using the Banach contraction mapping theorem,
Theorem 4.2.3, and this we do next.
Proof of Theorem 4.4.6 Let (X, �) be a complete d-metric space, and let f
be a contraction relative to �. Let d be the metric associated with �. Then d is
a complete metric, and f is a contraction relative to d. Hence, f has a unique
fixed point by the Banach contraction mapping theorem, Theorem 4.2.3. •
4.8.2 Domains as GUMS
It is our intention here to cast Scott domains into ultrametric spaces, a
construction we will use later in Chapter 5. Usually, domains are endowed with
the Scott topology, see Section A.6. However, as we will see next, domains can
be endowed with the structure of a spherically complete ultrametric space.
This is not something normally considered in domain theory. However, as
already noted at the beginning of the chapter, one of the objectives of the
chapter is to discuss a variety of distance functions, including (generalized)