[科普中國]-完全偏序

在數(shù)學(xué)中，有向完全偏序和完全偏序是兩種特殊的偏序集合，分別簡寫為 dcpo 和 cpo。它們特征化自特定的完備性性質(zhì)。dcpos 和 cpos 是序理論的概念，主要應(yīng)用于理論計算機科學(xué)和指稱語義。

定義一個偏序集合是有向完全偏序(dcpo)，如果它的每個有向子集都有上確界。完全偏序(cpo)是帶有最小元素的 dcpo。在文獻(xiàn)中，dcpos 有時分類為sup-完全偏序集合，或在不會造成歧義的情況下簡稱為“cpo”。帶有最小元素的 dcpo 有時叫做尖角(pointed) dcpo 或尖角 cpo。

要求有向上確界的存在的動機來自把有向集合看作一般化的逼近序列，把上確界看作各自(逼近)計算的極限。關(guān)于在指稱語義的上下文中這種直覺的詳情請參見域理論。

有向完全偏序集合的對偶概念叫做過濾完全偏序。但是這個概念在實踐中不常用，因為通?？梢悦鞔_地在這個對偶的次序上工作1。

性質(zhì)有序集合P是 cpo，當(dāng)且僅當(dāng)所有全序子集都有在P中的上確界?？勺鳛樘娲行蚣螾是 cpo，當(dāng)且僅當(dāng)所有P的序保持自映射都有最小不動點。所有集合S都可以變成 cpo，通過增加一個最小元素 ⊥ 并介入一個平坦次序，帶有 ⊥≤s對于所有s∈S，并沒有其他次序關(guān)系。

連續(xù)函數(shù)和不動點在兩個 dcposP和Q之間的函數(shù)f被稱為連續(xù)的，如果它把有向集合映射到有向集合，并保持它們的上確界:

是有向的，對有所有有向的 。

對于所有有向的 。

在兩個 cpos (P, ⊥P) 和 (Q, ⊥Q) 之間的函數(shù)f被稱為是連續(xù)的，如果它進一步保持最小元素:

這種連續(xù)性的概念等價于Scott拓?fù)湟l(fā)的概念。

在兩個 dcposP和Q之間的所有連續(xù)函數(shù)的集合被指示為 [P→Q]。配備了逐點(pointwise)次序，這是 dcpo，并是 cpo 只要Q是 cpo。

在 cpos 之間的所有連續(xù)函數(shù)是序保持的但反之不然。所有 cpo (P, ⊥) 的序保持的自映射f有最小不動點。如果f是連續(xù)的，則這個不動點等于 ⊥ 的迭代(⊥,f(⊥),f(f(⊥)), …f(⊥), …) 的上確界。

有關(guān)文章有向完全性以各種方式關(guān)聯(lián)于其他完備性概念。這在完全性 (序理論)中討論。有向完全性自身在其他序理論研究中是經(jīng)常出現(xiàn)的非?；镜男再|(zhì)。例如，涉及有向完全性的定理可以在連續(xù)偏序集合、代數(shù)偏序集合和Scott拓?fù)湮恼轮杏懻?。?dcpos 之間的函數(shù)經(jīng)常要求是單調(diào)的甚至是Scott連續(xù)性的2。

例子對于任何偏序集合，所有非空濾子的集合，用子集包含排序，是 dcpo，甚至是 cpo 如果這個偏序集合有最大元素。與空濾子在一起它也保證是 cpo。如果次序是交半格(甚至是格)，則這個構(gòu)造(包括空濾子)實際上生成一個完全格。

考慮在某個集合S上所有偏函數(shù)的集合，偏函數(shù)是只在(它的域)S的某些子集上有定義的函數(shù)。對于兩個這種函數(shù)f和g，定義f≤g當(dāng)且僅當(dāng)，f的域是g的域的子集，并且f和g的值在對兩個函數(shù)都有定義的所有輸出上一致。在這種情況下，我們稱g擴展了f。這個次序是 cpo，這里的最小元素是無處定義函數(shù)(有空域)。事實上，≤ 也是有界完全性的。這個例子還展示了為什么不總是自然的有一個最大元素。

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

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

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

本詞條內(nèi)容貢獻(xiàn)者為:

胡建平 - 副教授 - 西北工業(yè)大學(xué)