完全偏序

更新时间:2022-08-26 11:45

在数学中,有向完全偏序和完全偏序是两种特殊的偏序集合,分别简写为 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,并没有其他次序关系。

连续函数和不动点

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

是有向的,对有所有有向的 。

对于所有有向的 。

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

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

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

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

有关文章

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

例子

免责声明
隐私政策
用户协议
目录 22
0{{catalogNumber[index]}}. {{item.title}}
{{item.title}}