120
Mathematical Aspects of Logic Programming Semantics
(c) B β ∈ B
β (y) and B
α
α ∈ B (x).
(d) Whenever B
α (x) ⊆ B
β (y), we have B β [ B α .
Proof: (a) Since �
β
r (z, y) ≤ 2
− , the first statement follows immediately from
the definition of � r .
(b) Since the set {c ∈ approx(z) | r(c) < β} is bounded by z, for any z and
β, the second statement follows immediately from the consistent completeness
of D.
(c) By definition, we obtain B β [ y. Since B β and y agree on all c ∈ D c
with r(c) < β, the first statement in (c) holds, and the second similarly.
(d) First note that x ∈ B
β (y), so that B
β (y) = B
β (x), and the hypothesis
can be written as B
α (x) ⊆ B
β (x). We consider two cases.
Case
i. If β ≤ α, then using (a) and noting again that x ∈ B
β (y), we get
B β = {c ∈ approx(y) | r(c) < β} = {c ∈ approx(x) | r(c) < β} [ {c ∈
approx(x) | r(c) < α} = B α , as required.
Case ii. If α < β, then we cannot ha
ve B
α (x)
⊂ B
β (x), and we therefore
obtain B
α (x) = B
β (x) and consequently B
α (B ) = B
β (B ) = B
β
β
β
(B α ) using
(c). With the argument of Case i and noting that y ∈ B
α (x), it follows that
B α [ B β . We want to show that B α = B β . Assume, in fact, that B α c B β .
Since any poin
t of a ball is its centre, we can take z = B β in (b), twice, to
obtain B β = {c ∈ approx(B β ) | r(c) < β} and B α = {c ∈ approx(B β ) |
r(c) < α}. Th
us, the supposition B α c B β means that {c ∈ approx(B β )
c
|
r(c) < α}
{c ∈ approx(B β ) | r(c) < β
}. Since {c ∈ approx(B β ) | r(c) <
α} ⊆ {c ∈ approx(B β ) r(c) < β , there must be some d
c
|
}
∈ { ∈ approx(B β ) |
r(c) < β} with d [ {c ∈ approx(B β ) | r(c) < α} = B α . Thus, there is an
element d ∈ D c with r(d) < β satisfying d [ B α and d [ B β . This contradicts
the fact that � r (B α ,
B β ) ≤ 2
−β . Hence, B α c B β . Since B α [ B β , it follows
that B α = B β and therefore that B β [ B α , as required.
•
4.8.14 Theorem The ultrametric space (D, � r ) is spherically complete.
Proof: By the previous lemma, every chain (B
α (x
α )) of balls in D gives rise
to a chain (B α ) in D in reverse order. Let B = B α . Now let B
α (x α ) be
an arbitrary ball in the chain. It suffices to show that B ∈ B
α (x α ). Since
B α ∈ B
α (x α ), we have � r (B α , x α ) ≤ 2
−α . But � r is a generalized ultrametric,
and so it suffices to show that � r (B, B α ) ≤ 2
−α . For every compact element
c [ B α , we have c [ B by construction of B. Now let c [ B with c ∈ D c and
r(c) < α. We have to show that c [ B α . Since c is compact and c [ B, there
exists B β in the chain with c [ B β . If B
α (x α ) ⊆ B
β (x β ), then B β [ B α by
Lemma 4.8.13, and therefore c [ B α . If B
β (x β ) ⊂ B
α (x α ), then α < β, and,
since c [ B β , we see that c is an element of the set {c ∈ approx(x β ) | r(c) <
α} = {c ∈ approx(x α ) | r(c) < α}. Since B α is the supremum of the latter
set, we have c [ B α , as required.
•
We will apply this result in Section 5.1.1.
Mathematical Aspects of Logic Programming Semantics
(c) B β ∈ B
β (y) and B
α
α ∈ B (x).
(d) Whenever B
α (x) ⊆ B
β (y), we have B β [ B α .
Proof: (a) Since �
β
r (z, y) ≤ 2
− , the first statement follows immediately from
the definition of � r .
(b) Since the set {c ∈ approx(z) | r(c) < β} is bounded by z, for any z and
β, the second statement follows immediately from the consistent completeness
of D.
(c) By definition, we obtain B β [ y. Since B β and y agree on all c ∈ D c
with r(c) < β, the first statement in (c) holds, and the second similarly.
(d) First note that x ∈ B
β (y), so that B
β (y) = B
β (x), and the hypothesis
can be written as B
α (x) ⊆ B
β (x). We consider two cases.
Case
i. If β ≤ α, then using (a) and noting again that x ∈ B
β (y), we get
B β = {c ∈ approx(y) | r(c) < β} = {c ∈ approx(x) | r(c) < β} [ {c ∈
approx(x) | r(c) < α} = B α , as required.
Case ii. If α < β, then we cannot ha
ve B
α (x)
⊂ B
β (x), and we therefore
obtain B
α (x) = B
β (x) and consequently B
α (B ) = B
β (B ) = B
β
β
β
(B α ) using
(c). With the argument of Case i and noting that y ∈ B
α (x), it follows that
B α [ B β . We want to show that B α = B β . Assume, in fact, that B α c B β .
Since any poin
t of a ball is its centre, we can take z = B β in (b), twice, to
obtain B β = {c ∈ approx(B β ) | r(c) < β} and B α = {c ∈ approx(B β ) |
r(c) < α}. Th
us, the supposition B α c B β means that {c ∈ approx(B β )
c
|
r(c) < α}
{c ∈ approx(B β ) | r(c) < β
}. Since {c ∈ approx(B β ) | r(c) <
α} ⊆ {c ∈ approx(B β ) r(c) < β , there must be some d
c
|
}
∈ { ∈ approx(B β ) |
r(c) < β} with d [ {c ∈ approx(B β ) | r(c) < α} = B α . Thus, there is an
element d ∈ D c with r(d) < β satisfying d [ B α and d [ B β . This contradicts
the fact that � r (B α ,
B β ) ≤ 2
−β . Hence, B α c B β . Since B α [ B β , it follows
that B α = B β and therefore that B β [ B α , as required.
•
4.8.14 Theorem The ultrametric space (D, � r ) is spherically complete.
Proof: By the previous lemma, every chain (B
α (x
α )) of balls in D gives rise
to a chain (B α ) in D in reverse order. Let B = B α . Now let B
α (x α ) be
an arbitrary ball in the chain. It suffices to show that B ∈ B
α (x α ). Since
B α ∈ B
α (x α ), we have � r (B α , x α ) ≤ 2
−α . But � r is a generalized ultrametric,
and so it suffices to show that � r (B, B α ) ≤ 2
−α . For every compact element
c [ B α , we have c [ B by construction of B. Now let c [ B with c ∈ D c and
r(c) < α. We have to show that c [ B α . Since c is compact and c [ B, there
exists B β in the chain with c [ B β . If B
α (x α ) ⊆ B
β (x β ), then B β [ B α by
Lemma 4.8.13, and therefore c [ B α . If B
β (x β ) ⊂ B
α (x α ), then α < β, and,
since c [ B β , we see that c is an element of the set {c ∈ approx(x β ) | r(c) <
α} = {c ∈ approx(x α ) | r(c) < α}. Since B α is the supremum of the latter
set, we have c [ B α , as required.
•
We will apply this result in Section 5.1.1.