Editing Complete partial order

{{Short description|Mathematical phrase}}
In [[mathematics]], the phrase '''complete partial order''' is variously used to refer to at least three similar, but distinct, classes of [[partially ordered set]]s, characterized by particular [[completeness (order theory)|completeness properties]]. Complete partial orders play a central role in [[theoretical computer science]]: in [[denotational semantics]] and [[domain theory]].

== 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"/>

== Examples ==

* Every finite poset is directed complete.
* All [[complete lattice]]s are also directed complete.
* For any poset, the set of all non-empty [[filter (mathematics)|filters]], ordered by [[inclusion (set theory)|subset inclusion]], is a dcpo. Together with the empty filter it is also pointed. If the order has binary [[join and meet|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 ⊥&nbsp;≤&nbsp;''s'' and s&nbsp;≤&nbsp;''s'' for every ''s'' in ''S'' and no other order relations.
* The set of all [[partial function]]s on some given set ''S'' can be ordered by defining ''f''&nbsp;≤&nbsp;''g'' if and only if ''g'' extends ''f'', i.e. if the [[domain of a function|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''&nbsp;≤&nbsp;''g'' if and only if ''f''&nbsp;⊆&nbsp;''g'' where ''f'' and ''g'' are identified with their respective [[graph of a function|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]] [[subset]]s of a [[vector space]] ''V'', ordered by [[inclusion (set theory)|inclusion]]. 
* The set of all partial [[choice function]]s on a collection of [[empty set|non-empty]] sets, ordered by restriction.
* The set of all [[prime ideal]]s of a [[ring (mathematics)|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 [[sentence (mathematical logic)|sentences]] closed under consequence (for defining notion of consequence, let us use e.g. [[Alfred Tarski]]'s algebraic approach<ref name=Tar-BizIg>Tarski, Alfred: Bizonyítás és igazság / Válogatott tanulmányok. Gondolat, Budapest, 1990. (Title means: Proof and truth / Selected papers.)</ref><ref name=BurSan-UnivAlg>[http://www.math.uwaterloo.ca/~snburris/index.html Stanley N. Burris] and H.P. Sankappanavar: [http://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html A Course in Universal Algebra]</ref>). There are interesting theorems that concern a set of deductive systems being a directed-complete partial ordering.<ref name=seqdcpo>See online in p. 24 exercises 5–6 of §5 in [https://www.math.uwaterloo.ca/~snburris/htdocs/UALG/univ-algebra.pdf]. Or, on paper, see [[#_note-Tar-BizIg|Tar:BizIg]].</ref> 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 ==

An ordered set is a dcpo if and only if every non-empty [[chain (order theory)|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 partial order|chain-complete]].<ref name="markowsky-1976"/><ref>
{{cite web
 | url = https://topology.lmf.cnrs.fr/iwamuras-lemma-kowalskys-theorem-and-ordinals/
 | title = Iwamura's Lemma, Markowsky's Theorem and ordinals
 | last = Goubault-Larrecq
 | first = Jean
 | date = February 23, 2015
 | access-date = January 6, 2024
}}</ref><ref>
{{cite book
 | last = Cohn
 |first = Paul Moritz
 | title = Universal Algebra
 | publisher = Harper and Row
 | page = 33
}}</ref><ref>
{{ cite web
 | url = https://topology.lmf.cnrs.fr/markowsky-or-cohn/
 | title = Markowsky or Cohn?
 | last = Goubault-Larrecq
 | first = Jean
 | date = January 28, 2018
 | access-date = January 6, 2024
}}</ref> Proofs rely on the [[axiom of choice]].

Alternatively, an ordered set <math>P</math> is a pointed dcpo if and only if every [[order-preserving]] self-map of <math>P</math> has a least [[fixpoint]].

== Continuous functions and fixed-points ==

A [[function (mathematics)|function]] ''f'' between two dcpos ''P'' and ''Q'' is called '''[[Scott continuity|(Scott) continuous]]''' if it maps directed sets to directed sets while preserving their suprema:
* <math>f(D) \subseteq Q</math> is directed for every directed <math>D \subseteq P</math>.
* <math>f(\sup D) = \sup f(D)</math> for every directed <math>D \subseteq P</math>.
Note that every continuous function between dcpos is a [[Monotone function#Monotonicity in order theory|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 <nowiki>[</nowiki>''P''&nbsp;→&nbsp;''Q''<nowiki>]</nowiki>. Equipped with the [[Pointwise#Pointwise relations|pointwise order]], this is again a dcpo, and pointed whenever ''Q'' is pointed.
Thus the complete partial orders with Scott-continuous maps form a [[cartesian closed category|cartesian closed]] [[category (mathematics)|category]].<ref name="barendregt1984">[[Henk Barendregt|Barendregt, Henk]], [http://www.elsevier.com/wps/find/bookdescription.cws_home/501727/description#description ''The lambda calculus, its syntax and semantics''] {{Webarchive|url=https://web.archive.org/web/20040823174002/http://www.elsevier.com/wps/find/bookdescription.cws_home/501727/description#description |date=2004-08-23 }}, [[North-Holland Publishing Company|North-Holland]] (1984)</ref>

Every order-preserving self-map ''f'' of a pointed dcpo (''P'', ⊥) has a least fixed-point.<ref>This is a strengthening of the [[Knaster–Tarski theorem]] sometimes referred to as "Pataraia’s theorem". For example, see Section 4.1 of [https://doi.org/10.4230/LIPIcs.TYPES.2016.6 "Realizability at Work: Separating Two Constructive Notions of Finiteness"] (2016) by Bezem et al.  See also Chapter 4 of ''The foundations of program verification'' (1987), 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, {{ISBN|0-471-91282-4}}, where the Knaster–Tarski theorem, formulated over pointed dcpo's, is given to prove as exercise 4.3-5 on page 90.</ref> If ''f'' is continuous then this fixed-point is equal to the supremum of the [[Iterated function|iterates]] (⊥, ''f''{{hairsp}}(⊥), ''f''{{hairsp}}(''f''{{hairsp}}(⊥)), … ''f''<sup>&thinsp;''n''</sup>(⊥), …) of ⊥ (see also the [[Kleene fixed-point theorem]]).

Another fixed point theorem is the [[Bourbaki–Witt theorem]], stating that if <math>f</math> is a function from a dcpo to itself with the property that <math>f(x) \geq x</math> for all <math>x</math>, then <math>f</math> 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.<ref>{{citation
 | last = Bourbaki | first = Nicolas | authorlink = Nicolas Bourbaki
 | journal = [[Archiv der Mathematik]]
 | mr = 0047739
 | pages = 434–437 (1951)
 | title = Sur le théorème de Zorn
 | volume = 2
 | year = 1949
 | issue = 6 | doi=10.1007/bf02036949| s2cid = 117826806 }}.</ref><ref>{{citation
 | last = Witt | first = Ernst | authorlink = Ernst Witt
 | journal = [[Mathematische Nachrichten]]
 | mr = 0039776
 | pages = 434–438
 | title = Beweisstudien zum Satz von M. Zorn
 | volume = 4
 | year = 1951
 | doi=10.1002/mana.3210040138}}.</ref>

== See also ==
* [[Algebraic poset]]s
* [[Scott topology]]
* [[completeness (order theory)|Completeness]]

== Notes ==

<references/>

== References ==
* {{cite book
 |author1=Davey, B.A. |author2-link = Hilary Priestley|author2=Priestley, H. A.
 | year = 2002
 | title = Introduction to Lattices and Order
 | title-link = Introduction to Lattices and Order
 | edition = Second
 | publisher = Cambridge University Press
 | isbn = 0-521-78451-4
}}

{{DEFAULTSORT:Complete Partial Order}}
[[Category:Order theory]]

[[ru:Частично упорядоченное множество#Полное частично упорядоченное множество]]