�
132
Mathematical Aspects of Logic Programming Semantics
We next present some results relating those just given to the notion of
spherical completeness we discussed earlier. Indeed, we show that if (X, ρ) is
a g-metric space with respect to V as given in Definition 4.3.2, then ρ is a
generalized ultrametric space, and vice-versa.
4.12.9 Proposition Let (X, ρ) be a complete g-metric space with respect to
V . Then X is spherically complete as an ultrametric space.
=
A
Proof: Let B
B v β (x β )
b
be a decreasing chain of balls in X, and without
β<α
loss of generality assume that
� it is strictly decreasing and that α is a limit
ordinal. We have to show that B = ∅. Let v = (v β ) β . Since B is a chain, it
is easy to see that (x β+1 ) β is v-Cauchy and therefore, by completeness of X,
(x β+1 ) v-clusters to some x ∈ X. By definition, this means that ρ(x β+1 , x) <
v β and therefore that x ∈ B v β (x β+1 ) = B v β (x β ) for all β. Thus, x ∈
In
� B. •
the opposite direction, we have the following result.
4.12.10 Proposition Let (X, ρ, V ) be a spherically complete, generalized
ultrametric space. Then X is complete as a g-metric space.
Proof: Let v= (v β ) be a decreasing family of elements of V which is, without
loss of generality, strictly decreasing, and let (x β ) be v-Cauchy. For v ∈ v,
u
'
for example, v = 2
−α , let v denote 2
−(α+1) . Then B =
/
is a
B v β (x β )
β
decreasing chain of balls in X. By spherical completeness, it has non-empty
'
intersection. Choose x ∈ B. Then for all β we obtain ρ (x β , x) ≤ v < v β ,
β
and so (x β ) v-clusters to x.
•
This means, by virtue of Theorem 4.12.2, that we can reformulate the
assumptions in Theorem 4.12.8 and thereby obtain the following result, which,
in fact, is a special case of a theorem of Prieß-Crampe and Ribenboim, see
[Prieß-Crampe and Ribenboim, 2000c, (3.4)].
4.12.11 Theorem Let X be a spherically complete, generalized ultrametric
space (with respect to V ), and let T be a multivalued, non-empty, and strictly
contracting mapping defined on X such that T (x) is spherically complete for
all x ∈ X. Then T has a fixed point.
4.13 Quasimetrics and Multivalued Mappings
We move next to study a multivalued version of the Rutten-Smyth theorem, Theorem 4.6.3. As a consequence, we obtain a multivalued version of
Kleene’s theorem, Theorem 1.1.9.
26
26 For further details, see [Hitzler and Seda, 1999c].
132
Mathematical Aspects of Logic Programming Semantics
We next present some results relating those just given to the notion of
spherical completeness we discussed earlier. Indeed, we show that if (X, ρ) is
a g-metric space with respect to V as given in Definition 4.3.2, then ρ is a
generalized ultrametric space, and vice-versa.
4.12.9 Proposition Let (X, ρ) be a complete g-metric space with respect to
V . Then X is spherically complete as an ultrametric space.
=
A
Proof: Let B
B v β (x β )
b
be a decreasing chain of balls in X, and without
β<α
loss of generality assume that
� it is strictly decreasing and that α is a limit
ordinal. We have to show that B = ∅. Let v = (v β ) β . Since B is a chain, it
is easy to see that (x β+1 ) β is v-Cauchy and therefore, by completeness of X,
(x β+1 ) v-clusters to some x ∈ X. By definition, this means that ρ(x β+1 , x) <
v β and therefore that x ∈ B v β (x β+1 ) = B v β (x β ) for all β. Thus, x ∈
In
� B. •
the opposite direction, we have the following result.
4.12.10 Proposition Let (X, ρ, V ) be a spherically complete, generalized
ultrametric space. Then X is complete as a g-metric space.
Proof: Let v= (v β ) be a decreasing family of elements of V which is, without
loss of generality, strictly decreasing, and let (x β ) be v-Cauchy. For v ∈ v,
u
'
for example, v = 2
−α , let v denote 2
−(α+1) . Then B =
/
is a
B v β (x β )
β
decreasing chain of balls in X. By spherical completeness, it has non-empty
'
intersection. Choose x ∈ B. Then for all β we obtain ρ (x β , x) ≤ v < v β ,
β
and so (x β ) v-clusters to x.
•
This means, by virtue of Theorem 4.12.2, that we can reformulate the
assumptions in Theorem 4.12.8 and thereby obtain the following result, which,
in fact, is a special case of a theorem of Prieß-Crampe and Ribenboim, see
[Prieß-Crampe and Ribenboim, 2000c, (3.4)].
4.12.11 Theorem Let X be a spherically complete, generalized ultrametric
space (with respect to V ), and let T be a multivalued, non-empty, and strictly
contracting mapping defined on X such that T (x) is spherically complete for
all x ∈ X. Then T has a fixed point.
4.13 Quasimetrics and Multivalued Mappings
We move next to study a multivalued version of the Rutten-Smyth theorem, Theorem 4.6.3. As a consequence, we obtain a multivalued version of
Kleene’s theorem, Theorem 1.1.9.
26
26 For further details, see [Hitzler and Seda, 1999c].