Complete partial order

A complete partial order, abbreviated cpo, can refer to any of the following concepts 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 partially ordered set is a pointed directed-complete partial order if it is a dcpo with a least element. They are sometimes abbreviated cppos.

• A partially ordered set is a ω-complete partial order (ω-cpo) if it is a poset in which every ω-chain (x₁ ≤ x₂ ≤ x₃ ≤ x₄ ≤ ...) has a supremum that belongs to the poset. 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).[1] An ω-cpo (dcpo) with a basis is also called a continuous ω-cpo (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.

• 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 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[2][3]). There are interesting theorems that concern a set of deductive systems being a directed-complete partial ordering.[4] 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 P is a pointed dcpo if and only if every chain has a supremum in P, i.e., P is chain-complete.[5] Alternatively, an ordered set P is a pointed dcpo if and only if every order-preserving self-map of P has a least fixpoint.

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:

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

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.[6]

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

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.

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