92
Mathematical Aspects of Logic Programming Semantics
TABLE 4.1: Generalized metrics: Definition 4.2.1.
notion satisfies
(M1) (M2) (M3) (M4) (M5)
metric
×
×
×
×
ultrametric
×
×
×
(×)
×
pseudometric
×
×
×
pseudo-ultrametric
×
×
(×)
×
quasimetric
×
×
×
quasi-ultrametric
×
×
(×)
×
dislocated metric
×
×
×
dislocated ultrametric
×
×
(×)
×
dislocated quasimetric
×
×
dislocated quasi-ultrametric
×
(×)
×
quasi-pseudometric
×
×
quasi-pseudo-ultrametric
×
(×)
×
called the triangle inequality. Furthermore, if a (pseudo, quasi, d-)metric satisfies the strong triangle inequality (M5), then it is called a (pseudo-, quasi-,
d-)ultrametric. These notions are displayed in Table 4.1, where the symbol
× indicates that the respective condition is satisfied and the symbol (×) indicates that the respective condition is automatically satisfied; for example,
since the condition (M5) implies (M4), any distance function satisfying (M5)
automatically satisfies (M4).
Note that one can take the codomain of � to be [0, ∞] in Definition 4.2.1
rather than R
+ . We note then that all the distance functions just considered
0
in Definition 4.2.1, apart from dislocated metrics, are continuity functions,
as is easily checked. However, even dislocated metrics give rise to topologies,
and essentially the same correspondence between them and topologies holds
between continuity spaces and topologies, as we see later.
6 Indeed, each dmetric gives rise to its associated metric, see Definition 4.8.9, and each dgeneralized ultrametric gives rise to its associated generalized ultrametric, see
Definition 4.8.19.
4.2.2 Remark As far as notation for distance functions is concerned, we will,
generally, although not rigidly, use d and occasionally λ to denote metrics,
ultrametrics, pseudometrics, and quasimetrics, all as just defined; we will use
� and occasionally ρ to denote d-metrics, to denote generalized ultrametrics
as introduced in Section 4.3, and to denote the extensions of these notions
studied in Section 4.4 and beyond. This convention will be employed both
in the context of single-valued mappings and in the context of multivalued
6 See [Hitzler and Seda, 2000] for full details of the topology determined by a d-metric.
Mathematical Aspects of Logic Programming Semantics
TABLE 4.1: Generalized metrics: Definition 4.2.1.
notion satisfies
(M1) (M2) (M3) (M4) (M5)
metric
×
×
×
×
ultrametric
×
×
×
(×)
×
pseudometric
×
×
×
pseudo-ultrametric
×
×
(×)
×
quasimetric
×
×
×
quasi-ultrametric
×
×
(×)
×
dislocated metric
×
×
×
dislocated ultrametric
×
×
(×)
×
dislocated quasimetric
×
×
dislocated quasi-ultrametric
×
(×)
×
quasi-pseudometric
×
×
quasi-pseudo-ultrametric
×
(×)
×
called the triangle inequality. Furthermore, if a (pseudo, quasi, d-)metric satisfies the strong triangle inequality (M5), then it is called a (pseudo-, quasi-,
d-)ultrametric. These notions are displayed in Table 4.1, where the symbol
× indicates that the respective condition is satisfied and the symbol (×) indicates that the respective condition is automatically satisfied; for example,
since the condition (M5) implies (M4), any distance function satisfying (M5)
automatically satisfies (M4).
Note that one can take the codomain of � to be [0, ∞] in Definition 4.2.1
rather than R
+ . We note then that all the distance functions just considered
0
in Definition 4.2.1, apart from dislocated metrics, are continuity functions,
as is easily checked. However, even dislocated metrics give rise to topologies,
and essentially the same correspondence between them and topologies holds
between continuity spaces and topologies, as we see later.
6 Indeed, each dmetric gives rise to its associated metric, see Definition 4.8.9, and each dgeneralized ultrametric gives rise to its associated generalized ultrametric, see
Definition 4.8.19.
4.2.2 Remark As far as notation for distance functions is concerned, we will,
generally, although not rigidly, use d and occasionally λ to denote metrics,
ultrametrics, pseudometrics, and quasimetrics, all as just defined; we will use
� and occasionally ρ to denote d-metrics, to denote generalized ultrametrics
as introduced in Section 4.3, and to denote the extensions of these notions
studied in Section 4.4 and beyond. This convention will be employed both
in the context of single-valued mappings and in the context of multivalued
6 See [Hitzler and Seda, 2000] for full details of the topology determined by a d-metric.