94
Mathematical Aspects of Logic Programming Semantics
Notice that the condition x = y is not actually needed in the statement of
the previous result, but is included for the sake of consistency with what we
want to say next, namely, that it is well-known
7 that the requirement λ < 1
cannot be relaxed in general. This can be seen by considering the function
f : R → R defined by
x +
1
x
,
f (x) =
x
for ≥ 1
2
otherwise.
This function satisfies the condition d(f (x), f (y)) < d(x, y) for all x, y ∈ R
with x = y, where d is the usual metric on R, but has no fixed point since
f (x) > x for all x ∈ R. If X is compact, however, the requirement on λ can
be relaxed.
4.2.4 Theorem Let (X, d) be a compact metric space, and let f : X → X
be a function which is strictly contracting, that is, f satisfies d(f (x), f (y)) <
d(x, y) for all x, y ∈ X with x = y. Then f has a unique fixed point.
Proof: The function d(x) = d(x, f (x)) is continuous since f is continuous.
It therefore achieves a minimum m on X. Assume d(x 0 ) = m > 0. Then
d(f (x 0 )) = d(f (x 0 ), f (f (x 0 ))) < d(x 0 , f (x 0 )) = d(x 0 ) = m, which is a contradiction. Hence, m = 0, and so f has a fixed point.
Assume x and y are fixed points of f and x = y. Then d(x, y) =
d(f (x), f (y)) < d(x, y), which is a contradiction. Therefore, the fixed point
of f is unique.
•
There is quite a lot of interest in establishing results which can be viewed
in one way or another as converses of the Banach theorem.
8 The following
is such a result. It was originally inspired by certain applications to logic
programming, to be given in Chapters 5 and 6, of the results presented in this
chapter.
4.2.5 Theorem Let (X, τ ) be a T 1 topological space, and let f : X → X
be a function which has a unique fixed point a and is such that, for each
x ∈ X, the sequence (f
n (x)) converges to a in τ . Then there exists a function
d : X × X → R such that (X, d) is a complete ultrametric space and such that
for all x, y ∈ X we have d(f (x), f (y)) ≤
1 d(x, y).
2
Proof: The proof is divided into several steps, numbered consecutively.
(1) Given x ∈ X, we define the set T (x) ⊆ X to be the smallest subset of
X which is closed under the following rules.
(1.1) x ∈ T (x).
7 The results of Section 4.2 can be found in many places including [Kirk and Sims, 2001,
Dugundji and Granas, 1982], for example.
8 A discussion of this question can be found in [Kirk and Sims, 2001] and its references
and in [Istr˘ at ¸escu, 1981].
Mathematical Aspects of Logic Programming Semantics
Notice that the condition x = y is not actually needed in the statement of
the previous result, but is included for the sake of consistency with what we
want to say next, namely, that it is well-known
7 that the requirement λ < 1
cannot be relaxed in general. This can be seen by considering the function
f : R → R defined by
x +
1
x
,
f (x) =
x
for ≥ 1
2
otherwise.
This function satisfies the condition d(f (x), f (y)) < d(x, y) for all x, y ∈ R
with x = y, where d is the usual metric on R, but has no fixed point since
f (x) > x for all x ∈ R. If X is compact, however, the requirement on λ can
be relaxed.
4.2.4 Theorem Let (X, d) be a compact metric space, and let f : X → X
be a function which is strictly contracting, that is, f satisfies d(f (x), f (y)) <
d(x, y) for all x, y ∈ X with x = y. Then f has a unique fixed point.
Proof: The function d(x) = d(x, f (x)) is continuous since f is continuous.
It therefore achieves a minimum m on X. Assume d(x 0 ) = m > 0. Then
d(f (x 0 )) = d(f (x 0 ), f (f (x 0 ))) < d(x 0 , f (x 0 )) = d(x 0 ) = m, which is a contradiction. Hence, m = 0, and so f has a fixed point.
Assume x and y are fixed points of f and x = y. Then d(x, y) =
d(f (x), f (y)) < d(x, y), which is a contradiction. Therefore, the fixed point
of f is unique.
•
There is quite a lot of interest in establishing results which can be viewed
in one way or another as converses of the Banach theorem.
8 The following
is such a result. It was originally inspired by certain applications to logic
programming, to be given in Chapters 5 and 6, of the results presented in this
chapter.
4.2.5 Theorem Let (X, τ ) be a T 1 topological space, and let f : X → X
be a function which has a unique fixed point a and is such that, for each
x ∈ X, the sequence (f
n (x)) converges to a in τ . Then there exists a function
d : X × X → R such that (X, d) is a complete ultrametric space and such that
for all x, y ∈ X we have d(f (x), f (y)) ≤
1 d(x, y).
2
Proof: The proof is divided into several steps, numbered consecutively.
(1) Given x ∈ X, we define the set T (x) ⊆ X to be the smallest subset of
X which is closed under the following rules.
(1.1) x ∈ T (x).
7 The results of Section 4.2 can be found in many places including [Kirk and Sims, 2001,
Dugundji and Granas, 1982], for example.
8 A discussion of this question can be found in [Kirk and Sims, 2001] and its references
and in [Istr˘ at ¸escu, 1981].