3
Order and Logic
1.1.2 Proposition A partially ordered set (D, [) is a complete partial order
if and only if it has a bottom element and is chain complete.
Many aspects of theoretical computer science depend on the notion of
a partially ordered set. More structure is often required, however, than is
provided simply by a partial order or even by a complete partial order or
complete lattice. For example, one needs extra structure in order to model
standard programming language constructs or to provide an abstract theory of
computability, as well as having a satisfactory fixed-point theorem available. It
is now widely recognized that Scott’s theory of domains provides a satisfactory
setting in which to attain all these objectives, and we will find it useful later on
to view spaces of valuations as Scott domains. It will therefore be convenient
to give next the definition of the term “(Scott) domain” in the form in which
we will always use it. First, however, we need to define the notion of compact
element.
1.1.3 Definition Let (D [) be a partially ordered set. We call an element
a ∈ D compact or finite if it satisfies the property that whenever A is directed
and a [ A, we have a [ x for some x ∈ A. We denote the set of compact
elements in D by D c .
Notice that the bottom element in a complete partial order is always a
compact element, and hence the set D c is always non-empty in this case. The
compact elements are fundamental in domain theory.
1.1.4 Definition A Scott-Ershov domain, Scott domain, or just domain
(D, [) is a consistently complete algebraic complete partial order. Thus, the
following statements hold.
(1) (D, [) is a complete partial order.
(2) For each x ∈ D, the set approx(x) = {a ∈ D c | a [ x} is directed, and we
have x = approx(x) (the algebraicity of D).
(3) If the set
{a, b} ⊆ D c is consistent (that is, there exists x ∈ D such that
a [ x and b [ x), then {a, b} exists in D (the consistent completeness
of D).
We next give some simple examples of the concepts defined above; note
that (1) and (2) are special cases of Theorem 1.3.2.
1.1.5 Example (1) The power set D = P(N) of the set N of natural numbers
is a complete lattice when ordered by set inclusion. In this ordering, D is
also a domain in which the compact elements are the finite subsets of N.
Furthermore, the bottom element of D is the empty set ∅ and ∅ is also
the only minimal element of D; the top element of D is N and N is the
only maximal element of D.
Order and Logic
1.1.2 Proposition A partially ordered set (D, [) is a complete partial order
if and only if it has a bottom element and is chain complete.
Many aspects of theoretical computer science depend on the notion of
a partially ordered set. More structure is often required, however, than is
provided simply by a partial order or even by a complete partial order or
complete lattice. For example, one needs extra structure in order to model
standard programming language constructs or to provide an abstract theory of
computability, as well as having a satisfactory fixed-point theorem available. It
is now widely recognized that Scott’s theory of domains provides a satisfactory
setting in which to attain all these objectives, and we will find it useful later on
to view spaces of valuations as Scott domains. It will therefore be convenient
to give next the definition of the term “(Scott) domain” in the form in which
we will always use it. First, however, we need to define the notion of compact
element.
1.1.3 Definition Let (D [) be a partially ordered set. We call an element
a ∈ D compact or finite if it satisfies the property that whenever A is directed
and a [ A, we have a [ x for some x ∈ A. We denote the set of compact
elements in D by D c .
Notice that the bottom element in a complete partial order is always a
compact element, and hence the set D c is always non-empty in this case. The
compact elements are fundamental in domain theory.
1.1.4 Definition A Scott-Ershov domain, Scott domain, or just domain
(D, [) is a consistently complete algebraic complete partial order. Thus, the
following statements hold.
(1) (D, [) is a complete partial order.
(2) For each x ∈ D, the set approx(x) = {a ∈ D c | a [ x} is directed, and we
have x = approx(x) (the algebraicity of D).
(3) If the set
{a, b} ⊆ D c is consistent (that is, there exists x ∈ D such that
a [ x and b [ x), then {a, b} exists in D (the consistent completeness
of D).
We next give some simple examples of the concepts defined above; note
that (1) and (2) are special cases of Theorem 1.3.2.
1.1.5 Example (1) The power set D = P(N) of the set N of natural numbers
is a complete lattice when ordered by set inclusion. In this ordering, D is
also a domain in which the compact elements are the finite subsets of N.
Furthermore, the bottom element of D is the empty set ∅ and ∅ is also
the only minimal element of D; the top element of D is N and N is the
only maximal element of D.