130
Mathematical Aspects of Logic Programming Semantics
The following theorem was proved by Prieß-Crampe and Ribenboim, see
[Prieß-Crampe and Ribenboim, 2000c], and is a multivalued version of Theorem 4.3.6.
4.12.2 Theorem (Prieß-Crampe and Ribenboim) Let (X, �, Γ) be a
spherically complete, generalized ultrametric space, and let T : X → P(X)
be non-empty, non-expanding, and strictly contracting on orbits. In addition,
assume that for every x ∈ X, Min Π x is finite and that every element of Π x
has a lower bound in Min Π x . Then T has a fixed point.
This result has several corollaries, due to Prieß-Crampe and Ribenboim,
see [Prieß-Crampe and Ribenboim, 2000c], both for multivalued mappings
and for single-valued mappings, and we state two of these next for completeness. Theorem 4.12.2 has been applied to establish the stable model semantics
for disjunctive logic programs, see [Seda and Hitzler, 2010]. Note that Theorem 4.12.4 is a slight extension of Theorem 4.3.6.
4.12.3 Theorem Let (X, �, Γ) be spherically complete, and let Γ be narrow,
that is, such that every trivially ordered subset of Γ is finite. Let f : X → P(X)
be non-empty, strictly contracting on orbits and such that f (x) is spherically
complete for every x ∈ X. Then f has a fixed point.
4.12.4 Theorem Let (X, �, Γ) be a spherically complete, generalized ultrametric space, and let f : X → X be non-expanding on X. Then either f
has a fixed point or there exists a ball B π (z) such that �(y, f (y)) = π for all
y ∈ B π (z). If, in addition, f is strictly contracting on orbits, then f has a
fixed point. Finally, this fixed point is unique if f is strictly contracting on X.
The following ideas are closely related to the notion of value semigroup
given in Definition 4.1.2 and were considered by Khamsi, Kreinovich, and
Misane in the context of the stable model semantics for disjunctive logic programs, see [Khamsi et al., 1993]. We show that, in fact, these notions basically
coincide with those from generalized ultrametric theory.
4.12.5 Definition Let V be an ordered Abelian semigroup with 0, and let
X be an arbitrary set. A g-metric on X is a mapping ρ : X × X → V which
satisfies the following conditions for all x, y, z ∈ X.
(1) ρ(x, y) = 0 if and only if x = y.
(2) ρ(x, y) = ρ(y, x).
(3) ρ(x, y) ≤ ρ(x, z) + ρ(z, y).
A pair (X, ρ) consisting of a set X and a g-metric ρ on X is called a g-metric
space.
Mathematical Aspects of Logic Programming Semantics
The following theorem was proved by Prieß-Crampe and Ribenboim, see
[Prieß-Crampe and Ribenboim, 2000c], and is a multivalued version of Theorem 4.3.6.
4.12.2 Theorem (Prieß-Crampe and Ribenboim) Let (X, �, Γ) be a
spherically complete, generalized ultrametric space, and let T : X → P(X)
be non-empty, non-expanding, and strictly contracting on orbits. In addition,
assume that for every x ∈ X, Min Π x is finite and that every element of Π x
has a lower bound in Min Π x . Then T has a fixed point.
This result has several corollaries, due to Prieß-Crampe and Ribenboim,
see [Prieß-Crampe and Ribenboim, 2000c], both for multivalued mappings
and for single-valued mappings, and we state two of these next for completeness. Theorem 4.12.2 has been applied to establish the stable model semantics
for disjunctive logic programs, see [Seda and Hitzler, 2010]. Note that Theorem 4.12.4 is a slight extension of Theorem 4.3.6.
4.12.3 Theorem Let (X, �, Γ) be spherically complete, and let Γ be narrow,
that is, such that every trivially ordered subset of Γ is finite. Let f : X → P(X)
be non-empty, strictly contracting on orbits and such that f (x) is spherically
complete for every x ∈ X. Then f has a fixed point.
4.12.4 Theorem Let (X, �, Γ) be a spherically complete, generalized ultrametric space, and let f : X → X be non-expanding on X. Then either f
has a fixed point or there exists a ball B π (z) such that �(y, f (y)) = π for all
y ∈ B π (z). If, in addition, f is strictly contracting on orbits, then f has a
fixed point. Finally, this fixed point is unique if f is strictly contracting on X.
The following ideas are closely related to the notion of value semigroup
given in Definition 4.1.2 and were considered by Khamsi, Kreinovich, and
Misane in the context of the stable model semantics for disjunctive logic programs, see [Khamsi et al., 1993]. We show that, in fact, these notions basically
coincide with those from generalized ultrametric theory.
4.12.5 Definition Let V be an ordered Abelian semigroup with 0, and let
X be an arbitrary set. A g-metric on X is a mapping ρ : X × X → V which
satisfies the following conditions for all x, y, z ∈ X.
(1) ρ(x, y) = 0 if and only if x = y.
(2) ρ(x, y) = ρ(y, x).
(3) ρ(x, y) ≤ ρ(x, z) + ρ(z, y).
A pair (X, ρ) consisting of a set X and a g-metric ρ on X is called a g-metric
space.