�
122
Mathematical Aspects of Logic Programming Semantics
balls in X, where Λ ⊆ Γ. Then [(x β , β)] is an ascending chain in BX and has
least upper bound (x, γ), and hence B γ (x) ⊆
B β (x β ).
•
β∈Λ
4.8.16 Proposition The function ι : X → BX, where ι(x) = [(x, 0)] for each
x ∈ X, is injective, and ι(X) is the set of all maximal elements of BX.
Proof: Injectivity of ι follows from (U2). The observation that the maximal
elements of BX are exactly the elements of the form [(x, 0)] completes the
proof.
•
Now suppose that f is a strictly contracting mapping on a generalized ultrametric space (X, �, Γ) with ordinal distances. We use f to induce a mapping
Bf : BX → BX defined by
A
b
f (x), 2
−(α+1)
if 2
−α = 0,
Bf (x, 2
−α ) =
(f (x), 0)
if 2
−α = 0.
4.8.17 Proposition If f is strictly contracting, then Bf is monotonic.
Proof: Let (x, 2
−α ) [ (y, 2
−β ), so that �(x, y) ≤ 2
−α and α ≤ β. If 2
−α = 0,
there is nothing to show, so assume 2
−α = 0. It then remains to show that
�(f (x), f (y)) ≤ 2
−(α+1) , and this holds since f is strictly contracting and
because the following Statements (i) and (ii) hold, as is easily verified, namely,
(i) α + 1 ≤ β + 1 if 2
−β = 0, and (ii) α + 1 ≤ β if 2
−β = 0 and α = β.
•
Alternative Proof of Theorem 4.3.6 Let (X, �, Γ) be a spherically complete generalized ultrametric space with ordinal distances, and let f : X → X
be strictly contracting. Then X is a chain-complete partially ordered set,
B
and Bf is a monotonic mapping on BX. For B 0 ∈ BX, we denote by ↑ B 0 the
upper cone of B 0 , that is, the set of all B ∈ BX with B 0 [ B, as defined in
Section 3.2.
Let x ∈ X be arbitrarily chosen, assume without loss of generality that
x = f (x), and also let α be an ordinal such that �(x, f (x)) = 2
−α . Then
A
b
(x, 2
−α ) [ f (x), 2
−(α+1) , and by monotonicity of Bf we obtain that Bf
maps ↑ [(x, 2
−α )] into itself. Since ↑ [(x, 2
−α )] is a chain-complete partial order
with bottom element [(x, 2
−α )], we obtain by the Knaster-Tarski theorem,
Theorem 1.1.10, that Bf has a least fixed point in ↑ [(x, 2
−α )], which we will
denote by B 0 .
It is clear by definition of Bf that B 0 must be maximal in BX and, hence,
is of the form [(x 0 , 0)]. From Bf [(x 0 , 0)] = [(x 0 , 0)], we obtain f (x 0 ) = x 0 , so
that x 0 is a fixed point of f .
Now assume that y = x 0 is another fixed point of f . Then �(x 0 , y) =
�(f (x 0 ), f (y)) < �(x 0 , y) since f is strictly contracting. This contradiction
establishes that f has no fixed point other than x 0 .
•
122
Mathematical Aspects of Logic Programming Semantics
balls in X, where Λ ⊆ Γ. Then [(x β , β)] is an ascending chain in BX and has
least upper bound (x, γ), and hence B γ (x) ⊆
B β (x β ).
•
β∈Λ
4.8.16 Proposition The function ι : X → BX, where ι(x) = [(x, 0)] for each
x ∈ X, is injective, and ι(X) is the set of all maximal elements of BX.
Proof: Injectivity of ι follows from (U2). The observation that the maximal
elements of BX are exactly the elements of the form [(x, 0)] completes the
proof.
•
Now suppose that f is a strictly contracting mapping on a generalized ultrametric space (X, �, Γ) with ordinal distances. We use f to induce a mapping
Bf : BX → BX defined by
A
b
f (x), 2
−(α+1)
if 2
−α = 0,
Bf (x, 2
−α ) =
(f (x), 0)
if 2
−α = 0.
4.8.17 Proposition If f is strictly contracting, then Bf is monotonic.
Proof: Let (x, 2
−α ) [ (y, 2
−β ), so that �(x, y) ≤ 2
−α and α ≤ β. If 2
−α = 0,
there is nothing to show, so assume 2
−α = 0. It then remains to show that
�(f (x), f (y)) ≤ 2
−(α+1) , and this holds since f is strictly contracting and
because the following Statements (i) and (ii) hold, as is easily verified, namely,
(i) α + 1 ≤ β + 1 if 2
−β = 0, and (ii) α + 1 ≤ β if 2
−β = 0 and α = β.
•
Alternative Proof of Theorem 4.3.6 Let (X, �, Γ) be a spherically complete generalized ultrametric space with ordinal distances, and let f : X → X
be strictly contracting. Then X is a chain-complete partially ordered set,
B
and Bf is a monotonic mapping on BX. For B 0 ∈ BX, we denote by ↑ B 0 the
upper cone of B 0 , that is, the set of all B ∈ BX with B 0 [ B, as defined in
Section 3.2.
Let x ∈ X be arbitrarily chosen, assume without loss of generality that
x = f (x), and also let α be an ordinal such that �(x, f (x)) = 2
−α . Then
A
b
(x, 2
−α ) [ f (x), 2
−(α+1) , and by monotonicity of Bf we obtain that Bf
maps ↑ [(x, 2
−α )] into itself. Since ↑ [(x, 2
−α )] is a chain-complete partial order
with bottom element [(x, 2
−α )], we obtain by the Knaster-Tarski theorem,
Theorem 1.1.10, that Bf has a least fixed point in ↑ [(x, 2
−α )], which we will
denote by B 0 .
It is clear by definition of Bf that B 0 must be maximal in BX and, hence,
is of the form [(x 0 , 0)]. From Bf [(x 0 , 0)] = [(x 0 , 0)], we obtain f (x 0 ) = x 0 , so
that x 0 is a fixed point of f .
Now assume that y = x 0 is another fixed point of f . Then �(x 0 , y) =
�(f (x 0 ), f (y)) < �(x 0 , y) since f is strictly contracting. This contradiction
establishes that f has no fixed point other than x 0 .
•