# Complete partial order

In mathematics, the phrase **complete partial order** is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central role in theoretical computer science: in denotational semantics and domain theory.

## Definitions

[edit]The term **complete partial order**, abbreviated **cpo**, has several possible meanings depending on context.

A partially ordered set is a **directed-complete partial order** (**dcpo**) if each of its directed subsets has a supremum. (A subset of a partial order is directed if it is non-empty and every pair of elements has an upper bound in the subset.) In the literature, dcpos sometimes also appear under the label **up-complete poset**.

A **pointed directed-complete partial order** (**pointed dcpo**, sometimes abbreviated **cppo**), is a dcpo with a least element (usually denoted ). Formulated differently, a pointed dcpo has a supremum for every directed *or empty* subset. The term **chain-complete partial order** is also used, because of the characterization of pointed dcpos as posets in which every chain has a supremum.

A related notion is that of **ω-complete partial order** (**ω-cpo**). These are posets in which every ω-chain () has a supremum that belongs to the poset. The same notion can be extended to other cardinalities of chains. ^{[1]}

Every dcpo is an ω-cpo, since every ω-chain is a directed set, but the converse is not true. However, every ω-cpo with a basis is also a dcpo (with the same basis).^{[2]} An ω-cpo (dcpo) with a basis is also called a **continuous** ω-cpo (or continuous dcpo).

Note that *complete partial order* is never used to mean a poset in which *all* subsets have suprema; the terminology complete lattice is used for this concept.

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. This intuition, in the context of denotational semantics, was the motivation behind the development of domain theory.

The dual notion of a directed-complete partial order 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.

By analogy with the Dedekind–MacNeille completion of a partially ordered set, every partially ordered set can be extended uniquely to a minimal dcpo.^{[1]}

## Examples

[edit]- Every finite poset is directed complete.
- All complete lattices are also directed complete.
- For any poset, the set of all non-empty filters, ordered by subset inclusion, is a dcpo. Together with the empty filter it is also pointed. If the order has binary meets, then this construction (including the empty filter) actually yields a complete lattice.
- Every set
*S*can be turned into a pointed dcpo by adding a least element ⊥ and introducing a flat order with ⊥ ≤*s*and s ≤*s*for every*s*in*S*and no other order relations. - The set of all partial functions on some given set
*S*can be ordered by defining*f*≤*g*if and only if*g*extends*f*, i.e. if 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 they are both defined. (Equivalently,*f*≤*g*if and only if*f*⊆*g*where*f*and*g*are identified with their respective graphs.) This order is a pointed dcpo, where the least element is the nowhere-defined partial 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 set of all linearly independent subsets of a vector space
*V*, ordered by inclusion. - The set of all partial choice functions on a collection of non-empty sets, ordered by restriction.
- The set of all prime ideals of a ring, ordered by inclusion.
- The specialization order of any sober space is a dcpo.
- Let us use the term “deductive system” as a set of sentences closed under consequence (for defining notion of consequence, let us use e.g. Alfred Tarski's algebraic approach
^{[3]}^{[4]}). There are interesting theorems that concern a set of deductive systems being a directed-complete partial ordering.^{[5]}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 pointed dcpo), because the set of all consequences 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.

## Characterizations

[edit]An ordered set is a dcpo if and only if every non-empty chain has a supremum. As a corollary, an ordered set is a pointed dcpo if and only if every (possibly empty) chain has a supremum, i.e., if and only if it is chain-complete.^{[1]}^{[6]}^{[7]}^{[8]} Proofs rely on the axiom of choice.

Alternatively, an ordered set is a pointed dcpo if and only if every order-preserving self-map of has a least fixpoint.

## Continuous functions and fixed-points

[edit]A function *f* between two dcpos *P* and *Q* is called **(Scott) continuous** if it maps directed sets to directed sets while preserving their suprema:

- is directed for every directed .
- for every directed .

Note that every continuous function between dcpos is a monotone function. This notion of continuity is equivalent to the topological continuity induced by the Scott topology.

The set of all continuous functions between two dcpos *P* and *Q* is denoted [*P* → *Q*]. Equipped with the pointwise order, this is again a dcpo, and a cpo whenever *Q* is a cpo.
Thus the complete partial orders with Scott-continuous maps form a cartesian closed category.^{[9]}

Every order-preserving self-map *f* of a cpo (*P*, ⊥) has a least fixed-point.^{[10]} If *f* is continuous then this fixed-point is equal to the supremum of the iterates (⊥, *f* (⊥), *f* (*f* (⊥)), … *f*^{ n}(⊥), …) of ⊥ (see also the Kleene fixed-point theorem).

Another fixed point theorem is the Bourbaki-Witt theorem, stating that if is a function from a dcpo to itself with the property that for all , then has a fixed point. This theorem, in turn, can be used to prove that Zorn's lemma is a consequence of the axiom of choice.^{[11]}^{[12]}

## See also

[edit]Directed completeness alone is quite a basic property that occurs often in other order-theoretic investigations, using for instance algebraic posets and the Scott topology.

Directed completeness relates in various ways to other completeness notions such as chain completeness.

## Notes

[edit]- ^
^{a}^{b}^{c}Markowsky, George (1976), "Chain-complete posets and directed sets with applications",*Algebra Universalis*,**6**(1): 53–68, doi:10.1007/bf02485815, MR 0398913, S2CID 16718857 **^**Abramsky S, Gabbay DM, Maibaum TS (1994).*Handbook of Logic in Computer Science, volume 3*. Oxford: Clarendon Press. Prop 2.2.14, pp. 20. ISBN 9780198537625.**^**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 [1]. Or, on paper, see Tar:BizIg.**^**Goubault-Larrecq, Jean (February 23, 2015). "Iwamura's Lemma, Markowsky's Theorem and ordinals". Retrieved January 6, 2024.**^**Cohn, Paul Moritz.*Universal Algebra*. Harper and Row. p. 33.**^**Goubault-Larrecq, Jean (January 28, 2018). "Markowsky or Cohn?". Retrieved January 6, 2024.**^**Barendregt, Henk,*The lambda calculus, its syntax and semantics*Archived 2004-08-23 at the Wayback Machine, North-Holland (1984)**^**See Knaster–Tarski theorem; The foundations of program verification, 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, ISBN 0-471-91282-4, Chapter 4; the Knaster–Tarski theorem, formulated over cpo's, is given to prove as exercise 4.3-5 on page 90.**^**Bourbaki, Nicolas (1949), "Sur le théorème de Zorn",*Archiv der Mathematik*,**2**(6): 434–437 (1951), doi:10.1007/bf02036949, MR 0047739, S2CID 117826806.**^**Witt, Ernst (1951), "Beweisstudien zum Satz von M. Zorn",*Mathematische Nachrichten*,**4**: 434–438, doi:10.1002/mana.3210040138, MR 0039776.

## References

[edit]- Davey, B.A.; Priestley, H. A. (2002).
*Introduction to Lattices and Order*(Second ed.). Cambridge University Press. ISBN 0-521-78451-4.