116
Mathematical Aspects of Logic Programming Semantics
and let T be defined as in Example 4.8.4. Then the construction in Proposition
4.8.2 yields a d-metric � such that
�([a, b], [c, d]) = max{b, d} − min{a, c}
for all [a, b], [c, d] ∈ I.
Indeed, we obtain
1
1
1
1
�([a, b], [c, d]) = d([a, b], [c, d]) + b − a + d − c
2
2
2
2
1
= (|b − d| + b + d + |a − c| − a − c)
2
1
1
= (|b − d| + (b + d)) + (|a − c| − (a + c))
2
2
= max{b, d} − min{a, c}.
4.8.6 Example (R
+
0 , �) is a dislocated metric space, where � is defined by
�(x, y) = x + y.
The following proposition gives an alternative way of obtaining dultrametrics from ultrametrics. We will apply this later in Section 5.1.2.
4.8.7 Proposition Let (X, d) be an ultrametric space, and let u : X → R
be a function. Then (X, �), where
�(x, y) = max{d(x, y), u(x), u(y)}
+
0
for all x, y ∈ X, is a d-ultrametric, and �(x, x) = u(x) for all x ∈ X. If
u is continuous as a function on (X, d), then completeness of (X, d) implies
completeness of (X, �).
Proof: (M2) and (M3) are obvious.
(M5) We obtain for all x, y, z ∈ X
�(x, y) = max{d(x, y), u(x), u(y)}
≤ max{d(x, z), d(z, y), u(x), u(y)}
≤ max{d(x, z), u(x), u(z), d(z, y), u(y)}
= max{�(x, z), �(z, y)}.
For completeness, let (x n ) be a Cauchy sequence in (X, �). Then (x n ) is a
Cauchy sequence in (X, d) and converges to some x ∈ X. We then obtain
�(x n , x) = max{d(x n , x), u(x n ), u(x)} → u(x) as n → ∞. As in the proof of
Proposition 4.8.3, we obtain u(x) = 0, and this completes the proof.
•
We want to investigate next the relationship between Matthews’ theorem,
Theorem 4.4.6, and the Banach contraction mapping theorem, Theorem 4.2.3.