81
Topology and Logic Programming
the domain of interpretation is countable, as shown in the following example.
In fact, in this next example, we show that a sequence (I n ) of two-valued
interpretations converges in Q to a two-valued interpretation I if and only
if the symmetric difference
14 I n D I of the sets representing I n and I can be
made arbitrarily small (in the sense described in Example 3.3.8), and this fact
appears to be in accord with one’s intuition regarding negation. Indeed, the
symmetric difference provides a simple metric for the topology Q, as we see
next.
3.3.8 Example Let P denote a normal logic program, and, to make the
discussion non-trivial, suppose that the underlying first-order language L of
P contains at least one function symbol. Thus, B P is denumerable, and we
can suppose that the elements of B P are given some fixed listing, so that
B P = (A 1 , A 2 , A 3 , . . .), say. (In fact, the exact nature of B P plays no role
here, and we could work equally well over any preinterpretation J for L whose
domain is denumerable and can therefore be listed.) Now let d i be a real
o ∞
number satisfying 0 < d i < 1, for each i, and such that
d i = 1; each d i
i=1
is a weight to be attached to the element A i of B P . Now define the metric d
on I P by
d(I, I
' ) =
d i ,
Ai∈IfI /
'
for I, I ∈ I P . Note that it is routine to check that d does indeed define a
metric on I P , and we show that d generates the topology Q on I P . To do this,
it suffices to show that an arbitrary sequence (I n ) converges to I, say, in Q if
and only if it converges to I in the metric d.
Suppose that (I n ) is a sequence of interpretations in I P , and I n → I in
the metric d. Thus, d(I n , I) → 0 as n → ∞. So, given E > 0, there is a natural
o
number n 0 such that whenever n ≥ n 0 we have d(I n , I) =
d i <
Ai∈InfI
E. Suppose that A j ∈ I. Choose E so small that E < d j , and obtain the
o
corresponding n 0 such that
d i < E whenever n ≥ n 0 . Then obviously
Ai∈InfI
d j does not occur in this sum for any n ≥ n 0 . In other words, A j ∈ I n ∩ I for
all n ≥ n 0 , and so A j is eventually in I n . On the other hand, suppose that
o
A j ∈ I. If A j belongs to infinitely many I n , then
fI d i ≥ d j infinitely
Aj ∈In
often, contradicting d(I n , I) → 0. Thus, A j belongs to only finitely many I n ,
and so A j is eventually not in I n . Therefore, by Proposition 3.3.5, convergence
in d implies convergence in Q.
Conversely, suppose I n → I in Q. Given E > 0, choose integers n 0 so large
o
'
'
that i≥n0 d i < E and n 0 ≥ n 0 so large that whenever n ≥ n 0 , I n DI only
contains elements A j with j ≥ n 0 or is empty (this situation can be achieved
by finitely many applications of Proposition 3.3.5 since the set {A j ; j < n 0 }
'
is finite and, in fact, contains n 0 − 1 elements). Then, whenever n ≥ n 0 , we
have
d(I n , I) =
d j ≤
d i < E
Aj ∈InfI
i≥n0
14 We remind the reader that the symmetric difference of sets A and B is defined by
A6B = (A \ B) ∪ (B \ A).
Topology and Logic Programming
the domain of interpretation is countable, as shown in the following example.
In fact, in this next example, we show that a sequence (I n ) of two-valued
interpretations converges in Q to a two-valued interpretation I if and only
if the symmetric difference
14 I n D I of the sets representing I n and I can be
made arbitrarily small (in the sense described in Example 3.3.8), and this fact
appears to be in accord with one’s intuition regarding negation. Indeed, the
symmetric difference provides a simple metric for the topology Q, as we see
next.
3.3.8 Example Let P denote a normal logic program, and, to make the
discussion non-trivial, suppose that the underlying first-order language L of
P contains at least one function symbol. Thus, B P is denumerable, and we
can suppose that the elements of B P are given some fixed listing, so that
B P = (A 1 , A 2 , A 3 , . . .), say. (In fact, the exact nature of B P plays no role
here, and we could work equally well over any preinterpretation J for L whose
domain is denumerable and can therefore be listed.) Now let d i be a real
o ∞
number satisfying 0 < d i < 1, for each i, and such that
d i = 1; each d i
i=1
is a weight to be attached to the element A i of B P . Now define the metric d
on I P by
d(I, I
' ) =
d i ,
Ai∈IfI /
'
for I, I ∈ I P . Note that it is routine to check that d does indeed define a
metric on I P , and we show that d generates the topology Q on I P . To do this,
it suffices to show that an arbitrary sequence (I n ) converges to I, say, in Q if
and only if it converges to I in the metric d.
Suppose that (I n ) is a sequence of interpretations in I P , and I n → I in
the metric d. Thus, d(I n , I) → 0 as n → ∞. So, given E > 0, there is a natural
o
number n 0 such that whenever n ≥ n 0 we have d(I n , I) =
d i <
Ai∈InfI
E. Suppose that A j ∈ I. Choose E so small that E < d j , and obtain the
o
corresponding n 0 such that
d i < E whenever n ≥ n 0 . Then obviously
Ai∈InfI
d j does not occur in this sum for any n ≥ n 0 . In other words, A j ∈ I n ∩ I for
all n ≥ n 0 , and so A j is eventually in I n . On the other hand, suppose that
o
A j ∈ I. If A j belongs to infinitely many I n , then
fI d i ≥ d j infinitely
Aj ∈In
often, contradicting d(I n , I) → 0. Thus, A j belongs to only finitely many I n ,
and so A j is eventually not in I n . Therefore, by Proposition 3.3.5, convergence
in d implies convergence in Q.
Conversely, suppose I n → I in Q. Given E > 0, choose integers n 0 so large
o
'
'
that i≥n0 d i < E and n 0 ≥ n 0 so large that whenever n ≥ n 0 , I n DI only
contains elements A j with j ≥ n 0 or is empty (this situation can be achieved
by finitely many applications of Proposition 3.3.5 since the set {A j ; j < n 0 }
'
is finite and, in fact, contains n 0 − 1 elements). Then, whenever n ≥ n 0 , we
have
d(I n , I) =
d j ≤
d i < E
Aj ∈InfI
i≥n0
14 We remind the reader that the symmetric difference of sets A and B is defined by
A6B = (A \ B) ∪ (B \ A).