124
Mathematical Aspects of Logic Programming Semantics
4.8.21 Proposition Let (X, �, Γ) be a spherically complete dislocated generalized ultrametric space, and let d denote the generalized ultrametric associated with �. Then d is spherically complete. However, if f is strictly contracting relative to d, it does not follow that f is necessarily strictly contracting
relative to �.
Proof: Let B be a chain of balls in d. If B contains a ball B = {x} for some
x ∈ X, then x is in the intersection of the chain. So assume that all balls in
B contain more than one point.
Now let B γ (x m ) = {x | d(x, x m ) ≤ γ} be a ball in B, and let z ∈ B γ (x m )
with z = x m . Then �(x m , x m ) ≤ �(z, x m ) = d(z, x m ) ≤ γ; hence B γ (x m ) =
{x | �(x, x m ) ≤ γ}. It follows that B is also a chain of balls in � and, hence,
has non-empty intersection by spherical completeness of �, as required.
Let X = {0, 1}, and define a mapping f : X → X by f (x) = 0 for all
x ∈ X. Let � be constant and equal to 1. Then (X, �, {0, 1}), where 0 < 1,
is a spherically complete d-gum and f is strictly contracting relative to d.
However, �(f (0), f (1)) = �(0, 0) = �(0, 1), and so f is not strictly contracting
relative to �.
•
We can now use Theorem 4.3.6 to give an easy proof of Theorem 4.5.2,
as follows. With the notation used in Theorems 4.3.6 and 4.5.2 and using
Proposition 4.8.18, we obtain a generalized ultrametric space (X, d , Γ) which is
spherically complete by Proposition 4.8.21. By Proposition 4.8.20, the function
f is strictly contracting relative to d. Hence, by Theorem 4.3.6, f has a unique
fixed point.
We close this section by giving two constructions of d-gums from gums.
4.8.22 Proposition Let (X, d , Γ) be a generalized ultrametric space with
ordinal distances, and let u : X → Γ be a function. Then the distance function
� defined by
�(x, y) = max{d(x, y), u(x), u(y)}
is a dislocated generalized ultrametric on X.
Proof: (U2) and (U3) are trivial. For (U4), see the proof of Proposition 4.8.7.
•
This result will be applied in Section 5.1.3.
4.8.23 Proposition Let (X, d , Γ) be a generalized ultrametric space with
ordinal distances, let z ∈ X, and define the distance function � by
�(x, y) = max{d(x, z), d(y, z)}.
Then (X, � , Γ) is a spherically complete, dislocated generalized ultrametric
space.
Mathematical Aspects of Logic Programming Semantics
4.8.21 Proposition Let (X, �, Γ) be a spherically complete dislocated generalized ultrametric space, and let d denote the generalized ultrametric associated with �. Then d is spherically complete. However, if f is strictly contracting relative to d, it does not follow that f is necessarily strictly contracting
relative to �.
Proof: Let B be a chain of balls in d. If B contains a ball B = {x} for some
x ∈ X, then x is in the intersection of the chain. So assume that all balls in
B contain more than one point.
Now let B γ (x m ) = {x | d(x, x m ) ≤ γ} be a ball in B, and let z ∈ B γ (x m )
with z = x m . Then �(x m , x m ) ≤ �(z, x m ) = d(z, x m ) ≤ γ; hence B γ (x m ) =
{x | �(x, x m ) ≤ γ}. It follows that B is also a chain of balls in � and, hence,
has non-empty intersection by spherical completeness of �, as required.
Let X = {0, 1}, and define a mapping f : X → X by f (x) = 0 for all
x ∈ X. Let � be constant and equal to 1. Then (X, �, {0, 1}), where 0 < 1,
is a spherically complete d-gum and f is strictly contracting relative to d.
However, �(f (0), f (1)) = �(0, 0) = �(0, 1), and so f is not strictly contracting
relative to �.
•
We can now use Theorem 4.3.6 to give an easy proof of Theorem 4.5.2,
as follows. With the notation used in Theorems 4.3.6 and 4.5.2 and using
Proposition 4.8.18, we obtain a generalized ultrametric space (X, d , Γ) which is
spherically complete by Proposition 4.8.21. By Proposition 4.8.20, the function
f is strictly contracting relative to d. Hence, by Theorem 4.3.6, f has a unique
fixed point.
We close this section by giving two constructions of d-gums from gums.
4.8.22 Proposition Let (X, d , Γ) be a generalized ultrametric space with
ordinal distances, and let u : X → Γ be a function. Then the distance function
� defined by
�(x, y) = max{d(x, y), u(x), u(y)}
is a dislocated generalized ultrametric on X.
Proof: (U2) and (U3) are trivial. For (U4), see the proof of Proposition 4.8.7.
•
This result will be applied in Section 5.1.3.
4.8.23 Proposition Let (X, d , Γ) be a generalized ultrametric space with
ordinal distances, let z ∈ X, and define the distance function � by
�(x, y) = max{d(x, z), d(y, z)}.
Then (X, � , Γ) is a spherically complete, dislocated generalized ultrametric
space.