106
Mathematical Aspects of Logic Programming Semantics
4.6 Quasimetrics
Quasimetrics are a convenient way of reconciling metric and order structures, see Example 4.6.4. We give the relevant definitions in order to state and
prove the Rutten-Smyth theorem,
18 which is the appropriate analogue of the
Banach theorem for quasimetric spaces.
4.6.1 Definition A sequence (x n ) in a quasimetric space (X, d) is a (forward )
Cauchy sequence if, for all ε > 0, there exists n 0 ∈ N such that for all n ≥
m ≥ n 0 we have d(x m , x n ) < ε. A Cauchy sequence (x n ) converges to x ∈ X
if, for all y ∈ X, d(x, y) = lim n→∞ d(x n , y). Finally, X is called CS-complete
if every Cauchy sequence in X converges.
Note that limits of Cauchy sequences in quasimetric spaces are unique.
Given a quasimetric space (X, d), d induces a partial order ≤ d on X, called
the partial order induced by d, by setting x ≤ d y if and only if d(x, y) = 0.
Furthermore, if (X, d) is a quasimetric space, then (X, d
∗ ) is a metric space,
where d
∗ (x, y) = max{d(x, y), d(y, x)}, and d
∗ is called the metric induced by
d. We call a quasimetric space (X, d) totally bounded if for every ε > 0 there
exists a finite set E ⊆ X such that for every y ∈ X there is an e ∈ E with
d
∗ (e, y) < ε.
4.6.2 Definition Let X be a quasimetric space, and let f : X → X be a
function.
(1) f is called CS-continuous if, for all Cauchy sequences (x n ) in X which
converge to x, (f (x n )) is a Cauchy sequence which converges to f (x).
(2) f is called non-expanding if d(f (x), f (y)) ≤ d(x, y) for all x, y ∈ X.
(3) f is called contractive if there exists some c with 0 ≤ c < 1 such that
d(f (x), f (y)) ≤ c · d(x, y) for all x, y ∈ X.
Contractive mappings are not necessarily CS-continuous: consider the set
N ∪ {∞} with the natural order and the distance function
0 if x y,
d(x, y) =
⎪
⎧
⎨
1
≤
⎪
if
⎩
x = 1 and y = 0,
2
1 otherwise.
Then the function f which maps any n ∈ N to 0 and ∞ to 1 is contractive,
but not continuous since lim n N n = ∞, whereas lim f (n) = 0 = 1 = f (
∈
∞).
18 We give Theorem 4.6.3 in the form in which it appears in [Rutten, 1996]; see also the
paper [Rutten, 1995]. A more general version of this result was given in [Smyth, 1987] in
the context of quasi-uniformities.
Mathematical Aspects of Logic Programming Semantics
4.6 Quasimetrics
Quasimetrics are a convenient way of reconciling metric and order structures, see Example 4.6.4. We give the relevant definitions in order to state and
prove the Rutten-Smyth theorem,
18 which is the appropriate analogue of the
Banach theorem for quasimetric spaces.
4.6.1 Definition A sequence (x n ) in a quasimetric space (X, d) is a (forward )
Cauchy sequence if, for all ε > 0, there exists n 0 ∈ N such that for all n ≥
m ≥ n 0 we have d(x m , x n ) < ε. A Cauchy sequence (x n ) converges to x ∈ X
if, for all y ∈ X, d(x, y) = lim n→∞ d(x n , y). Finally, X is called CS-complete
if every Cauchy sequence in X converges.
Note that limits of Cauchy sequences in quasimetric spaces are unique.
Given a quasimetric space (X, d), d induces a partial order ≤ d on X, called
the partial order induced by d, by setting x ≤ d y if and only if d(x, y) = 0.
Furthermore, if (X, d) is a quasimetric space, then (X, d
∗ ) is a metric space,
where d
∗ (x, y) = max{d(x, y), d(y, x)}, and d
∗ is called the metric induced by
d. We call a quasimetric space (X, d) totally bounded if for every ε > 0 there
exists a finite set E ⊆ X such that for every y ∈ X there is an e ∈ E with
d
∗ (e, y) < ε.
4.6.2 Definition Let X be a quasimetric space, and let f : X → X be a
function.
(1) f is called CS-continuous if, for all Cauchy sequences (x n ) in X which
converge to x, (f (x n )) is a Cauchy sequence which converges to f (x).
(2) f is called non-expanding if d(f (x), f (y)) ≤ d(x, y) for all x, y ∈ X.
(3) f is called contractive if there exists some c with 0 ≤ c < 1 such that
d(f (x), f (y)) ≤ c · d(x, y) for all x, y ∈ X.
Contractive mappings are not necessarily CS-continuous: consider the set
N ∪ {∞} with the natural order and the distance function
0 if x y,
d(x, y) =
⎪
⎧
⎨
1
≤
⎪
if
⎩
x = 1 and y = 0,
2
1 otherwise.
Then the function f which maps any n ∈ N to 0 and ∞ to 1 is contractive,
but not continuous since lim n N n = ∞, whereas lim f (n) = 0 = 1 = f (
∈
∞).
18 We give Theorem 4.6.3 in the form in which it appears in [Rutten, 1996]; see also the
paper [Rutten, 1995]. A more general version of this result was given in [Smyth, 1987] in
the context of quasi-uniformities.