96
Mathematical Aspects of Logic Programming Semantics
(4) We show that (X, d) is an ultrametric space. (M1) Let d(x, y) = 0, and
assume that x = y. Then we have δ(x, y) = d(x, y) = 0. Therefore, we obtain
max{ι(l(x)), ι(l(y))} = 0, so ι(l(x)) = ι(l(y)) = 0. Hence, l(x) = l(y) = ∞
and x = y = a by construction of l, which is a contradiction.
(M2) This is true by definition of d.
(M3) This is true by symmetry of δ and, hence, of d.
(M5) Let x, y, z ∈ X. Assume without loss of generality that ι(l(x)) <
ι(l(z)) so that d(x, z) = ι(l(z)). If ι(l(y)) ≤ ι(l(z)), then d(y, z) = ι(l(z)).
If ι(l(y)) > ι(l(z)), then d(y, z) = ι(l(y)) > ι(l(z)). In both cases we get
d(y, z) ≥ d(x, z), as required.
(5) (X, d) is complete as a metric space. In order to show this, let (x n ) be
a Cauchy sequence in X. If (x n ) is eventually constant, then it converges trivially. So now assume that (x n ) is not eventually constant. We proceed to show
that x n converges to a in d, for which it suffices to show that (ι(l(x n ))) n∈N
converges to 0. Let ε > 0. Then there exists n 0 ∈ N such that for all m, n ≥ n 0
we have d(x m , x n ) < ε. In particular, we have d(x m , x n0 ) < ε for all m ≥ n 0 ,
and, since (x n ) is not eventually constant, we thus obtain ι(l(x n0 )) < ε and
also ι(l(x m )) < ε for all m ≥ n 0 . Since ε was chosen arbitrarily, we see that
(ι(l(x n ))) n∈N converges to 0.
(6) We note that for f (x) = a, we have l(f (x)) = l(x) + 1 by definition of
l, and hence ι(l(f (x))) =
1
2 ι(l(x)).
(7) For all x, y ∈ X, we have that d(f (x), f (y)) ≤
1
2 d(x, y). In order
to establish this claim, let x, y ∈ X, and assume without loss of generality
1
2
−k
that x = y. Now let d(x, y) = 2
−k , say, so that max{ι(l(x)), ι(l(y))} =
.
max{ι(l(f (x))), ι(l(f (y)))} = max{ι(l(x)), ι(l(y))}
Then d(f (x), f (y)) =
2
1
2 d(x, y), as required.
=
•
It should be noted that Theorem 4.2.5 is not a true converse of the Banach
theorem in that we do not start out with a metrizable space and attempt to
obtain a metric for it relative to which f is a contraction. Thus, Theorem 4.2.5
is quite different from those discussed, for example, in Section 3.6 of the text
[Istr˘ at ¸escu, 1981], in which a number of converses of the Banach theorem are
considered. Even the result of Bessaga discussed there, which applies to an
abstract set, is very different from ours in that we do not require all iterations
of f to have a unique fixed point, but we do require topological convergence of
the iterates of any point. Indeed, we can only make the following observations
on the relationship between the original topology and the one created by the
metric constructed in the proof of Theorem 4.2.5.
4.2.6 Proposition With the notation of the proof of Theorem 4.2.5, the
following hold.
(a) Any x = a is an isolated point with respect to d, that is, {x} is open and
closed in the topology generated by d.
(b) If (x n ) is a sequence in X which converges in d to some x = a, then the
sequence (x n ) is eventually constant.
Mathematical Aspects of Logic Programming Semantics
(4) We show that (X, d) is an ultrametric space. (M1) Let d(x, y) = 0, and
assume that x = y. Then we have δ(x, y) = d(x, y) = 0. Therefore, we obtain
max{ι(l(x)), ι(l(y))} = 0, so ι(l(x)) = ι(l(y)) = 0. Hence, l(x) = l(y) = ∞
and x = y = a by construction of l, which is a contradiction.
(M2) This is true by definition of d.
(M3) This is true by symmetry of δ and, hence, of d.
(M5) Let x, y, z ∈ X. Assume without loss of generality that ι(l(x)) <
ι(l(z)) so that d(x, z) = ι(l(z)). If ι(l(y)) ≤ ι(l(z)), then d(y, z) = ι(l(z)).
If ι(l(y)) > ι(l(z)), then d(y, z) = ι(l(y)) > ι(l(z)). In both cases we get
d(y, z) ≥ d(x, z), as required.
(5) (X, d) is complete as a metric space. In order to show this, let (x n ) be
a Cauchy sequence in X. If (x n ) is eventually constant, then it converges trivially. So now assume that (x n ) is not eventually constant. We proceed to show
that x n converges to a in d, for which it suffices to show that (ι(l(x n ))) n∈N
converges to 0. Let ε > 0. Then there exists n 0 ∈ N such that for all m, n ≥ n 0
we have d(x m , x n ) < ε. In particular, we have d(x m , x n0 ) < ε for all m ≥ n 0 ,
and, since (x n ) is not eventually constant, we thus obtain ι(l(x n0 )) < ε and
also ι(l(x m )) < ε for all m ≥ n 0 . Since ε was chosen arbitrarily, we see that
(ι(l(x n ))) n∈N converges to 0.
(6) We note that for f (x) = a, we have l(f (x)) = l(x) + 1 by definition of
l, and hence ι(l(f (x))) =
1
2 ι(l(x)).
(7) For all x, y ∈ X, we have that d(f (x), f (y)) ≤
1
2 d(x, y). In order
to establish this claim, let x, y ∈ X, and assume without loss of generality
1
2
−k
that x = y. Now let d(x, y) = 2
−k , say, so that max{ι(l(x)), ι(l(y))} =
.
max{ι(l(f (x))), ι(l(f (y)))} = max{ι(l(x)), ι(l(y))}
Then d(f (x), f (y)) =
2
1
2 d(x, y), as required.
=
•
It should be noted that Theorem 4.2.5 is not a true converse of the Banach
theorem in that we do not start out with a metrizable space and attempt to
obtain a metric for it relative to which f is a contraction. Thus, Theorem 4.2.5
is quite different from those discussed, for example, in Section 3.6 of the text
[Istr˘ at ¸escu, 1981], in which a number of converses of the Banach theorem are
considered. Even the result of Bessaga discussed there, which applies to an
abstract set, is very different from ours in that we do not require all iterations
of f to have a unique fixed point, but we do require topological convergence of
the iterates of any point. Indeed, we can only make the following observations
on the relationship between the original topology and the one created by the
metric constructed in the proof of Theorem 4.2.5.
4.2.6 Proposition With the notation of the proof of Theorem 4.2.5, the
following hold.
(a) Any x = a is an isolated point with respect to d, that is, {x} is open and
closed in the topology generated by d.
(b) If (x n ) is a sequence in X which converges in d to some x = a, then the
sequence (x n ) is eventually constant.