�
74
Mathematical Aspects of Logic Programming Semantics
each of the interpretations ∅, {p(a)}, {p(s(a))}, {p(a), p(s(a))}, but not
to {p(a), p(s(a)), p(s
2 (a))}.
Again, if I n is the interpretation defined by taking it to be the set
{p(a), p(s(a)), . . . , p(s
n (a))} if n is even and taking it to be the set
{p(a), p(s(a)), . . . , p(s
2n (a))} if n is odd, then the sequence (I n ) converges
to the interpretation {p(a), p(s(a)), p(s
2 (a)), . . .}; note that (I n ) is not
monotonic in the sense of Part (2).
Although we have taken convergence as the basic concept, it is easy to exhibit properties of the Scott topology in other familiar terms, as the following
example shows.
3.2.8 Example In the context of spaces of interpretations, Proposition 3.2.2
gives a simple description of the basic open sets in the Scott topology, and
we briefly consider this point here. In the case of T W O, for example, let
A 1 , . . . , A n ∈ X and let G(A 1 , . . . , A n ) = {I ∈ I(X, T W O) | A 1 , . . . , A n ∈
I}. By means of (f) of Theorem 1.3.2 and (c) of Proposition 3.2.2, it is
clear that the sets G(A 1 , . . . , A n ) form a base for the Scott topology on
I(X, T WO). Indeed, the sets G(A) = {I ∈ I(X, T W O) | A ∈ I} form a
subbase for the Scott topology, since G(A 1 , . . . , A n ) =
G(A i ). As
i∈{1,...,n}
another example, consider this time the knowledge ordering [ k in the case of
T HREE. Take elements A 1 , . . . , A n , B 1 , . . . , B m ∈ X, where n, m ≥ 0, and
let G(A 1 , . . . , A n ; B 1 , . . . , B m ) be the set {I ∈ I(X, T HREE) | A 1 , . . . , A n ∈
I t and B 1 , . . . , B m ∈ I f }. Then these sets form a base for the Scott topology
on I(X, T HREE). Indeed, the sets G(A; B) clearly form a subbase for this
topology, where G(A; B) = {I ∈ I(X, T HREE) | A ∈ I t and B ∈ I f }.
The other cases dealt with in Section 1.3.2 can be treated similarly.
We turn next to consider the continuity of the immediate consequence
operator in the Scott topology. By virtue of (a) of Theorem 2.2.3 and Proposition A.6.4, we have immediately that T P is Scott continuous whenever P is a
definite program. However, we will take the trouble to include a self-contained
proof of this fact next.
3.2.9 Theorem Let P be a definite program. Then T P is continuous in the
Scott topology on I P,2 .
Proof: Let I ∈ I P,2 , and let I i → I be a net converging to I in the Scott
topology; we show that T P (I i ) → T P (I) in the Scott topology. If T P (I) = ∅,
then the required conclusion is immediate since, by Theorem 3.2.4, every net
in a domain converges in the Scott topology to the bottom element. So suppose
that T P (I) = ∅, and let A belong to T P (I). Then there is a ground instance
A ← A 1 , . . . , A n of a clause in P such that I(A 1 ∧ . . . ∧ A n ) = t, where
n ≥ 0. Since I i → I, we have, by (a) of Theorem 3.2.6, that eventually
I i (A 1 ∧ . . . ∧ A n ) = t. Therefore, A ∈ T P (I i ) eventually. It now follows from
Theorem 3.2.6 that T P (I i ) → T P (I) in the Scott topology, as required.
•
74
Mathematical Aspects of Logic Programming Semantics
each of the interpretations ∅, {p(a)}, {p(s(a))}, {p(a), p(s(a))}, but not
to {p(a), p(s(a)), p(s
2 (a))}.
Again, if I n is the interpretation defined by taking it to be the set
{p(a), p(s(a)), . . . , p(s
n (a))} if n is even and taking it to be the set
{p(a), p(s(a)), . . . , p(s
2n (a))} if n is odd, then the sequence (I n ) converges
to the interpretation {p(a), p(s(a)), p(s
2 (a)), . . .}; note that (I n ) is not
monotonic in the sense of Part (2).
Although we have taken convergence as the basic concept, it is easy to exhibit properties of the Scott topology in other familiar terms, as the following
example shows.
3.2.8 Example In the context of spaces of interpretations, Proposition 3.2.2
gives a simple description of the basic open sets in the Scott topology, and
we briefly consider this point here. In the case of T W O, for example, let
A 1 , . . . , A n ∈ X and let G(A 1 , . . . , A n ) = {I ∈ I(X, T W O) | A 1 , . . . , A n ∈
I}. By means of (f) of Theorem 1.3.2 and (c) of Proposition 3.2.2, it is
clear that the sets G(A 1 , . . . , A n ) form a base for the Scott topology on
I(X, T WO). Indeed, the sets G(A) = {I ∈ I(X, T W O) | A ∈ I} form a
subbase for the Scott topology, since G(A 1 , . . . , A n ) =
G(A i ). As
i∈{1,...,n}
another example, consider this time the knowledge ordering [ k in the case of
T HREE. Take elements A 1 , . . . , A n , B 1 , . . . , B m ∈ X, where n, m ≥ 0, and
let G(A 1 , . . . , A n ; B 1 , . . . , B m ) be the set {I ∈ I(X, T HREE) | A 1 , . . . , A n ∈
I t and B 1 , . . . , B m ∈ I f }. Then these sets form a base for the Scott topology
on I(X, T HREE). Indeed, the sets G(A; B) clearly form a subbase for this
topology, where G(A; B) = {I ∈ I(X, T HREE) | A ∈ I t and B ∈ I f }.
The other cases dealt with in Section 1.3.2 can be treated similarly.
We turn next to consider the continuity of the immediate consequence
operator in the Scott topology. By virtue of (a) of Theorem 2.2.3 and Proposition A.6.4, we have immediately that T P is Scott continuous whenever P is a
definite program. However, we will take the trouble to include a self-contained
proof of this fact next.
3.2.9 Theorem Let P be a definite program. Then T P is continuous in the
Scott topology on I P,2 .
Proof: Let I ∈ I P,2 , and let I i → I be a net converging to I in the Scott
topology; we show that T P (I i ) → T P (I) in the Scott topology. If T P (I) = ∅,
then the required conclusion is immediate since, by Theorem 3.2.4, every net
in a domain converges in the Scott topology to the bottom element. So suppose
that T P (I) = ∅, and let A belong to T P (I). Then there is a ground instance
A ← A 1 , . . . , A n of a clause in P such that I(A 1 ∧ . . . ∧ A n ) = t, where
n ≥ 0. Since I i → I, we have, by (a) of Theorem 3.2.6, that eventually
I i (A 1 ∧ . . . ∧ A n ) = t. Therefore, A ∈ T P (I i ) eventually. It now follows from
Theorem 3.2.6 that T P (I i ) → T P (I) in the Scott topology, as required.
•