Editing Complete partial order (section)

== Definitions ==

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 set|directed subsets]] has a [[supremum]]. (A subset of a partial order is directed if it is [[empty set|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 <math>\bot</math>). 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 (ordered set)|chain]] has a supremum.

A related notion is that of '''ω-complete partial order''' ('''ω-cpo'''). These are posets in which every ω-chain (<math>x_1 \leq x_2 \leq x_3 \leq ...</math>) has a supremum that belongs to the poset. The same notion can be extended to other [[cardinality|cardinalities]] of chains. <ref name="markowsky-1976">
{{citation
 | last = Markowsky
 | first = George
 | issue = 1
 | journal = [[Algebra Universalis]]
 | mr = 0398913
 | pages = 53–68
 | title = Chain-complete posets and directed sets with applications
 | volume = 6
 | year = 1976
 | doi=10.1007/bf02485815
 | s2cid = 16718857
 }}
</ref>

Every dcpo is an ω-cpo, since every ω-chain is a directed set, but the [[converse (logic)|converse]] is not true. However, every ω-cpo with a [[domain theory#Bases of domains|basis]] is also a dcpo (with the same basis).<ref>{{Cite book|title=Handbook of Logic in Computer Science, volume 3|vauthors=[[Samson Abramsky|Abramsky S]], [[Dov Gabbay|Gabbay DM]], Maibaum TS|publisher=Clarendon Press|year=1994|isbn=9780198537625|location=Oxford|at=Prop 2.2.14, pp. 20}}</ref> 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 [[duality (order theory)|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.<ref name="markowsky-1976"/>