領域理論
すでに述べたように、領域理論は計算の領域をモデル化するのに半順序集合を取り扱う。 目標は、このような順序集合の要素を「情報の断片」あるいは「計算の(部分的)結果」として解釈することである。 そこでは、この順序でより大きな要素は、それ以下の要素の情報を矛盾しない方法で拡張したものとなる。 ここでこの単純な直観的解釈からすでに、領域は多くの場合、最大元を持っていないことがわかる。 最大元を持つことは、領域の「すべて」の要素の情報を含むというあまり面白くない状況にあたる要素が存在することを意味するからである。
この理論で重要な役割をはたす概念のひとつは、領域の有向部分集合 (directed subset)、すなわち、任意の 2 要素に対してその上界を持つような非空の部分集合である。領域についての直観的解釈の観点では、2つの情報の断片に矛盾がないことを上界の存在が保証することになり、有向部分集合を「矛盾しない仕様」、つまり、どの 2 つの要素も矛盾することのない部分的な計算結果の集合としてみることができる。 この解釈は、列の各要素がそれより前の要素よりも収束先を明確に示唆しているような解析学の収束列の概念と比較できる。 実際、距離空間の理論では、数列は、領域理論における有向集合の役割と多くの点で類似した役割を演じる。
いま、数列の場合と同じように、有向集合の「極限」に興味がある。
計算の領域が何であるべきかについて、すでにいくつかの基礎的で形式的な記述がそろったので、計算そのものへと目を転じることができる。 明らかに、それは関数でなければならず、ある計算の領域から入力をもらい、ある(おそらくは異なった)領域へと出力を返す。 さらに、入力の情報の内容が増えたなら、関数の出力がより多くの情報を含むとも期待できるだろう。 これは、形式的には単調な関数を要求していることになる。
Dcpo を扱うときには、有向集合の極限の構成と矛盾しない計算も要求するかもしれない。 これは形式的に、ある関数 f に対して、有向集合 D の像 f(D) (すなわち、D の各要素の像の集合)がやはり有向集合であって、上限として D の上限の像をもつことを意味する。 これを f が有向集合の上限を保存するとも言える。 また、2 要素の有向集合を考えればわかるように、このような関数は単調でなければならないこともわかる。 この特性は、スコット連続 (Scott-continuous) な関数の概念を与える。 多くの場合あいまいにはならないので、これは単に 連続関数 とも言われる。