�
100
Mathematical Aspects of Logic Programming Semantics
4.3.6 Theorem (Prieß-Crampe and Ribenboim) Let (X, �, Γ) be a
spherically complete generalized ultrametric space, and let f : X → X be
non-expanding and strictly contracting on orbits. Then f has a fixed point.
Moreover, if f is strictly contracting on X, then f has a unique fixed point.
Note that every compact ultrametric space is spherically complete by the
finite intersection property. The converse is not true: let X be an infinite set,
and let d be the ultrametric defined by setting d(x, y) = 1 if x = y and
taking d(x, x) = 0 for all x ∈ X. Then (X, d) is not compact but is spherically
complete.
The relationship between spherical completeness and completeness is given
by the next proposition.
13
4.3.7 Proposition Let (X, d) be an ultrametric space. If X is spherically
complete, then it is complete. The converse does not hold in general.
Proof: Assume that (X, d) is spherically complete and that (x n ) is a Cauchy
sequence in (X, d). Then, for every k ∈ N, there exists a least n k ∈ N such
1
that for all n, m ≥ n k we have d(x n , x m ) ≤ . We note that n k increases
: k
with k. Now consider the set of balls B = B 1 (x n k ) | k ∈ N . By (U4), B
k
is a decreasing chain of balls and has non-empty intersection B by spherical
completeness of (X, d). Let a ∈ B. Then it is easy to see that (x n ) converges
to a. Hence, B = {a} is a one-point set since limits in (X, d) are unique.
Therefore, (X, d) is complete.
In order to show that the converse does not hold in general, define an
ultrametric d on N as follows. For n, m ∈ N, let d(n, m) = 1 + 2
− min{m,n}
if n = m, and set d(n, n) = 0 for all n ∈ N. The topology induced by d is
the discrete topology on N, and the Cauchy sequences with respect to d are
exactly the sequences which are eventually constant; hence, (N, d) is complete.
Now consider the chain of balls B n of the form {m ∈ N | d(m, n) ≤ 1 + 2
−n }.
Then we obtain B n = {m | m ≥ n} for all n ∈ N. Hence, B n = ∅.
•
Note also that, with the notation from the second part of the proof, the
successor function n � → n + 1 is strictly contracting, but does not have a fixed
point. By Proposition 4.3.7 and the remarks preceding it, we see that the
notion of spherical completeness is strictly less general than completeness and
is strictly more general than compactness.
Spherical completeness can also be characterized by means of transfinite
sequences, and we consider this next.
14
13 Similar studies of this issue have been undertaken in [Prieß-Crampe, 1990] in the case of
totally ordered distance sets. The topology of generalized ultrametric spaces is investigated
in [Heckmanns, 1996].
14 Here, we follow a line of thought developed in [Prieß-Crampe, 1990], only slightly
changed (the original version was established under the assumption that the distance sets
in question were linearly ordered) and with the proofs adapted to the more general setting.
100
Mathematical Aspects of Logic Programming Semantics
4.3.6 Theorem (Prieß-Crampe and Ribenboim) Let (X, �, Γ) be a
spherically complete generalized ultrametric space, and let f : X → X be
non-expanding and strictly contracting on orbits. Then f has a fixed point.
Moreover, if f is strictly contracting on X, then f has a unique fixed point.
Note that every compact ultrametric space is spherically complete by the
finite intersection property. The converse is not true: let X be an infinite set,
and let d be the ultrametric defined by setting d(x, y) = 1 if x = y and
taking d(x, x) = 0 for all x ∈ X. Then (X, d) is not compact but is spherically
complete.
The relationship between spherical completeness and completeness is given
by the next proposition.
13
4.3.7 Proposition Let (X, d) be an ultrametric space. If X is spherically
complete, then it is complete. The converse does not hold in general.
Proof: Assume that (X, d) is spherically complete and that (x n ) is a Cauchy
sequence in (X, d). Then, for every k ∈ N, there exists a least n k ∈ N such
1
that for all n, m ≥ n k we have d(x n , x m ) ≤ . We note that n k increases
: k
with k. Now consider the set of balls B = B 1 (x n k ) | k ∈ N . By (U4), B
k
is a decreasing chain of balls and has non-empty intersection B by spherical
completeness of (X, d). Let a ∈ B. Then it is easy to see that (x n ) converges
to a. Hence, B = {a} is a one-point set since limits in (X, d) are unique.
Therefore, (X, d) is complete.
In order to show that the converse does not hold in general, define an
ultrametric d on N as follows. For n, m ∈ N, let d(n, m) = 1 + 2
− min{m,n}
if n = m, and set d(n, n) = 0 for all n ∈ N. The topology induced by d is
the discrete topology on N, and the Cauchy sequences with respect to d are
exactly the sequences which are eventually constant; hence, (N, d) is complete.
Now consider the chain of balls B n of the form {m ∈ N | d(m, n) ≤ 1 + 2
−n }.
Then we obtain B n = {m | m ≥ n} for all n ∈ N. Hence, B n = ∅.
•
Note also that, with the notation from the second part of the proof, the
successor function n � → n + 1 is strictly contracting, but does not have a fixed
point. By Proposition 4.3.7 and the remarks preceding it, we see that the
notion of spherical completeness is strictly less general than completeness and
is strictly more general than compactness.
Spherical completeness can also be characterized by means of transfinite
sequences, and we consider this next.
14
13 Similar studies of this issue have been undertaken in [Prieß-Crampe, 1990] in the case of
totally ordered distance sets. The topology of generalized ultrametric spaces is investigated
in [Heckmanns, 1996].
14 Here, we follow a line of thought developed in [Prieß-Crampe, 1990], only slightly
changed (the original version was established under the assumption that the distance sets
in question were linearly ordered) and with the proofs adapted to the more general setting.