完全偏序

维基百科，自由的百科全书

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

[编辑] 定义

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

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

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

[编辑] 性质和有关文章

有向完全性以各种方式关联于其他完备性概念。这在完备性 (序理论)中讨论。有向完全性自身在其他序理论研究中是经常出现的非常基本的性质。例如，涉及有向完全性的定理可以在连续偏序集合、代数偏序集合和Scott拓扑文章中讨论。在 dcpos 之间的函数经常要求是单调的甚至是Scott连续性的。

[编辑] 例子

对于任何偏序集合，所有非空滤子的集合，用子集包含排序，是 dcpo，甚至是 cpo 如果这个偏序集合有最大元素。与空滤子在一起它也保证是 cpo。如果次序是交半格(甚至是格)，则这个构造(包括空滤子)实际上生成一个完全格。

考虑在某个集合 S 上所有偏函数的集合，偏函数是只在(它的域) S 的某些子集上有定义的函数。对于两个这种函数 f 和 g，定义 f ≤ g 当且仅当，f 的域是 g 的域的子集，并且 f 和 g 的值在对两个函数都有定义的所有输出上一致。在这种情况下，我们称 g 扩展了 f。这个次序是 cpo，这里的最小元素是无处定义函数(有空域)。事实上，≤ 也是有界完全性的。这个例子还展示了为什么不总是自然的有一个最大元素。