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.

A complete partial order abbreviated cpo can, depending on context, refer to any of the following concepts.

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 poset 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.

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:

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(⊥)), … fn(⊥), …) 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.