Complete partial order
From Wikipedia, the free encyclopedia
In mathematics, directed complete partial orders and complete partial orders are special classes of partially ordered sets. These orders, called dcpos and cpos for short, are characterized by particular completeness properties. Both dcpos and cpos are considered in domain theory and have major applications in theoretical computer science and denotational semantics.
Contents |
[edit] Definition
A partially ordered set is a directed complete partial order (dcpo), if each of its directed subsets has a supremum. A complete partial order (cpo) is a dcpo with a least element. In the literature, dcpos sometimes also appear under the label up-complete poset or, confusingly, simply "cpo". A dcpo with a least element is sometimes called a pointed dcpo or a pointed cpo.
Requiring the existence of directed suprema can be motivated by viewing directed sets as generalized approximation sequences and suprema as limits of the respective (approximative) computations. Details on this intuition in the context of denotational semantics are to be found in the introductory article on domain theory.
The dual notion of a directed complete poset is called a filtered complete partial order. However, this concept occurs far less frequently in practice, since one usually can work on the dual order explicitly.
[edit] Properties and related articles
Directed completeness relates in various ways to other completeness notions. This is documented in the article on completeness (order theory). Directed completeness alone is quite a basic property that occurs often in other order theoretic investigations. For instance, theorems involving directed completeness (and characterizations thereof) are to be found in the articles on continuous posets, algebraic posets, and the Scott topology. Functions between dcpos are often required to be monotone or even Scott continuous.
[edit] Examples
- For any poset, the set of all non-empty filters, ordered by subset inclusion, is a dcpo, even a cpo if the poset has a greatest element. Together with the empty filter it is also guaranteed to be a cpo. If the order is a meet-semilattice (or even a lattice), then this construction (including the empty filter) actually yields a complete lattice.
- Consider the set of all partial functions on some set S, i.e. functions defined only on some subset (its domain) of S. For two such functions f and g, define f ≤ g iff the domain of f is a subset of the domain of g and the values of f and g agree on all inputs for which both functions are defined. In this case, we say that g extends f. This order is a cpo, where the least element is the nowhere defined function (with empty domain). In fact, ≤ is also bounded complete. This example also demonstrates why it is not always natural to have a greatest element.
- The specialization order of any sober space is a dcpo.
- Every finite poset is directed complete, every finite poset with a least element is a cpo.
- All complete lattices are of course also directed complete and thus provide numerous (though not particularly instructive) examples for dcpos.
- Let use term “deductive system” as a set of sentences closed under consequence (for defining notion of consequence, let us use e.g. Tarski's algebraic approach [1] [2]). There are interesting theorems which concern a set of deductive systems being a directed complete partial ordering [3]. Also, a set of deductive systems can be chosen to have a least element in a natural way (so that it can be also a complete partial ordering), because the set of all conseqences of the empty set (i.e. “the set of the logically provable / logically valid sentences”) is (1) a deductive system (2) contained by all deductive systems.
[edit] Notes
- ^ Tarski, Alfred: Bizonyítás és igazság / Válogatott tanulmányok. Gondolat, Budapest, 1990. (Title means: Proof and truth / Selected papers.)
- ^ Stanley N. Burris and H.P. Sankappanavar: A Course in Universal Algebra
- ^ See online in p. 24 exercises 5–6 of §5 in BurSan:UnivAlg. Or, on paper, see Tar:BizIg.
