完全偏序

在数学中，有向完全偏序和完全偏序是特殊种类的偏序集合。分别简写为 dcpo 和 cpo，它们特征化自特定特定完备性性质。dcpos 和 cpos 在序理论中考虑并主要应用于理论计算机科学和指称语义。

定义

一个偏序集合是有向完全偏序(dcpo)，如果它的每个有向子集都有上确界。完全偏序(cpo)是带有最小元素的 dcpo。在文献中，dcpos 有时分类为 sup-完全偏序集合，或混淆为“cpo”。带有最小元素的 dcpo 有时叫做尖角(pointed) dcpo 或尖角 cpo。

要求有向上确界的存在可能推动自把有向集合看作一般化的逼近序列把上确界看作各自(逼近)计算的极限。关于在指称语义的上下文中这种直觉的详情请参见域理论。

有向完全偏序集合的对偶概念叫做过滤完全偏序。但是这个概念在实践中不常用，因为你通常可以明确的在这个对偶的次序上工作。

性质和有关文章

Directed completeness relates in various ways to other completeness notions. This is documented in the article on completeness (order theory). Directed completeness alone is quite a basic property that occurs often in other order theoretic investigations. For instance, theorems involving directed completeness (and characterizations thereof) are to be found in the articles on continuous posets, algebraic posets, and the Scott topology. Functions between dcpos are often required to be monotone or even Scott continuous.

例子

• For any poset, the set of all non-empty filters, ordered by subset inclusion, is a dcpo, even a cpo if the poset has a greatest element. Together with the empty filter it is also guaranteed to be a cpo. If the order is a meet-semilattice (or even a lattice), then this construction (including the empty filter) actually yields a complete lattice.

• Consider the set of all partial functions on some set S, i.e. functions defined only on some subset (its domain) of S. For two such functions f and g, define f ≤ g iff 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 both functions are defined. In this case, we say that g extends f. This order is a cpo, where the least element is the nowhere defined 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.

• Every finite poset is directed complete, every finite poset with a least element is a cpo.

• All complete lattices are of course also directed complete and thus provide numerous (though not particularly instructive) examples for dcpos.