完全偏序

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

定义

一个偏序集合是有向完全偏序(dcpo)，如果它的每个有向子集都有上确界。完全偏序(cpo)是带有最小元素的 dcpo。在文献中，dcpos 有时分类为 sup-完全偏序集合，或在不会造成歧义的情况下简称为“cpo”。带有最小元素的 dcpo 有时叫做尖角(pointed) dcpo 或尖角 cpo。

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

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

性质

有序集合 P 是 cpo，当且仅当所有全序子集都有在 P 中的上确界。可作为替代，有序集合 P 是 cpo，当且仅当所有 P 的序保持自映射都有最小不动点。所有集合 S 都可以变成 cpo，通过增加一个最小元素 ⊥ 并介入一个平坦次序，带有 ⊥ ≤ s 对于所有 s ∈ S，并没有其他次序关系。

连续函数和不动点

在两个 dcpos P 和 Q 之间的函数 f 被称为连续的，如果它把有向集合映射到有向集合，并保持它们的上确界:

$f(D)\subseteq Q$ 是有向的，对有所有有向的 $D\subseteq P$ 。
$f(\sup D)=\sup f(D)$ 对于所有有向的 $D\subseteq P$ 。

在两个 cpos (P, ⊥_P) 和 (Q, ⊥_Q) 之间的函数 f 被称为是连续的，如果它进一步保持最小元素:

$f(\bot _{P})=\bot _{Q}$

这种连续性的概念等价于Scott拓扑引发的概念。

在两个 dcpos P 和 Q 之间的所有连续函数的集合被指示为 [P → Q]。配备了逐点(pointwise)次序，这是 dcpo，并是 cpo 只要 Q 是 cpo。

在 cpos 之间的所有连续函数是序保持的但反之不然。所有 cpo (P, ⊥) 的序保持的自映射 f 有最小不动点。如果 f 是连续的，则这个不动点等于 ⊥ 的迭代 (⊥, f(⊥), f(f(⊥)), … fⁿ(⊥), …) 的上确界。

有关文章

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

例子

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

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

sober空间的特殊化次序是 dcpo。

所有有限偏序集合都是有向完全的，所有带有最小元素的有限偏序集合都是 cpo。

所有完全格都是有向完全的并因此为 dcpos 提供了众多例子。

引用

Davey, B.A., and Priestley, H. A. Introduction to Lattices and Order Second Edition. Cambridge University Press. 2002. ISBN 978-0-521-78451-1.