119
Fixed-Point Theory for Generalized Metric Spaces
ultrametrics, which have applications both in logic programming and more
generally in theoretical computer science.
23
As in Remark 4.3.2, let γ denote an arbitrary ordinal, and let Γ γ denote
the set {2
−α | α < γ} of symbols 2
−α ordered by 2
−α < 2
−β if and only
if β < α. As already noted, this ordering is, in effect, the dual of the usual
ordering on γ. However, we find it convenient to work with the set Γ γ and the
ordering just defined, rather than with the dual ordering on γ, especially in
1
the context of contraction mappings whose contractivity factor is , see, for
2
example, Proposition 4.8.17 and particularly Theorem 5.1.6.
We recall that the set of compact elements in a domain D is denoted by
D c , see Definition 1.1.4.
4.8.12 Definition Let r : D c → γ be a function, called a rank function, form
Γ γ+1 , and denote 2
−γ by 0. Define � r : D × D → Γ γ+1 by � r (x, y) = inf{2
−α |
c [ x if and only if c [ y for every c ∈ D c with r(c) < α}.
It is readily checked that (D, � r ) is a generalized ultrametric space. We
call � r the generalized ultrametric induced by the rank function r. Indeed, the
intuition behind � r is that two elements x and y of the domain D are close
if they dominate the same compact elements up to a certain rank (and hence
agree in this sense up to this rank); the higher the rank giving agreement, the
closer are x and y. Furthermore, (D, � r ) is spherically complete. The proof
of this claim does not make use of the existence of a bottom element of D,
so this requirement can be omitted. The main idea of the proof is captured
in the next lemma, which shows that chains of balls give rise to chains of
elements in the domain. It depends on the following two elementary facts,
which result immediately from Lemma 4.3.5: (1) if γ ≤ δ and x ∈ B δ (y), then
B γ (x) ⊆ B δ (y), and (2) if B γ (x) ⊂ B δ (y), then δ ≤ γ (thus, γ < δ, if Γ is
totally ordered).
In order to simplify notation in the following proofs, we will denote the
ball B 2 −α (x) by B
α (x).
4.8.13 Lemma Let B
β (y) and B
α (x) be arbitrary balls in (D, � r ). Then the
following statements hold.
(a) For any z ∈ B
β (y), we have {c ∈ approx(z) | r(c) < β} = {c ∈ approx(y) |
r(c) < β}.
(b) B β = {c ∈ approx(y) | r(c) < β} and B α = {c ∈ approx(x) | r(c) <
α} both exist.
23 This point of view is further developed in a number of papers including the following:
[Kuhlmann, 1999], [Ribenboim, 1996], [Bouamama et al., 2000], [Prieß-Crampe, 1990]; also
the papers [Prieß-Crampe and Ribenboim, 1993], [Prieß-Crampe and Ribenboim, 2000c],
[Prieß-Crampe and Ribenboim, 2000b], [Prieß-Crampe and Ribenboim, 2000a] should be
consulted.
Fixed-Point Theory for Generalized Metric Spaces
ultrametrics, which have applications both in logic programming and more
generally in theoretical computer science.
23
As in Remark 4.3.2, let γ denote an arbitrary ordinal, and let Γ γ denote
the set {2
−α | α < γ} of symbols 2
−α ordered by 2
−α < 2
−β if and only
if β < α. As already noted, this ordering is, in effect, the dual of the usual
ordering on γ. However, we find it convenient to work with the set Γ γ and the
ordering just defined, rather than with the dual ordering on γ, especially in
1
the context of contraction mappings whose contractivity factor is , see, for
2
example, Proposition 4.8.17 and particularly Theorem 5.1.6.
We recall that the set of compact elements in a domain D is denoted by
D c , see Definition 1.1.4.
4.8.12 Definition Let r : D c → γ be a function, called a rank function, form
Γ γ+1 , and denote 2
−γ by 0. Define � r : D × D → Γ γ+1 by � r (x, y) = inf{2
−α |
c [ x if and only if c [ y for every c ∈ D c with r(c) < α}.
It is readily checked that (D, � r ) is a generalized ultrametric space. We
call � r the generalized ultrametric induced by the rank function r. Indeed, the
intuition behind � r is that two elements x and y of the domain D are close
if they dominate the same compact elements up to a certain rank (and hence
agree in this sense up to this rank); the higher the rank giving agreement, the
closer are x and y. Furthermore, (D, � r ) is spherically complete. The proof
of this claim does not make use of the existence of a bottom element of D,
so this requirement can be omitted. The main idea of the proof is captured
in the next lemma, which shows that chains of balls give rise to chains of
elements in the domain. It depends on the following two elementary facts,
which result immediately from Lemma 4.3.5: (1) if γ ≤ δ and x ∈ B δ (y), then
B γ (x) ⊆ B δ (y), and (2) if B γ (x) ⊂ B δ (y), then δ ≤ γ (thus, γ < δ, if Γ is
totally ordered).
In order to simplify notation in the following proofs, we will denote the
ball B 2 −α (x) by B
α (x).
4.8.13 Lemma Let B
β (y) and B
α (x) be arbitrary balls in (D, � r ). Then the
following statements hold.
(a) For any z ∈ B
β (y), we have {c ∈ approx(z) | r(c) < β} = {c ∈ approx(y) |
r(c) < β}.
(b) B β = {c ∈ approx(y) | r(c) < β} and B α = {c ∈ approx(x) | r(c) <
α} both exist.
23 This point of view is further developed in a number of papers including the following:
[Kuhlmann, 1999], [Ribenboim, 1996], [Bouamama et al., 2000], [Prieß-Crampe, 1990]; also
the papers [Prieß-Crampe and Ribenboim, 1993], [Prieß-Crampe and Ribenboim, 2000c],
[Prieß-Crampe and Ribenboim, 2000b], [Prieß-Crampe and Ribenboim, 2000a] should be
consulted.