73
Topology and Logic Programming
Proof: We prove the first of the claims in (c), with the others being proved
similarly. Let v denote the valuation corresponding to the interpretation I,
and, for each index i, let v i denote the valuation corresponding to the interpretation I i . Suppose first that (v i ) converges to v in the Scott topology
on I(X, T ), and let x ∈ X. Suppose further that x ∈ v t , so that v(x) = t.
Define u ∈ I(X, T ) by u(x) = t, and, for y = x, set u(y) = u. Then u is a
finite element satisfying u [ k v. Therefore, by Theorem 3.2.4, there exists i 0
such that u [ k v i whenever i ≥ i 0 , and hence eventually either v i (x) = t or
v i (x) = b. Thus, eventually x ∈ v it ∪ v i b . A similar argument holds in case
x ∈ v f or x ∈ v b , and hence we obtain the stated condition.
Conversely, suppose that the given condition holds. Let u be a finite valuation such that u [ k v, and suppose further that u takes value u at all points of
X except possibly at one point x, say. Let us first suppose that u(x) = t. Then
either x ∈ v t or x ∈ v b . But then, by the given condition, either eventually
x ∈ v it ∪ v i b or eventually x ∈ v i b , and in either case, eventually u [ k v i . A
similar argument holds in case u(x) = f or u(x) = b. By a standard argument
using the directedness of the index set of the net v i , it follows that, for any
finite valuation u [ k v, we have eventually u [ k v i . Hence, (v i ) converges to
v in the Scott topology on I(X, T ), as required.
•
Thus, we obtain a uniform description of net convergence in the Scott
topology on (I(X, T ), [), where (T , ≤) is any one of the main sets of truth
values which are important in logic programming. Indeed, the convergence
conditions involved are simple, natural, and intuitive, and this is one of the
advantages of approaching this topic via convergence.
In fact, it is Part (a) of Theorem 3.2.6 which we will use most often, and
we illustrate its use next with an example.
3.2.7 Example The following statements concerning convergence in the
Scott topology hold in two-valued logic.
10
(1) Any net (I λ ) of interpretations converges to the empty interpretation ∅.
(2) If (I λ ) is a net of interpretations which is monotonic in the sense that
I λ ⊆ I γ whenever λ ≤ γ, then (I λ ) converges to
λ I λ .
(3) If a net (I λ ) of interpretations converges to an interpretation I, and J ⊆ I,
then (I λ ) converges to J. Thus, in general, a net (I λ ) of interpretations
has many limits. A specific example of this can be given as follows. Suppose that L is a first-order language containing a unary predicate symbol p, a unary function symbol s, and a constant symbol a, such as the
language underlying Example 3.2.3, say. Consider the sequence (I n ) of
interpretations defined as follows: I n is the set {p(a), p(s(a))} if n is even
and is the set {p(a), p(s(a)), p(s
2 (a))} if n is odd. Then (I n ) converges to
10 For further results in this direction, see [Seda, 1995].
Topology and Logic Programming
Proof: We prove the first of the claims in (c), with the others being proved
similarly. Let v denote the valuation corresponding to the interpretation I,
and, for each index i, let v i denote the valuation corresponding to the interpretation I i . Suppose first that (v i ) converges to v in the Scott topology
on I(X, T ), and let x ∈ X. Suppose further that x ∈ v t , so that v(x) = t.
Define u ∈ I(X, T ) by u(x) = t, and, for y = x, set u(y) = u. Then u is a
finite element satisfying u [ k v. Therefore, by Theorem 3.2.4, there exists i 0
such that u [ k v i whenever i ≥ i 0 , and hence eventually either v i (x) = t or
v i (x) = b. Thus, eventually x ∈ v it ∪ v i b . A similar argument holds in case
x ∈ v f or x ∈ v b , and hence we obtain the stated condition.
Conversely, suppose that the given condition holds. Let u be a finite valuation such that u [ k v, and suppose further that u takes value u at all points of
X except possibly at one point x, say. Let us first suppose that u(x) = t. Then
either x ∈ v t or x ∈ v b . But then, by the given condition, either eventually
x ∈ v it ∪ v i b or eventually x ∈ v i b , and in either case, eventually u [ k v i . A
similar argument holds in case u(x) = f or u(x) = b. By a standard argument
using the directedness of the index set of the net v i , it follows that, for any
finite valuation u [ k v, we have eventually u [ k v i . Hence, (v i ) converges to
v in the Scott topology on I(X, T ), as required.
•
Thus, we obtain a uniform description of net convergence in the Scott
topology on (I(X, T ), [), where (T , ≤) is any one of the main sets of truth
values which are important in logic programming. Indeed, the convergence
conditions involved are simple, natural, and intuitive, and this is one of the
advantages of approaching this topic via convergence.
In fact, it is Part (a) of Theorem 3.2.6 which we will use most often, and
we illustrate its use next with an example.
3.2.7 Example The following statements concerning convergence in the
Scott topology hold in two-valued logic.
10
(1) Any net (I λ ) of interpretations converges to the empty interpretation ∅.
(2) If (I λ ) is a net of interpretations which is monotonic in the sense that
I λ ⊆ I γ whenever λ ≤ γ, then (I λ ) converges to
λ I λ .
(3) If a net (I λ ) of interpretations converges to an interpretation I, and J ⊆ I,
then (I λ ) converges to J. Thus, in general, a net (I λ ) of interpretations
has many limits. A specific example of this can be given as follows. Suppose that L is a first-order language containing a unary predicate symbol p, a unary function symbol s, and a constant symbol a, such as the
language underlying Example 3.2.3, say. Consider the sequence (I n ) of
interpretations defined as follows: I n is the set {p(a), p(s(a))} if n is even
and is the set {p(a), p(s(a)), p(s
2 (a))} if n is odd. Then (I n ) converges to
10 For further results in this direction, see [Seda, 1995].