Fixed-Point Theory for Generalized Metric Spaces
109
called a rank function,
21 such that r
−1 (n) is a finite set for each n ∈ N. Define
: D × D → R by
22
d r
d r (x, y) := inf{2
−n | (c [ x =⇒ c [ y) for all c ∈ D c with r(c) < n}.
Then d r is called the quasi-ultrametric induced by r.
It is straightforward to see that (D, d r ) is a quasi-ultrametric space. Furthermore, d r induces the Scott topology on D, and (D, d r ) is totally bounded,
see Proposition 4.6.10.
In order to discuss the relationships between quasimetrics and the Cantor
topology on spaces of interpretations, we need the following proposition.
4.6.8 Proposition Let (X, d) be a totally bounded quasimetric space, and
let (x n ) be a Cauchy sequence in X. Then, for all ε > 0, there exists k ∈ N
such that for all l, m ≥ k, d
∗ (x l , x m ) < ε. (A sequence with this property is
usually called a bi-Cauchy sequence.)
Proof: Choose ε > 0 and a finite subset E ⊆ X together with a map h : N →
ε
E such that d
∗ (x n , h(n)) < , using total boundedness. Since (x n ) is a Cauchy
3
ε
sequence, there exists k 0 ∈ N such that for all m ≥ l ≥ k 0 , d(x l , x m ) < .
3
Now choose k 1 ≥ k 0 such that for every e ∈ E, the set h
−1 (e) ∩ {n | n ≥ k 1 }
is either infinite or empty. Choose now l, m ≥ k 1 , and let p ≥ l be minimal
such that h(p) = h(m). Then
d(x l , x m ) ≤ d(x l , x p ) + d(x p , h(p)) + d(h(p), x m ) < 3 ·
ε = ε,
3
and by symmetry d
∗ (x l , x m ) < ε.
•
We next define totally bounded quasi-ultrametrics on I P , for a given program P , by using level mappings and show that these are closely related to
the Cantor topology Q.
4.6.9 Definition Let P be a normal logic program, and let l : B P → N be a
level mapping for P such that l
−1 (n) is finite for every n ∈ N. The mapping
l induces a rank function r : I c → N defined by
r(I) = max{l(A)},
A∈I
where we take I c = (I P ) c to be the set of all finite subsets of B P . By Definition
4.6.7, r induces a quasi-ultrametric d r on I P .
For a given normal logic program P , we will denote I P,2 by I P for the rest
of this section.
21 The notion of rank function will be given in more generality in Definition 4.8.12.
22 The definition of dr is similar to one made by M.B. Smyth in Example 5 of the paper
[Smyth, 1991].
109
called a rank function,
21 such that r
−1 (n) is a finite set for each n ∈ N. Define
: D × D → R by
22
d r
d r (x, y) := inf{2
−n | (c [ x =⇒ c [ y) for all c ∈ D c with r(c) < n}.
Then d r is called the quasi-ultrametric induced by r.
It is straightforward to see that (D, d r ) is a quasi-ultrametric space. Furthermore, d r induces the Scott topology on D, and (D, d r ) is totally bounded,
see Proposition 4.6.10.
In order to discuss the relationships between quasimetrics and the Cantor
topology on spaces of interpretations, we need the following proposition.
4.6.8 Proposition Let (X, d) be a totally bounded quasimetric space, and
let (x n ) be a Cauchy sequence in X. Then, for all ε > 0, there exists k ∈ N
such that for all l, m ≥ k, d
∗ (x l , x m ) < ε. (A sequence with this property is
usually called a bi-Cauchy sequence.)
Proof: Choose ε > 0 and a finite subset E ⊆ X together with a map h : N →
ε
E such that d
∗ (x n , h(n)) < , using total boundedness. Since (x n ) is a Cauchy
3
ε
sequence, there exists k 0 ∈ N such that for all m ≥ l ≥ k 0 , d(x l , x m ) < .
3
Now choose k 1 ≥ k 0 such that for every e ∈ E, the set h
−1 (e) ∩ {n | n ≥ k 1 }
is either infinite or empty. Choose now l, m ≥ k 1 , and let p ≥ l be minimal
such that h(p) = h(m). Then
d(x l , x m ) ≤ d(x l , x p ) + d(x p , h(p)) + d(h(p), x m ) < 3 ·
ε = ε,
3
and by symmetry d
∗ (x l , x m ) < ε.
•
We next define totally bounded quasi-ultrametrics on I P , for a given program P , by using level mappings and show that these are closely related to
the Cantor topology Q.
4.6.9 Definition Let P be a normal logic program, and let l : B P → N be a
level mapping for P such that l
−1 (n) is finite for every n ∈ N. The mapping
l induces a rank function r : I c → N defined by
r(I) = max{l(A)},
A∈I
where we take I c = (I P ) c to be the set of all finite subsets of B P . By Definition
4.6.7, r induces a quasi-ultrametric d r on I P .
For a given normal logic program P , we will denote I P,2 by I P for the rest
of this section.
21 The notion of rank function will be given in more generality in Definition 4.8.12.
22 The definition of dr is similar to one made by M.B. Smyth in Example 5 of the paper
[Smyth, 1991].