70
Mathematical Aspects of Logic Programming Semantics
Now suppose that a 1 and a 2 are compact elements and that z ∈ ↑ a 1 ∩ ↑ a 2 .
Then a 1 , a 2 ∈ approx(z), and by directedness there is a 3 ∈ approx(z) such
that a 1 [ a 3 and a 2 [ a 3 . Hence, we have a 3 ∈ ↑ a 1 ∩ ↑ a 2 . But ↑ a 1 ∩ ↑ a 2 is
clearly upwards closed, and so we obtain z ∈ ↑ a 3 ⊆ ↑ a 1 ∩ ↑ a 2 and a 3 ∈ D c , as
required.
Finally, we show that the collection {↑ a | a ∈ D c } is a base for the Scott
topology on D. Let O be any Scott-open set, and let x ∈ O. Then approx(x)
is directed, and we have that approx(x) = x ∈ O. Therefore, there is some
a ∈ approx(x) such that a ∈ O. But then a ∈ D c and a [ x. Therefore,
x ∈ ↑ a ⊆ O, where a is a compact element, as required.
•
We refer to the elements of the Scott topology as Scott-open sets. Likewise,
we refer to neighbourhoods in the Scott topology as Scott neighbourhoods,
and so on.
We next give a simple example of the Scott topology in the context of I P,2 .
3.2.3 Example Consider the definite program P as follows.
p(a) ←
p(s(X)) ← p(X)
This program is intended to compute the natural numbers, where a is the
natural number 0, and s is the successor function on the natural numbers.
In accordance with Theorem 1.3.4, the set I P = I P,2 of all two-valued
interpretations for P is a domain, and, furthermore, its compact elements are
the finite subsets I of B P , where as usual we are identifying a two-valued
interpretation with the set of ground atoms which are true in I. Therefore, a
'
typical basic open set in the Scott topology on I P is the set ↑ I = {I ⊆ B P |
I ⊆ I
' } of all supersets of the finite set I.
One of our main aims here is to present the Scott topology in terms of
convergence, and we proceed to do this next.
9
3.2.4 Theorem Let (D, [) denote a domain, let (s i ) be a net in D, and let
s denote an element of D. Define lim i s i ≡ s (C) to mean that
for each a ∈ approx(s), there is an index i 0 such that a [ s i whenever i 0 ≤ i.
Then the condition just given determines a convergence class C whose associated topology is the Scott topology on D. Therefore, a net s i converges to s
in the Scott topology on D if and only if it satisfies the condition just stated.
Proof: We first verify that the conditions (1), (2), (3), and (4) in the definition
of a convergence class, see Definition 3.1.2, hold with the given meaning of
lim i s i ≡ s (C).
9 For further details of this result and of several more in this chapter, see [Seda, 2002].
Mathematical Aspects of Logic Programming Semantics
Now suppose that a 1 and a 2 are compact elements and that z ∈ ↑ a 1 ∩ ↑ a 2 .
Then a 1 , a 2 ∈ approx(z), and by directedness there is a 3 ∈ approx(z) such
that a 1 [ a 3 and a 2 [ a 3 . Hence, we have a 3 ∈ ↑ a 1 ∩ ↑ a 2 . But ↑ a 1 ∩ ↑ a 2 is
clearly upwards closed, and so we obtain z ∈ ↑ a 3 ⊆ ↑ a 1 ∩ ↑ a 2 and a 3 ∈ D c , as
required.
Finally, we show that the collection {↑ a | a ∈ D c } is a base for the Scott
topology on D. Let O be any Scott-open set, and let x ∈ O. Then approx(x)
is directed, and we have that approx(x) = x ∈ O. Therefore, there is some
a ∈ approx(x) such that a ∈ O. But then a ∈ D c and a [ x. Therefore,
x ∈ ↑ a ⊆ O, where a is a compact element, as required.
•
We refer to the elements of the Scott topology as Scott-open sets. Likewise,
we refer to neighbourhoods in the Scott topology as Scott neighbourhoods,
and so on.
We next give a simple example of the Scott topology in the context of I P,2 .
3.2.3 Example Consider the definite program P as follows.
p(a) ←
p(s(X)) ← p(X)
This program is intended to compute the natural numbers, where a is the
natural number 0, and s is the successor function on the natural numbers.
In accordance with Theorem 1.3.4, the set I P = I P,2 of all two-valued
interpretations for P is a domain, and, furthermore, its compact elements are
the finite subsets I of B P , where as usual we are identifying a two-valued
interpretation with the set of ground atoms which are true in I. Therefore, a
'
typical basic open set in the Scott topology on I P is the set ↑ I = {I ⊆ B P |
I ⊆ I
' } of all supersets of the finite set I.
One of our main aims here is to present the Scott topology in terms of
convergence, and we proceed to do this next.
9
3.2.4 Theorem Let (D, [) denote a domain, let (s i ) be a net in D, and let
s denote an element of D. Define lim i s i ≡ s (C) to mean that
for each a ∈ approx(s), there is an index i 0 such that a [ s i whenever i 0 ≤ i.
Then the condition just given determines a convergence class C whose associated topology is the Scott topology on D. Therefore, a net s i converges to s
in the Scott topology on D if and only if it satisfies the condition just stated.
Proof: We first verify that the conditions (1), (2), (3), and (4) in the definition
of a convergence class, see Definition 3.1.2, hold with the given meaning of
lim i s i ≡ s (C).
9 For further details of this result and of several more in this chapter, see [Seda, 2002].