2
Mathematical Aspects of Logic Programming Semantics
(We refer the reader to the Appendix for a brief discussion of the theory of
ordinals.) We note that any ω-chain is, of course, a chain.
A non-empty subset A of a partially ordered set (D, [) is called directed if,
for all a, b ∈ A, there is c ∈ A with a [ c and b [ c. An element b in an ordered
set D is called an upper bound of a subset A of D if we have a [ b for all a ∈ A
and is called a least upper bound or supremum of A if b is an upper bound of A
satisfying b [ b
' for all upper bounds b
' of A. Of course, by antisymmetry, the
supremum, A or sup A, of A is unique if it exists. Similarly, one defines lower
bound and the greatest lower bound or infimum,
n
A or inf A, of a subset A
of D. An element x of D is called maximal (minimal ) if we do not have x c y
(y c x) for any element y of D. Given an ordering [ on a set D, we define the
dual ordering [
d on D by x [
d y if and only if y [ x. Lower bounds, greatest
lower bounds, etc. in [ correspond to upper bounds, least upper bounds, etc.
in [
d .
1.1.1 Definition Let (D, [) be a partially ordered set.
(1) We call (D, [) an ω-complete partial order or an ω-cpo if A exists in D
for each ω-chain A in D, and D has an element ⊥, called the least element
or bottom element, satisfying ⊥ [ x for all x
∈ D.
(2) We call (D, [) chain complete if every chain in D has a supremum.
(3) We call (D, [) a complete partial order or a cpo if A exists in D for
each directed subset A of D, and D has a bottom elemen
t.
(4) We call (D, [) a complete upp
n er semi-lattice if A exists in D for each
directed subset A of D, and A exists for each
subset A of D.
(5) We call (D, [) a complete lattice if
A and
n
A exist in D for every
subset A of D.
Later on, we will encounter examples of each of these notions in the context
of spaces of valuations. Notice that on taking A = D in the previous definition,
we see that a complete upper semi-lattice or a complete lattice always has
a bottom element and that a complete lattice always has a top element or
greatest element, that is, an element T satisfying a [ T for all a ∈ D.
There are various implications between the notions formulated in Definition 1.1.1, some of which are obvious. Indeed, as far as the various notions of
completeness are concerned, each defined concept is apparently less general
than its predecessor. For example, since any chain is a directed set, we see that
any complete partial order is chain complete, and any chain-complete poset
with a bottom element is an ω-complete partial order. However, the following
fact, which we simply state, is less trivial.
2
2 For a discussion of chain completeness versus completeness (for directed sets), we refer
the reader to [Markowsky, 1976]; see also [Abramsky and Jung, 1994, Proposition 2.1.15].
Mathematical Aspects of Logic Programming Semantics
(We refer the reader to the Appendix for a brief discussion of the theory of
ordinals.) We note that any ω-chain is, of course, a chain.
A non-empty subset A of a partially ordered set (D, [) is called directed if,
for all a, b ∈ A, there is c ∈ A with a [ c and b [ c. An element b in an ordered
set D is called an upper bound of a subset A of D if we have a [ b for all a ∈ A
and is called a least upper bound or supremum of A if b is an upper bound of A
satisfying b [ b
' for all upper bounds b
' of A. Of course, by antisymmetry, the
supremum, A or sup A, of A is unique if it exists. Similarly, one defines lower
bound and the greatest lower bound or infimum,
n
A or inf A, of a subset A
of D. An element x of D is called maximal (minimal ) if we do not have x c y
(y c x) for any element y of D. Given an ordering [ on a set D, we define the
dual ordering [
d on D by x [
d y if and only if y [ x. Lower bounds, greatest
lower bounds, etc. in [ correspond to upper bounds, least upper bounds, etc.
in [
d .
1.1.1 Definition Let (D, [) be a partially ordered set.
(1) We call (D, [) an ω-complete partial order or an ω-cpo if A exists in D
for each ω-chain A in D, and D has an element ⊥, called the least element
or bottom element, satisfying ⊥ [ x for all x
∈ D.
(2) We call (D, [) chain complete if every chain in D has a supremum.
(3) We call (D, [) a complete partial order or a cpo if A exists in D for
each directed subset A of D, and D has a bottom elemen
t.
(4) We call (D, [) a complete upp
n er semi-lattice if A exists in D for each
directed subset A of D, and A exists for each
subset A of D.
(5) We call (D, [) a complete lattice if
A and
n
A exist in D for every
subset A of D.
Later on, we will encounter examples of each of these notions in the context
of spaces of valuations. Notice that on taking A = D in the previous definition,
we see that a complete upper semi-lattice or a complete lattice always has
a bottom element and that a complete lattice always has a top element or
greatest element, that is, an element T satisfying a [ T for all a ∈ D.
There are various implications between the notions formulated in Definition 1.1.1, some of which are obvious. Indeed, as far as the various notions of
completeness are concerned, each defined concept is apparently less general
than its predecessor. For example, since any chain is a directed set, we see that
any complete partial order is chain complete, and any chain-complete poset
with a bottom element is an ω-complete partial order. However, the following
fact, which we simply state, is less trivial.
2
2 For a discussion of chain completeness versus completeness (for directed sets), we refer
the reader to [Markowsky, 1976]; see also [Abramsky and Jung, 1994, Proposition 2.1.15].