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.

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. f(\sup D) = \sup f(D) for every directed 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 pointed whenever Q is pointed. Thus the complete partial orders with Scott-continuous maps form a cartesian closed category. Every order-preserving self-map f of a pointed dcpo (P, ⊥) has a least fixed-point. If f is continuous then this fixed-point is equal to the supremum of the iterates (⊥, f (⊥), f (f (⊥)), ... f n (⊥), ...) of ⊥ (see also the Kleene fixed-point theorem). Another fixed point theorem is the Bourbaki–Witt theorem, stating that if f is a function from a dcpo to itself with the property that f(x) \geq x for all x , then f 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1350660906 under CC BY-SA 4.0; modifications have been made.