ドメイン理論

前述の通り、ドメイン理論は、計算領域をモデル化するために、部分的に順序付けられた集合を扱います。その目的は、そのような順序の要素を情報の一部、あるいは計算の（部分的な）結果として解釈することであり、順序の上位にある要素は、下位にある要素の情報を一貫した方法で拡張します。この単純な直感から、ドメインには最大の要素が存在しないことが多いことは明らかです。なぜなら、最大の要素が存在するということは、他のすべての要素の情報を含む要素が存在することを意味し、それはあまり面白くない状況だからです。

この理論において重要な役割を果たす概念の一つに、ドメインの有向部分集合があります。有向部分集合とは、ある順序の空でない部分集合であり、任意の2つの要素の上限がこの部分集合の要素であるような集合です。ドメインに関する私たちの直感からすると、これは有向部分集合内の任意の2つの情報が、その部分集合内の他の要素によって一貫して拡張されることを意味します。したがって、有向部分集合は一貫性のある仕様、つまり2つの要素が矛盾しない部分結果の集合と見なすことができます。この解釈は、解析学における収束列の概念と比較できます。収束列では、各要素が前の要素よりも具体的です。実際、距離空間の理論では、列はドメイン理論における有向集合の役割と多くの点で類似した役割を果たします。

さて、数列の場合と同様に、ここでは有向集合の極限に関心があります。前述の通り、これは有向集合のすべての要素の情報を拡張する最も一般的な情報、つまり有向集合に存在していた情報のみを含む唯一の要素となります。順序理論の形式化では、これは有向集合の最小上界に相当します。数列の極限の場合と同様に、有向集合の最小上界は必ずしも存在するとは限りません。

当然ながら、すべての整合性のある仕様が収束する計算領域、すなわちすべての有向集合が最小上界を持つ順序には特別な関心が寄せられる。この性質は、有向完全部分順序（略してdcpo）のクラスを定義する。実際、領域理論のほとんどの考察では、少なくとも有向完全である順序のみが考慮される。

部分的に指定された結果を不完全な知識を表すものと捉えるという根本的な考え方から、もう一つの望ましい性質、すなわち最小要素の存在が導き出される。このような要素は、情報が全くない状態、つまりほとんどの計算が始まる場所をモデル化する。また、結果を全く返さない計算の出力とみなすこともできる。

計算領域がどのようなものであるべきかについて基本的な形式的記述ができたので、今度は計算そのものについて考えてみましょう。明らかに、これらは関数でなければならず、何らかの計算領域から入力を受け取り、何らかの（場合によっては異なる）領域で出力を返します。しかし、入力の情報量が増加すると、関数の出力にもより多くの情報が含まれることが期待されます。形式的には、これは関数が単調である必要があることを意味します。

dcposを扱う場合、有向集合の極限の形成と計算が互換性を持つようにしたい場合もある。形式的には、これは、ある関数fに対して、有向集合Dの像f ( D ) (つまり、 Dの各要素の像の集合) が再び有向であり、 Dの最小上界の像を最小上界として持つことを意味する。また、 f は有向上限を保持するとも言える。さらに、2 つの要素からなる有向集合を考えると、このような関数は単調でなければならないことにも注意する。これらの性質から、スコット連続関数の概念が生じる。これは多くの場合曖昧ではないため、連続関数と呼ぶこともできる。

ドメイン理論は、情報状態の構造をモデル化するための純粋に定性的なアプローチです。何かがより多くの情報を含んでいると言うことはできますが、追加される情報の量は特定されません。しかし、ある意味で、与えられた情報状態よりもはるかに単純な（あるいははるかに不完全な）要素について議論したい状況もあります。たとえば、ある冪集合上の自然な部分集合包含順序では、任意の無限要素（つまり集合）は、その有限部分集合よりもはるかに「情報量が多い」と言えます。

このような関係をモデル化したい場合、まず、順序が ≤ である領域の誘導された厳密な順序 < を検討する必要があるかもしれません。しかし、これは全順序の場合には有用な概念ですが、部分順序集合の場合にはあまり役に立ちません。集合の包含順序を再び考えると、ある集合が別の（場合によっては無限の）集合よりも厳密に小さいのは、その集合の要素が 1 つ少ない場合だけです。しかし、これが「はるかに単純」という概念を捉えているとは到底言えないでしょう。

より詳細なアプローチでは、いわゆる近似次数の定義に至り、これはより示唆的に「はるかに低い関係」とも呼ばれる。要素x が要素yよりもはるかに低いとは、上限を持つ任意の有向集合Dに対して、

$${\displaystyle y\sqsubseteq \sup D,}$$

Dには次のような要素dが存在する。

$${\displaystyle x\sqsubseteq d.}$$

また、xはyを近似する とも言われ、次のように書かれる。

$${\displaystyle x\ll y.}$$

これは、

$${\displaystyle x\sqsubseteq y,}$$

単一要素集合 { y } は有向であるため、例えば集合の順序付けでは、無限集合はどの有限部分集合よりもはるかに上位に位置します。一方、有限集合の有向集合（実際には連鎖）を考えてみましょう。

$${\displaystyle \{0\},\{0,1\},\{0,1,2\},\ldots }$$

この連鎖の上限はすべての自然数の集合Nであるため、これはNよりはるかに小さい無限集合は存在しないことを示しています。

しかし、ある要素よりはるかに小さいということは相対的な概念であり、要素単体について多くを明らかにするものではありません。例えば、有限集合を順序論的に特徴づけたい場合、無限集合でさえ他の集合よりはるかに小さい場合があります。これらの有限要素xの特別な性質は、それらが自身よりはるかに小さいということです。つまり

$${\displaystyle x\ll x}$$

この性質を持つ要素はコンパクトとも呼ばれる。ただし、このような要素は、他の数学用語の用法において「有限」である必要も「コンパクト」である必要もない。とはいえ、この表記法は、集合論や位相幾何学におけるそれぞれの概念との類似性に基づいている。領域のコンパクト要素は、既に出現していない有向集合の極限として得られないという重要な特殊性質を持つ。

下方関係に関する他の多くの重要な結果は、この定義が領域の多くの重要な側面を捉えるのに適切であるという主張を裏付けている。

以上の考察から、別の疑問が生じる。ある領域のすべての要素が、はるかに単純な要素の極限として得られることを保証できるだろうか？これは実際において非常に重要な問題である。なぜなら、無限のオブジェクトを計算することはできないが、それでもそれらを任意の精度で近似することは期待できるからである。

より一般的には、他のすべての要素を最小上界として得るのに十分である要素の特定の部分集合に限定したい。したがって、半順序集合Pの基底を、 Pの部分集合Bとして定義する。ただし、P の各要素 x に対して、 B内のxよりはるかに小さい要素の集合には、上限がxである有向集合が含まれる。半順序集合Pは、基底を持つ場合、連続半順序集合である。特に、この場合、 P自体が基底となる。多くの応用では、研究の主な対象として連続 (d)cpos に限定する。

最後に、半順序集合に対するさらに強い制約として、有限要素の基底の存在を要求する方法がある。このような半順序集合は代数的半順序集合と呼ばれる。表示的意味論の観点から見ると、代数的半順序集合は、有限要素に限定した場合でもすべての要素を近似できるため、特に扱いやすい。前述したように、すべての有限要素が古典的な意味で「有限」であるとは限らず、有限要素が非可算集合を構成する場合もある。

しかし、場合によっては、半順序集合の基底が可算であることがあります。この場合、ω連続半順序集合と呼ばれます。したがって、可算基底がすべて有限要素から構成されている場合、 ω代数的な順序が得られます。

ドメインの単純な特殊ケースとして、基本ドメインまたはフラットドメインと呼ばれるものがある。これは、整数などの比較不可能な要素の集合と、他のすべての要素よりも小さいとみなされる単一の「底」要素から構成される。

他にも「ドメイン」として適した興味深い特殊な順序構造のクラスがいくつか得られます。すでに連続半順序集合と代数半順序集合について述べました。これらのより特殊なバージョンは、連続および代数的なcposです。さらに完全性の性質を追加すると、連続束と代数束が得られます。これらは、それぞれの性質を持つ完全束です。代数の場合、研究する価値のあるより広い半順序集合のクラスが見つかります。歴史的に、スコットドメインはドメイン理論で最初に研究された構造でした。さらに広いドメインのクラスは、SFPドメイン、Lドメイン、および双有限ドメインで構成されています。

これらの順序のクラスはすべて、単調関数、スコット連続関数、あるいは射などのより特殊な関数を用いて、さまざまなカテゴリのdcposに分類できます。最後に、ドメインという用語自体は厳密な定義ではないため、正式な定義が既に与えられている場合、または詳細が重要でない場合にのみ、略語として使用されることに注意してください。