143
Supported Model Semantics
Proof: It suffices to prove (a). We will do this by applying Theorem 4.8.14. For
the given level mapping l, define the rank function r l by setting r l (∅) = 0 and
by setting r l (I) = max{l(A) | A ∈ I} for every non-empty I ∈ (I P ) c , where
we identify each element of (I P ) c with a finite subset of B P , as usual. The
generalized ultrametric d r l induced by r l , as in Definition 4.8.12, is spherically
complete by Theorem 4.8.14. The mappings d l and d r l coincide since, for each
I ∈ I P , we have I = sup{{A} | A ∈ I}, with the supremum being taken with
respect to subset inclusion.
•
Under certain conditions similar to those discussed in Section 4.6, we can
recover the Cantor topology from d l .
5.1.5 Proposition Let P be a normal logic program, and let l : B P → ω be
a level mapping such that l
−1 (n) is finite for each n ∈ N. Then d l induces the
Cantor topology Q on I P .
Proof: It is easily shown by using Proposition 3.3.5 that sequences converge
in Q if and only if they converge with respect to d l , and this observation
suffices.
•
We show finally that the immediate consequence operator satisfies the required contractivity conditions for applying the Prieß-Crampe and Ribenboim
theorem or the Banach contraction mapping theorem, as appropriate.
5.1.6 Theorem Suppose that P is a normal logic program, and that l is a
level mapping. Then the following statements hold.
(a) If P is locally hierarchical with respect to l, then T P is a strictly contracting.
(b) If P is acyclic with respect to l, then T P is a contraction.
Furthermore, in both cases, T P has a unique fixed point, and P has a unique
supported model.
Proof: (a) Suppose I 1 , I 2 ∈ I P , and that d l (I 1 , I 2 ) = 2
−α for some ordinal α.
Suppose α = 0. Let A ∈ T P (I 1 ) with l(A) = 0. Since P is locally hierarchical, A must be the head of a unit clause in ground(P ). From this it follows
that A ∈ T P (I 2 ) also. By the same argument, if A ∈ T P (I 2 ) with l(A) = 0,
then A ∈ T P (I 1 ). Therefore, T P (I 1 ) and T P (I 2 ) agree on all atoms of level less
than 1, and hence we have
d l (T P (I 1 ), T P (I 2 )) ≤ 2
−1 < 2
−0 = d l (I 1 , I 2 ),
as required.
Now suppose α > 0, so that I 1 and I 2 differ on some element of B P
with level α, but agree on all ground atoms of lower level. Let A ∈ T P (I 1 )
Supported Model Semantics
Proof: It suffices to prove (a). We will do this by applying Theorem 4.8.14. For
the given level mapping l, define the rank function r l by setting r l (∅) = 0 and
by setting r l (I) = max{l(A) | A ∈ I} for every non-empty I ∈ (I P ) c , where
we identify each element of (I P ) c with a finite subset of B P , as usual. The
generalized ultrametric d r l induced by r l , as in Definition 4.8.12, is spherically
complete by Theorem 4.8.14. The mappings d l and d r l coincide since, for each
I ∈ I P , we have I = sup{{A} | A ∈ I}, with the supremum being taken with
respect to subset inclusion.
•
Under certain conditions similar to those discussed in Section 4.6, we can
recover the Cantor topology from d l .
5.1.5 Proposition Let P be a normal logic program, and let l : B P → ω be
a level mapping such that l
−1 (n) is finite for each n ∈ N. Then d l induces the
Cantor topology Q on I P .
Proof: It is easily shown by using Proposition 3.3.5 that sequences converge
in Q if and only if they converge with respect to d l , and this observation
suffices.
•
We show finally that the immediate consequence operator satisfies the required contractivity conditions for applying the Prieß-Crampe and Ribenboim
theorem or the Banach contraction mapping theorem, as appropriate.
5.1.6 Theorem Suppose that P is a normal logic program, and that l is a
level mapping. Then the following statements hold.
(a) If P is locally hierarchical with respect to l, then T P is a strictly contracting.
(b) If P is acyclic with respect to l, then T P is a contraction.
Furthermore, in both cases, T P has a unique fixed point, and P has a unique
supported model.
Proof: (a) Suppose I 1 , I 2 ∈ I P , and that d l (I 1 , I 2 ) = 2
−α for some ordinal α.
Suppose α = 0. Let A ∈ T P (I 1 ) with l(A) = 0. Since P is locally hierarchical, A must be the head of a unit clause in ground(P ). From this it follows
that A ∈ T P (I 2 ) also. By the same argument, if A ∈ T P (I 2 ) with l(A) = 0,
then A ∈ T P (I 1 ). Therefore, T P (I 1 ) and T P (I 2 ) agree on all atoms of level less
than 1, and hence we have
d l (T P (I 1 ), T P (I 2 )) ≤ 2
−1 < 2
−0 = d l (I 1 , I 2 ),
as required.
Now suppose α > 0, so that I 1 and I 2 differ on some element of B P
with level α, but agree on all ground atoms of lower level. Let A ∈ T P (I 1 )