在数学中,有向完全偏序和完全偏序是两种特殊的
偏序集合,分别简写为 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,并没有其他次序关系。
在 cpos 之间的所有连续函数是序保持的但反之不然。所有 cpo (P, ⊥) 的序保持的自映射f有最小不动点。如果f是连续的,则这个不动点等于 ⊥ 的
迭代(⊥,f(⊥),f(f(⊥)), …f(⊥), …) 的上确界。
有向完全性以各种方式关联于其他完备性概念。这在
完全性 (序理论)中讨论。有向完全性自身在其他序理论研究中是经常出现的非常基本的性质。例如,涉及有向完全性的定理可以在连续偏序集合、代数偏序集合和Scott拓扑文章中讨论。在 dcpos 之间的函数经常要求是单调的甚至是Scott连续性的。