242
Mathematical Aspects of Logic Programming Semantics
by the monotonicity of f , we have that b [ f (a j ) [ f (s i ) whenever i 0 ≤ i.
Consequently, we have that f (s i ) → f (s) in the Scott topology on E, and so
f is continuous in the Scott topologies, as required.
•
Finally, we consider briefly the separation and compactness properties of
the Scott topology.
A.6.5 Proposition When endowed with the Scott topology, any domain
(D, [) is a compact T 0 topological space, but is not T 1 in general.
Proof: Suppose that {U i | i ∈ I} is an open cover of D. Then we have ⊥ ∈ U k ,
where U k is some element of the given cover and ⊥ denotes the bottom element
of D. But ⊥ [ x for each x ∈ D and U k is upwards closed, being Scott open.
Therefore, D ⊆ U k , and so {U k } is an open subcover of {U i | i ∈ I}, and
hence D is compact.
We show next that D is T 0 . Suppose that x, y ∈ D and x = y. First,
suppose that x and y are comparable, that is, either x [ y or y [ x; suppose
for the sake of argument that x [ y and, hence, that x c y since x = y.
We claim that there is a compact element a [ y such that either x c a [ y
or x and a are incomparable. If not, then for all compact elements a [ y,
we have that x and a are comparable and indeed a [ x. It follows now that
the supremum of such a is less than or equal to x, which is a contradiction
since in fact this supremum is y. But then, given the claim, ↑ a is a Scott
neighbourhood of y which does not contain x. Notice that if a is any compact
element and a [ x, then a [ y. So, any Scott neighbourhood of x contains y,
and we see that the condition in the definition of T 0 is not symmetric in this
case.
Now suppose that x and y are incomparable. We claim this time that
there is a compact element a ∈ approx(x) such that a and y are incomparable.
Suppose that this is not the case, that is, suppose that for each a ∈ approx(x),
a and y are comparable. Certainly, it cannot be the case that y [ a; otherwise,
we immediately have y [ x. So it must be the case that a [ y for each a ∈
approx(x). But then we have {a | a ∈ approx(x)} [ y, that is, x [ y, which
is again a contradiction. Now, given this claim, ↑ a is a Scott neighbourhood
of x not containing y. Notice that, by symmetry, in this case we also have
a Scott neighbourhood of y not containing x; thus, the T 1 property actually
applies to some pairs in D (the incomparable pairs), but not to all pairs. In
any case, we now see that D is T 0 .
Finally, take the two element domain D = {⊥, a}, where ⊥ c a. The Scott
topology on D contains ∅, ↑ ⊥ = D and ↑ a = {a} as its open sets (the set
{⊥} is not Scott open). This space D is not T 1 since any neighbourhood of ⊥
contains a.
•
Mathematical Aspects of Logic Programming Semantics
by the monotonicity of f , we have that b [ f (a j ) [ f (s i ) whenever i 0 ≤ i.
Consequently, we have that f (s i ) → f (s) in the Scott topology on E, and so
f is continuous in the Scott topologies, as required.
•
Finally, we consider briefly the separation and compactness properties of
the Scott topology.
A.6.5 Proposition When endowed with the Scott topology, any domain
(D, [) is a compact T 0 topological space, but is not T 1 in general.
Proof: Suppose that {U i | i ∈ I} is an open cover of D. Then we have ⊥ ∈ U k ,
where U k is some element of the given cover and ⊥ denotes the bottom element
of D. But ⊥ [ x for each x ∈ D and U k is upwards closed, being Scott open.
Therefore, D ⊆ U k , and so {U k } is an open subcover of {U i | i ∈ I}, and
hence D is compact.
We show next that D is T 0 . Suppose that x, y ∈ D and x = y. First,
suppose that x and y are comparable, that is, either x [ y or y [ x; suppose
for the sake of argument that x [ y and, hence, that x c y since x = y.
We claim that there is a compact element a [ y such that either x c a [ y
or x and a are incomparable. If not, then for all compact elements a [ y,
we have that x and a are comparable and indeed a [ x. It follows now that
the supremum of such a is less than or equal to x, which is a contradiction
since in fact this supremum is y. But then, given the claim, ↑ a is a Scott
neighbourhood of y which does not contain x. Notice that if a is any compact
element and a [ x, then a [ y. So, any Scott neighbourhood of x contains y,
and we see that the condition in the definition of T 0 is not symmetric in this
case.
Now suppose that x and y are incomparable. We claim this time that
there is a compact element a ∈ approx(x) such that a and y are incomparable.
Suppose that this is not the case, that is, suppose that for each a ∈ approx(x),
a and y are comparable. Certainly, it cannot be the case that y [ a; otherwise,
we immediately have y [ x. So it must be the case that a [ y for each a ∈
approx(x). But then we have {a | a ∈ approx(x)} [ y, that is, x [ y, which
is again a contradiction. Now, given this claim, ↑ a is a Scott neighbourhood
of x not containing y. Notice that, by symmetry, in this case we also have
a Scott neighbourhood of y not containing x; thus, the T 1 property actually
applies to some pairs in D (the incomparable pairs), but not to all pairs. In
any case, we now see that D is T 0 .
Finally, take the two element domain D = {⊥, a}, where ⊥ c a. The Scott
topology on D contains ∅, ↑ ⊥ = D and ↑ a = {a} as its open sets (the set
{⊥} is not Scott open). This space D is not T 1 since any neighbourhood of ⊥
contains a.
•