Inmathematics, the phrasecomplete partial order is variously used to refer to at least three similar, but distinct, classes ofpartially ordered sets, characterized by particularcompleteness properties. Complete partial orders play a central role intheoretical computer science: indenotational semantics anddomain theory.

The termcomplete partial order, abbreviatedcpo, has several possible meanings depending on context.

A partially ordered set is adirected-complete partial order (dcpo) if each of itsdirected subsets has asupremum. (A subset of a partial order is directed if it isnon-empty and every pair of elements has an upper bound in the subset.) In the literature, dcpos sometimes also appear under the labelup-complete poset.

Apointed directed-complete partial order (pointed dcpo, sometimes abbreviatedcppo), is a dcpo with aleast element (usually denoted${\displaystyle \mathrm{\perp }}$). Formulated differently, a pointed dcpo has a supremum for every directedor empty subset. The termchain-complete partial order is also used, because of the characterization of pointed dcpos as posets in which everychain has a supremum.

A related notion is that ofω-complete partial order (ω-cpo). These are posets in which every ω-chain (${\displaystyle x_1\le x_2\le x_3\le ...}$) has a supremum that belongs to the poset. The same notion can be extended to othercardinalities of chains.^[1]

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

Note thatcomplete partial order is never used to mean a poset in whichall subsets have suprema; the terminologycomplete 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 aslimits of the respective (approximative) computations. This intuition, in the context of denotational semantics, was the motivation behind the development ofdomain theory.

Thedual notion of a directed-complete partial order is called afiltered-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 theDedekind–MacNeille completion of a partially ordered set, every partially ordered set can be extended uniquely to a minimal dcpo.^[1]

• Every finite poset is directed complete.
• Allcomplete lattices are also directed complete.
• For any poset, the set of all non-emptyfilters, ordered bysubset inclusion, is a dcpo. Together with the empty filter it is also pointed. If the order has binarymeets, then this construction (including the empty filter) actually yields acomplete lattice.
• Every setS can be turned into a pointed dcpo by adding a least element ⊥ and introducing a flat order with ⊥ ≤ s and s ≤ s for everys inS and no other order relations.
• The set of allpartial functions on some given setS can be ordered by definingf ≤ g if and only ifg extendsf, i.e. if thedomain off is a subset of the domain ofg and the values off andg agree on all inputs for which they are both defined. (Equivalently,f ≤ g if and only iff ⊆ g wheref andg are identified with their respectivegraphs.) This order is a pointed dcpo, where the least element is the nowhere-defined partial function (with empty domain). In fact, ≤ is alsobounded complete. This example also demonstrates why it is not always natural to have a greatest element.
• The set of alllinearly independentsubsets of avector spaceV, ordered byinclusion.
• The set of all partialchoice functions on a collection ofnon-empty sets, ordered by restriction.
• The set of allprime ideals of aring, ordered by inclusion.
• Thespecialization order of anysober space is a dcpo.
• Let us use the term "deductive system" as a set ofsentences 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][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 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.

An ordered set is a dcpo if and only if every non-emptychain 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 ischain-complete.^[1][6][7][8] Proofs rely on theaxiom of choice.

Alternatively, an ordered set${\displaystyle P}$ is a pointed dcpo if and only if everyorder-preserving self-map of${\displaystyle P}$ has a leastfixpoint.

Afunctionf between two dcposP andQ is called(Scott) continuous if it maps directed sets to directed sets while preserving their suprema:

• ${\displaystyle f(D)\subseteq Q}$ is directed for every directed${\displaystyle D\subseteq P}$.
• ${\displaystyle f(supD)=supf(D)}$ for every directed${\displaystyle D\subseteq P}$.

Note that every continuous function between dcpos is amonotone function. This notion of continuity is equivalent to thetopological continuity induced by theScott topology.

The set of all continuous functions between two dcposP andQ is denoted [P → Q]. Equipped with thepointwise order, this is again a dcpo, and pointed wheneverQ is pointed.Thus the complete partial orders with Scott-continuous maps form acartesian closedcategory.^[9]

Every order-preserving self-mapf of a pointed dcpo (P, ⊥) has a least fixed-point.^[10] Iff is continuous then this fixed-point is equal to the supremum of theiterates (⊥,f (⊥),f (f (⊥)), ...f ⁿ(⊥), ...) of ⊥ (see also theKleene fixed-point theorem).

Another fixed point theorem is theBourbaki–Witt theorem, stating that if${\displaystyle f}$ is a function from a dcpo to itself with the property that${\displaystyle f(x)\ge x}$ for all${\displaystyle x}$, then${\displaystyle f}$ has a fixed point. This theorem, in turn, can be used to prove thatZorn's lemma is a consequence of the axiom of choice.^[11][12]

• Algebraic posets
• Scott topology
• Completeness

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

• Order theory

• Webarchive template wayback links
• Articles with short description
• Short description is different from Wikidata