完全偏序

在數學中，有向完全偏序和完全偏序是兩種特殊的偏序集合，分別簡寫為 dcpo 和 cpo。它們特徵化自特定的完備性性質。dcpos 和 cpos 是序理論的概念，主要套用於理論計算機科學和指稱語義。

基本介紹

• 中文名：完全偏序
• 外文名：Complete partial order
• 分類：數理科學

定義

一個偏序集合是有向完全偏序(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連續性的。

例子

• 對於任何偏序集合，所有非空濾子的集合，用子集包含排序，是 dcpo，甚至是 cpo 如果這個偏序集合有最大元素。與空濾子在一起它也保證是 cpo。如果次序是交半格(甚至是格)，則這個構造(包括空濾子)實際上生成一個完全格。
• 考慮在某個集合S上所有偏函式的集合，偏函式是只在(它的域)S的某些子集上有定義的函式。對於兩個這種函式f和g，定義f≤g若且唯若，f的域是g的域的子集，並且f和g的值在對兩個函式都有定義的所有輸出上一致。在這種情況下，我們稱g擴展了f。這個次序是 cpo，這裡的最小元素是無處定義函式(有空域)。事實上，≤ 也是有界完全性的。這個例子還展示了為什麼不總是自然的有一個最大元素。
• sober空間的特殊化次序是 dcpo。
• 所有有限偏序集合都是有向完全的，所有帶有最小元素的有限偏序集合都是 cpo。
• 所有完全格都是有向完全的並因此為 dcpos 提供了眾多例子。