�
104
Mathematical Aspects of Logic Programming Semantics
following calculations for all n ∈ N:
�(f (x), x) ≤ �(f (x), f
n (x)) + �(f
n (x), x)
A
b
< � x, f
n−1 (x) + �(f
n (x), x)
A
b
A
b
≤ � x, f
n−1 (y) + � f
n−1 (y), f
n−1 (x) + �(f
n (x), f
n (y))
+ �(f
n (y), x)
A
b
≤ � x, f
n−1 (y) + λ
n−1 �(y, x) + λ
n �(x, y) + �(f
n (y), x).
Since all four terms in the last line converge to 0 as n → ∞, we obtain
�(f (x), x) = 0, and therefore f (x) = x by (M3) and (M2).
•
4.5 Dislocated Generalized Ultrametrics
The following theorem gives a partial unification of Matthews’ theorem, Theorem 4.4.6, and the Prieß-Crampe and Ribenboim theorem, Theorem 4.3.6.
17
4.5.1 Theorem Let (X, � , Γ) be a spherically complete d-gum, and let f :
X → X be non-expanding and strictly contracting on orbits. Then f has a
fixed point. If f is strictly contracting on X, then the fixed point is unique.
Proof: Assume that f has no fixed point. Then for all x ∈ X, we have
�(x, f (x)) = 0. We now define the set B by B = {B 1(x,f (x)) (x) | x ∈ X}, and
note that each ball in this set is non-empty. We also note that B 1(x,f (x)) (x) =
B 1(x,f (x)) (f (x)) by Lemma 4.3.5. Now let C be a maximal chain in B. Since
X is spherically complete, there exists z ∈ C. We show that B 1(z,f (z)) (z) ⊆
B 1(x,f (x)) for all x ∈ X and, hence, by maximality, that B 1(z,f (z)) (z) is the
smallest ball in the chain. Let B 1(x,f (x)) (x) ∈ C. Since z ∈ B 1(x,f (x)) (x), and
noting our earlier observation that B 1(x,f (x)) (x) = B 1(x,f (x)) (f (x)) for all x,
we get �(z, x) ≤ �(x, f (x)) and �(z, f (x)) ≤ �(x, f (x)). By non-expansiveness
of f , we get �(f (z), f (x)) ≤ �(z, x) ≤ �(x, f (x)). It follows by (U4) that
�(z, f (z)) ≤ �(x, f (x)) and therefore by Lemma 4.3.5 that B 1(z,f (z)) (z) ⊆
B 1(x,f (x)) (x) for all x ∈ X, since x was chosen arbitrarily. Now, since f is
strictly contracting on orbits, �(f (z), f
2 (z)) < �(z, f (z)), and therefore z ∈
B 1(f (z),f 2 (z)) (f (z)) ⊂ B 1(z,f (z)) (f (z)). By Lemma 4.3.5, this is equivalent to
B 1(f (z),f 2 (z)) (f (z)) ⊂ B 1(z,f (z)) (z), which is a contradiction to the maximality
of C. So f has a fixed point.
17 The proof of Theorem 4.4.6 given here is, in fact, identical to that of Theorem 4.3.6
from [Prieß-Crampe and Ribenboim, 1993].
104
Mathematical Aspects of Logic Programming Semantics
following calculations for all n ∈ N:
�(f (x), x) ≤ �(f (x), f
n (x)) + �(f
n (x), x)
A
b
< � x, f
n−1 (x) + �(f
n (x), x)
A
b
A
b
≤ � x, f
n−1 (y) + � f
n−1 (y), f
n−1 (x) + �(f
n (x), f
n (y))
+ �(f
n (y), x)
A
b
≤ � x, f
n−1 (y) + λ
n−1 �(y, x) + λ
n �(x, y) + �(f
n (y), x).
Since all four terms in the last line converge to 0 as n → ∞, we obtain
�(f (x), x) = 0, and therefore f (x) = x by (M3) and (M2).
•
4.5 Dislocated Generalized Ultrametrics
The following theorem gives a partial unification of Matthews’ theorem, Theorem 4.4.6, and the Prieß-Crampe and Ribenboim theorem, Theorem 4.3.6.
17
4.5.1 Theorem Let (X, � , Γ) be a spherically complete d-gum, and let f :
X → X be non-expanding and strictly contracting on orbits. Then f has a
fixed point. If f is strictly contracting on X, then the fixed point is unique.
Proof: Assume that f has no fixed point. Then for all x ∈ X, we have
�(x, f (x)) = 0. We now define the set B by B = {B 1(x,f (x)) (x) | x ∈ X}, and
note that each ball in this set is non-empty. We also note that B 1(x,f (x)) (x) =
B 1(x,f (x)) (f (x)) by Lemma 4.3.5. Now let C be a maximal chain in B. Since
X is spherically complete, there exists z ∈ C. We show that B 1(z,f (z)) (z) ⊆
B 1(x,f (x)) for all x ∈ X and, hence, by maximality, that B 1(z,f (z)) (z) is the
smallest ball in the chain. Let B 1(x,f (x)) (x) ∈ C. Since z ∈ B 1(x,f (x)) (x), and
noting our earlier observation that B 1(x,f (x)) (x) = B 1(x,f (x)) (f (x)) for all x,
we get �(z, x) ≤ �(x, f (x)) and �(z, f (x)) ≤ �(x, f (x)). By non-expansiveness
of f , we get �(f (z), f (x)) ≤ �(z, x) ≤ �(x, f (x)). It follows by (U4) that
�(z, f (z)) ≤ �(x, f (x)) and therefore by Lemma 4.3.5 that B 1(z,f (z)) (z) ⊆
B 1(x,f (x)) (x) for all x ∈ X, since x was chosen arbitrarily. Now, since f is
strictly contracting on orbits, �(f (z), f
2 (z)) < �(z, f (z)), and therefore z ∈
B 1(f (z),f 2 (z)) (f (z)) ⊂ B 1(z,f (z)) (f (z)). By Lemma 4.3.5, this is equivalent to
B 1(f (z),f 2 (z)) (f (z)) ⊂ B 1(z,f (z)) (z), which is a contradiction to the maximality
of C. So f has a fixed point.
17 The proof of Theorem 4.4.6 given here is, in fact, identical to that of Theorem 4.3.6
from [Prieß-Crampe and Ribenboim, 1993].