98
Mathematical Aspects of Logic Programming Semantics
TABLE 4.2: (Dislocated) generalized ultrametrics: Definition 4.3.1.
notion satisfies
(U1) (U2) (U3) (U4)
generalized ultrametric (gum)
×
×
×
×
dislocated generalized ultrametric (d-gum)
×
×
×
see Table 4.2. Condition (U4) will be called the strong triangle inequality for
gums. We note that any gum is a d-gum.
4.3.2 Remark It is clear that every ultrametric space is also a generalized
ultrametric space. However, at the level of generality of the previous definition,
the function � this time is not a continuity function, that is, Γ need not be
a value semigroup. However, in the applications we will actually consider, Γ
will be a value semigroup, and � will indeed be a continuity function, and we
consider this point next.
Let γ > 0 denote an arbitrary ordinal, and denote by Γ γ the set {2
−α |
α < γ} of symbols 2
−α . Then Γ γ is totally ordered by 2
−α < 2
−β if and only
if β < α. Notice that Γ γ is really nothing other than γ endowed with the dual
of the usual ordering on ordinals, but it is convenient to use the symbols 2
−α
rather than the symbols α to denote typical elements, as will be seen later in
Section 4.8.2 and beyond. Notice also, as is commonly done, that we view an
ordinal γ as the set of all ordinals n such that n ∈ γ, that is, as the set of
ordinals n such that n < γ. Finally, we define the binary operation + on Γ γ
by
2
−α + 2
−β = max{2
−α , 2
−β }
noting that 2
−0 is an absorbing element for this operation. In particular,
applying this construction to the ordinal γ + 1, we note that 2
−γ is both the
bottom element of Γ γ+1 and the identity element for the operation + defined
on Γ γ+1 . Furthermore, 2
−γ = 2
−0 since γ > 0, where 0 denotes the finite
limit ordinal zero, and we note that we will sometimes also use 0 to denote
2
−γ where this does not cause confusion. Then Γ γ+1 is a value semigroup in
which
a
α
2 = a, where a = 2
− denotes a typical element of Γ γ+1 , and moreover,
the partial order induced on Γ γ+1 by + coincides with that already defined.
Furthermore, the set {2
−α | α < γ} is a set of positives in Γ γ+1 . It is the case
Γ = Γ γ+1 which is of most interest to us. Therefore, in these cases of most
interest, (X, � , Γ) is a continuity space. In fact, we shall take these points
further later on in this chapter by turning a domain (D, [) into a generalized
ultrametric space, see Sections 4.8.2 and 4.8.3 (and also Section 5.1.1).
The following definitions prepare the way for the main result of this section, namely, Theorem 4.3.6, which provides the main fixed-point theorem
applicable to gums. We note that the requisite form of completeness here is
Mathematical Aspects of Logic Programming Semantics
TABLE 4.2: (Dislocated) generalized ultrametrics: Definition 4.3.1.
notion satisfies
(U1) (U2) (U3) (U4)
generalized ultrametric (gum)
×
×
×
×
dislocated generalized ultrametric (d-gum)
×
×
×
see Table 4.2. Condition (U4) will be called the strong triangle inequality for
gums. We note that any gum is a d-gum.
4.3.2 Remark It is clear that every ultrametric space is also a generalized
ultrametric space. However, at the level of generality of the previous definition,
the function � this time is not a continuity function, that is, Γ need not be
a value semigroup. However, in the applications we will actually consider, Γ
will be a value semigroup, and � will indeed be a continuity function, and we
consider this point next.
Let γ > 0 denote an arbitrary ordinal, and denote by Γ γ the set {2
−α |
α < γ} of symbols 2
−α . Then Γ γ is totally ordered by 2
−α < 2
−β if and only
if β < α. Notice that Γ γ is really nothing other than γ endowed with the dual
of the usual ordering on ordinals, but it is convenient to use the symbols 2
−α
rather than the symbols α to denote typical elements, as will be seen later in
Section 4.8.2 and beyond. Notice also, as is commonly done, that we view an
ordinal γ as the set of all ordinals n such that n ∈ γ, that is, as the set of
ordinals n such that n < γ. Finally, we define the binary operation + on Γ γ
by
2
−α + 2
−β = max{2
−α , 2
−β }
noting that 2
−0 is an absorbing element for this operation. In particular,
applying this construction to the ordinal γ + 1, we note that 2
−γ is both the
bottom element of Γ γ+1 and the identity element for the operation + defined
on Γ γ+1 . Furthermore, 2
−γ = 2
−0 since γ > 0, where 0 denotes the finite
limit ordinal zero, and we note that we will sometimes also use 0 to denote
2
−γ where this does not cause confusion. Then Γ γ+1 is a value semigroup in
which
a
α
2 = a, where a = 2
− denotes a typical element of Γ γ+1 , and moreover,
the partial order induced on Γ γ+1 by + coincides with that already defined.
Furthermore, the set {2
−α | α < γ} is a set of positives in Γ γ+1 . It is the case
Γ = Γ γ+1 which is of most interest to us. Therefore, in these cases of most
interest, (X, � , Γ) is a continuity space. In fact, we shall take these points
further later on in this chapter by turning a domain (D, [) into a generalized
ultrametric space, see Sections 4.8.2 and 4.8.3 (and also Section 5.1.1).
The following definitions prepare the way for the main result of this section, namely, Theorem 4.3.6, which provides the main fixed-point theorem
applicable to gums. We note that the requisite form of completeness here is