部分的な注文を完了する

数学において、 「完全部分順序」という用語は、少なくとも3つの類似しているが区別される部分順序集合のクラスを指すために様々に用いられ、それぞれ特定の完全性特性によって特徴付けられる。完全部分順序は、理論計算機科学、特に表示的意味論と領域理論において中心的な役割を果たす。

完全部分順序（略称cpo）という用語は、文脈によっていくつかの意味を持ち得る。

半順序集合は、その有向部分集合のそれぞれに上限が存在する場合、有向完全半順序（dcpo ）と呼ばれる。（半順序の部分集合は、空集合ではなく、かつその部分集合内のすべての要素のペアに上限が存在する場合に有向である。）文献では、dcpoは上完全半順序集合というラベルで表記されることもある。

ポインテッド有向完全半順序(ポインテッド dcpo、略してcppoとも呼ばれる) は、最小要素(通常は で表される)を持つ dcpo です。${\displaystyle \bot }$言い換えれば、有向DCPOは、すべての有向部分集合または空部分集合に対して上限を持ちます。有向DCPOはすべての鎖が上限を持つ半順序集合として特徴付けられるため、鎖完全半順序という用語も使用されます。

関連する概念として、ω完全半順序（ω-cpo）がある。これらは、すべてのω鎖（${\displaystyle x_{1}\leq x_{2}\leq x_{3}\leq ...}$) は、順序集合に属する上限を持つ。同じ概念は、他の濃度の連鎖にも拡張できる。^{[ 1 ]}

すべての dcpo は ω-cpo です。なぜなら、すべての ω-chain は有向集合だからです。しかし、その逆は真ではありません。ただし、基底を持つすべての ω-cpoは dcpo (同じ基底を持つ) でもあります。^{[ 2 ]}基底を持つ ω-cpo (dcpo) は、連続ω-cpo (または連続 dcpo)とも呼ばれます。

完全半順序という用語は、すべての部分集合が上限を持つ半順序集合を意味するために使われることは決してないことに注意してください。この概念には完全束という用語が使用されます。

有向上限の存在を要求する根拠は、有向集合を一般化された近似列とみなし、上限をそれぞれの（近似）計算の極限とみなすことにある。この直観は、表示的意味論の文脈において、領域理論の発展の動機となった。

有向完全半順序の双対概念は、フィルタ完全半順序と呼ばれます。しかし、双対順序を明示的に扱うことができる場合が多いため、この概念は実際にはあまり頻繁には現れません。

半順序集合のデデキント・マクニール完備化との類推により、すべての半順序集合は最小のdcpoに一意に拡張できる。^{[ 1 ]}

• すべての有限半順序集合は有向完全である。
• すべての完全格子は、有向完全でもある。
• 任意の半順序集合に対して、部分集合包含関係で順序付けられたすべての空でないフィルタの集合は、dcpo です。空フィルタとともに、それはまた、ポイント付きです。順序が二項交点を持つ場合、この構成 (空フィルタを含む) は実際には完全束を生成します。
• 任意の集合S は、最小要素 ⊥ を追加し、Sのすべてのs に対して ⊥ ≤ sおよび s ≤ sを満たすフラットな順序を導入し、他の順序関係を導入しないことで、ポインテッド dcpo に変換できます。   
• 与えられた集合S上のすべての部分関数の集合は、f ≤ gがgを拡張する場合、すなわちfの定義域がgの定義域の部分集合であり、 fとgの値が両方とも定義されているすべての入力で一致する場合に限り、と定義することによって順序付けできます。（同等に、f ≤ gが f ⊆ gの場合に限り、 f ⊆ gであり、fとgはそれぞれのグラフと同一視されます。）この順序は、最小要素がどこにも定義されていない部分関数（定義域が空）であるような、点付き dcpo です。実際、≤ は有界完備でもあります。この例は、最大要素を持つことが必ずしも自然ではない理由も示しています。      
• ベクトル空間Vのすべての線形独立な部分集合の集合で、包含関係によって順序付けられている。
• 空でない集合の集合上のすべての部分選択関数の集合を、制限によって順序付けしたもの。
• 環のすべての素イデアルの集合を、包含関係によって順序付けしたもの。
• 禁酒スペースの専門化順序はdcpoである。
• 「演繹システム」という用語を、帰結に関して閉じている文の集合として用いることにしよう（帰結の概念を定義するために、例えばアルフレッド・タルスキの代数的アプローチ^{[ 3 ] [ 4 ]}を用いる）。演繹システムの集合が有向完全半順序であることに関する興味深い定理がある。^{[ 5 ] [ 3 ]}また、演繹システムの集合は、最小要素を自然な方法で持つように選択することができる（したがって、それは有向完全半順序にもなり得る）。なぜなら、空集合のすべての帰結の集合（すなわち、「論理的に証明可能/論理的に妥当な文の集合」）は、（1）演繹システムであり、（2）すべての演繹システムに含まれるからである。

（マルコフスキーの定理）順序付き集合がdcpoであるのは、それが鎖完全である場合、すなわち、すべての空でない鎖が上限を持つ場合のみです。

その結果として、順序付き集合が有向dcpoであるのは、すべての（空の場合もある）鎖が上限を持つ場合、すなわち、それが鎖完全である場合に限る。^{[ 1 ] [ 6 ] [ 7 ] [ 8 ]}証明は選択公理に基づいている。

あるいは、順序付き集合${\displaystyle P}$は、すべての順序保存自己写像がである場合に限り、有向 dcpo である。${\displaystyle P}$最小不動点を持つ。

2つのdcpos PとQの間の関数fは 、有向集合を有向集合に写像しつつ、それらの上限を保持する場合に（スコット）連続と呼ばれる。

• ${\displaystyle f(D)\subseteq Q}$すべての指示に対して指示されています${\displaystyle D\subseteq P}$。
• ${\displaystyle f(\sup D)=\sup f(D)}$すべての方向${\displaystyle D\subseteq P}$。

dcpos間の連続関数はすべて単調関数であることに注意してください。この連続性の概念は、スコット位相によって誘導される位相的連続性と同等です。

2 つの dcpo PとQの間のすべての連続関数の集合は[ P  → Q ]と表記される。点ごとの順序が備わっているため、これもまた dcpo であり、Qが指されているときはいつでも指されている。したがって、スコット連続写像を持つ完全な半順序は、デカルト閉圏を形成する。^{[ 9 ]} 

点付きdcpo( P , ⊥)の順序保存自己写像fには最小不動点が存在する。^{[ 10 ]} fが連続である場合、この不動点は⊥の反復(⊥, f (⊥), f ( f (⊥)), ... fn ⁽ ⊥), ...)の上限に等しい（クリーネの不動点定理も参照）。

もう一つの不動点定理はブルバキ・ウィットの定理で、もし${\displaystyle f}$これは、以下の特性を持つ、dcpo からそれ自身への関数です。${\displaystyle f(x)\geq x}$すべての人々のために${\displaystyle x}$、 それから${\displaystyle f}$不動点を持つ。この定理は、ゾルンの補題が選択公理の結果であることを証明するために使用できる。^{[ 11 ] [ 12 ]}

• 代数的半順序集合
• スコット位相
• 完全
• マルコフスキーの定理

• Davey, BA; Priestley, HA (2002).格子と秩序入門（第2 版）. Cambridge University Press. ISBN 0-521-78451-4。