Chapter 4
Fixed-Point Theory for Generalized
Metric Spaces
In Chapters 1 and 2, we gave ample evidence of the fundamental role played
by the Kleene and Knaster-Tarski fixed-point theorems, Theorems 1.1.9 and
1.1.10, in logic programming semantics. Moreover, we have also seen that the
operator T P need not be monotonic for normal programs and, hence, that
the theorems just cited are not generally applicable to T P in this case. It is,
therefore, of interest to consider possible alternatives to Theorems 1.1.9 and
1.1.10, and in this chapter we discuss a number of such fixed-point theorems
and some related results which will be put to use later on.
Almost always, alternatives to the theorems of Kleene and Knaster-Tarski
employ distance functions in their formulations and in their applications.
1
Logic programming is no exception to this rule, and we will consider a number of ways in which distance functions can be naturally introduced into this
subject along with appropriate fixed-point theorems. Part of this process consists of working with quite general distance functions, relaxing in one way
or another the standard axioms for a metric, and establishing corresponding
fixed-point theorems analogous to the Banach contraction mapping theorem.
Nevertheless, the applications we make later and the examples we discuss
show that these general distance functions do quite easily and naturally arise
in logic programming, although applications will be deferred until Chapter 5.
Indeed, Sections 4.1 to 4.7 in this chapter deal with the different generalized
metrics and corresponding fixed-point theorems we develop for single-valued
mappings, while in Section 4.8 we examine the interconnections between the
spaces underlying the various distance functions we study and also discuss a
number of relevant examples. In Sections 4.9 to 4.14, we consider the corresponding results for multivalued mappings. Hence, in summary, this chapter
is a self-contained account of the pure metric fixed-point theory appropriate
to logic programming and also provides the tools needed for the application of
distance functions in developing a unified approach to the fixed-point theory
of very general and significant classes of logic programs in Chapters 5 and
6. In addition, the methods and results discussed in this chapter have potential applications to a wider spectrum of topics in computer science than just
simply logic programming, but none of these will be pursued here.
1 We refer again to [Kirk and Sims, 2001] as an excellent source of information on fixedpoint theory in general.
87
Fixed-Point Theory for Generalized
Metric Spaces
In Chapters 1 and 2, we gave ample evidence of the fundamental role played
by the Kleene and Knaster-Tarski fixed-point theorems, Theorems 1.1.9 and
1.1.10, in logic programming semantics. Moreover, we have also seen that the
operator T P need not be monotonic for normal programs and, hence, that
the theorems just cited are not generally applicable to T P in this case. It is,
therefore, of interest to consider possible alternatives to Theorems 1.1.9 and
1.1.10, and in this chapter we discuss a number of such fixed-point theorems
and some related results which will be put to use later on.
Almost always, alternatives to the theorems of Kleene and Knaster-Tarski
employ distance functions in their formulations and in their applications.
1
Logic programming is no exception to this rule, and we will consider a number of ways in which distance functions can be naturally introduced into this
subject along with appropriate fixed-point theorems. Part of this process consists of working with quite general distance functions, relaxing in one way
or another the standard axioms for a metric, and establishing corresponding
fixed-point theorems analogous to the Banach contraction mapping theorem.
Nevertheless, the applications we make later and the examples we discuss
show that these general distance functions do quite easily and naturally arise
in logic programming, although applications will be deferred until Chapter 5.
Indeed, Sections 4.1 to 4.7 in this chapter deal with the different generalized
metrics and corresponding fixed-point theorems we develop for single-valued
mappings, while in Section 4.8 we examine the interconnections between the
spaces underlying the various distance functions we study and also discuss a
number of relevant examples. In Sections 4.9 to 4.14, we consider the corresponding results for multivalued mappings. Hence, in summary, this chapter
is a self-contained account of the pure metric fixed-point theory appropriate
to logic programming and also provides the tools needed for the application of
distance functions in developing a unified approach to the fixed-point theory
of very general and significant classes of logic programs in Chapters 5 and
6. In addition, the methods and results discussed in this chapter have potential applications to a wider spectrum of topics in computer science than just
simply logic programming, but none of these will be pursued here.
1 We refer again to [Kirk and Sims, 2001] as an excellent source of information on fixedpoint theory in general.
87