収束していく仕様としての有向集合

ウィキペディア小見出し辞書

収束していく仕様としての有向集合

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/22 07:55 UTC 版)

「領域理論」の記事における「収束していく仕様としての有向集合」の解説

すでに述べたように、領域理論は計算の領域をモデル化するのに半順序集合を取り扱う。 目標は、このような順序集合の要素を「情報の断片」あるいは「計算の（部分的）結果」として解釈することである。 そこでは、この順序でより大きな要素は、それ以下の要素の情報を矛盾しない方法で拡張したものとなる。 ここでこの単純な直観的解釈からすでに、領域は多くの場合、最大元を持っていないことがわかる。 最大元を持つことは、領域の「すべて」の要素の情報を含むというあまり面白くない状況にあたる要素が存在することを意味するからである。 この理論で重要な役割をはたす概念のひとつは、領域の有向部分集合 (directed subset)、すなわち、任意の 2 要素に対してその上界を持つような非空の部分集合である。領域についての直観的解釈の観点では、2つの情報の断片に矛盾がないことを上界の存在が保証することになり、有向部分集合を「矛盾しない仕様」、つまり、どの 2 つの要素も矛盾することのない部分的な計算結果の集合としてみることができる。 この解釈は、列の各要素がそれより前の要素よりも収束先を明確に示唆しているような解析学の収束列の概念と比較できる。 実際、距離空間の理論では、数列は、領域理論における有向集合の役割と多くの点で類似した役割を演じる。 いま、数列の場合と同じように、有向集合の「極限」に興味がある。 上で述べたことに従えば、これは、有向集合のすべての要素の情報を拡張した情報の最も一般的な断片にあたる要素、すなわち、有向集合に含まれる情報を「正確」に含み、それ以上のものはもたない唯一の要素ということになるだろう。 順序集合の形式では、これは有向集合の上限 (最小上界) にすぎない。 数列の極限の場合のように、有向集合の上限は常に存在するとは限らない。 もちろん、仕様が矛盾しないならば必ず「収束」するような計算の領域、すなわち、すべての有向集合が上限をもつような順序に興味をもつのが自然だろう。 この特性は有向完備半順序集合 (directed complete partial order set)、あるいは略して dcpo を定める。 実のところ、領域理論のほとんどの考察は、少なくとも有向完備であるような順序のみを考えている。 不完全な知識を表現するものとして部分的な仕様を考えるというアイデアから、最小元の存在という別の望ましい特性が導かれる。 この要素は情報を持たないという状態のモデルとなり、ふつう計算が開始される起点である。 これはまた、まったく何も結果を返さないような計算の出力とみなすこともできる。 理論にとっての重要さから最小元をもつ dcpo は完備半順序集合 (complete partial order set) または単に cpo と呼ばれる。