デデキント・マクニール完成

数学、特に順序理論において、半順序集合のデデキント・マクニール完備化は、その集合を含む最小の完備束である。これは、1937年の論文で初めて定義と構成を行ったホルブルック・マン・マクニールにちなんで名付けられ、また、その構成が、デデキントが有理数から実数を構成するために用いたデデキントカットを一般化していることから、リチャード・デデキントにもちなんで名付けられている。これは、カットによる完備化または正規完備化とも呼ばれる。^{[ 1 ]}

半順序集合( poset)は、要素の集合と、要素のペア間の反射律 (すべてのxに対してx ≤ xが成り立つ)、推移律( x ≤ yかつy ≤ zならばx ≤ zが成り立つ)、反対称律(x ≤ y かつ y ≤ x が成り立つならばx = yが成り立つ)を満たす二項関係x ≤ yから構成されます。整数または実数に対する通常の数値順序はこれらの性質を満たしますが、数値に対する順序とは異なり、半順序には比較不可能な2 つの要素が存在する場合があります。つまり、 x ≤ yもy ≤ xも成り立ちません。半順序のもう 1 つのよく知られた例は、集合のペアに対する包含順序 ⊆ です。 ^{[ 2 ]}

Sが半順序集合である場合、 Sの完備化とは、 SをLに順序埋め込みした完備束Lを意味します。^{[ 3 ]}完備束とは、 Lの要素のすべての部分集合が下限と上限を持つ束のことです。これは、実数の類似の性質を一般化したものです。順序埋め込みとは、 Sの異なる要素をLの異なる要素に写像する関数であり、 Sの要素の各ペアは、Sと同じ順序をLでも持ちます。拡張された実数直線(実数と +∞ および −∞ を含む) は、この意味で有理数の完備化です。有理数の集合{3, 3.1, 3.14, 3.141, 3.1415, 3.14159, ...} は有理数の最小上界を持ちませんが、実数では最小上界πを持ちます。^{[ 4 ]}

与えられた半順序集合には、いくつかの異なる完備化が存在する可能性がある。例えば、任意の半順序集合Sの完備化の一つは、包含関係によって順序付けられた、その下方閉部分集合の集合である。Sは、各要素x をx以下の要素の下位集合に写像することによって、この（完備な）束に埋め込まれる。結果として得られるのは分配束であり、 Birkhoff の表現定理で使用される。ただし、 Sの完備化を形成するために必要な要素よりもはるかに多くの要素を持つ可能性がある。^{[ 5 ]}すべての可能な束の完備化の中で、Dedekind–MacNeille 完備化は、 Sが埋め込まれた最小の完備束である。 ^{[ 6 ]}

半順序集合Sの各部分集合Aについて、A ^{u を}Aの上限集合とします。つまり、Sの要素xは、 x がAのすべての要素以上である場合に限りA ^uに属します。同様に、A ^{ℓ を}Aの下限集合、つまりAのすべての要素以下である要素の集合とします。すると、 Sのデデキント・マクニール完備化は、次の条件を満たすすべての部分集合Aから構成されます。

( A ^u ) ^ℓ = A、

包含関係によって順序付けられる:完備化においてA ≤ Bとなるのは、 A ⊆ B が集合として成り立つ場合に限る。^{[ 7 ]}

Sの要素xは、その主イデアルとして完備化に埋め込まれ、 x以下の要素の集合↓ _xとなる。このとき、(↓ _x ) ^uはx以上要素の集合であり、((↓ _x ) ^u ) ^ℓ = ↓ _xとなる。これは、 ↓ _xが確かに完備化の要素であることを示している。xから↓ _xへの写像は順序埋め込みである。^{[ 7 ]}

デデキントカットの定義により近い、デデキント・マクニール完備化の別の定義が用いられることがある。^{[ 8 ]}半順序集合Sにおいて、カットをA ^u = BかつA = B ^ℓとなる集合のペア( A , B )と定義する。( A , B )がカットであれば、 A は方程式( A ^u ) ^ℓ = Aを満たし、逆に( A ^u ) ^ℓ = Aであれば、 ( A , A ^u )はカットである。したがって、カットの下位集合に対する包含関係 (または上位集合に対する包含関係の逆) によって半順序付けられたカットの集合は、デデキント・マクニール完備化の同等の定義を与える。^{[ 9 ]}

別の定義では、完全格子の結合操作と交わり操作の両方に対称的な記述があります。任意のカット族のカットが( A _i , B _i )である場合、これらのカットの交わりはカット( L , L ^u )で、L = ∩ _i A _i、結合はカット( U ^ℓ , U )で、 U = ∩ _i B _iです。^{[ 9 ]}

もし${\displaystyle \mathbb {Q} }$は、通常の数値順序を持つ全順序集合とみなされる有理数の集合であり、そのデデキント・マクニール完備化の各要素は、${\displaystyle \mathbb {Q} }$これはデデキントカットと見なすことができ、デデキントとマクニールによる完成は${\displaystyle \mathbb {Q} }$は実数全体の順序であり、2つの追加値も含まれる。${\displaystyle \pm \infty }$[ ^{10 ]​}

S が反鎖(2 つの要素が比較できない要素の集合)である場合、 Sのデデキント-マクニール完備化は、S自体と、 Sのすべての要素の下にある最下位要素とSのすべての要素の上にある最上位要素という2 つの追加要素から構成されます。^{[ 11 ]}

Oが任意の有限個のオブジェクトの集合であり、AがO内のオブジェクトの任意の有限個の単項属性の集合である場合、オブジェクトと属性を要素とする高さ 2 の半順序を形成でき、x が属性yを持つオブジェクトである場合はx ≤ yとなります。このように定義された半順序の場合、Sのデデキント-マクニール完備化は概念束として知られており、形式概念分析の分野で中心的な役割を果たします。^{[ 12 ]} 

半順序集合Sのデデキント・マクニール完備化は、Sが埋め込まれた最小の完備束である。つまり、L がSの任意の束完備化である場合、デデキント・マクニール完備化はLの半順序部分集合である。^{[ 6 ]} Sが有限の場合、その完備化も有限であり、 Sを含むすべての有限完備束の中で要素数が最小である。^{[ 12 ]}

半順序集合Sは、デデキント-マクニール完備化において結合密かつ交わり密である。すなわち、完備化のすべての要素は、Sの要素の集合の結合であり、かつSの要素の集合の交わりでもある。^{[ 13 ]}デデキント-マクニール完備化は、Sの完備化の中でこの性質によって特徴づけられる。^{[ 14 ]}

ブール代数のデデキント・マクニール完備化は完備ブール代数である。この結果は、ヴァレリー・イヴァノヴィチ・グリヴェンコとマーシャル・ストーンにちなんでグリヴェンコ・ストーン定理として知られている。^{[ 15 ]}同様に、残余束のデデキント・マクニール完備化は完備残余束である。^{[ 16 ]}ただし、分配束の完備化はそれ自体が分配的であるとは限らず、モジュラー束の完備化はモジュラーのままではない可能性がある。^{[ 17 ]}

デデキント・マクニール完備化は自己双対である。半順序の双対の完備化は、完備化の双対と同じである。^{[ 18 ]}

Sのデデキント-マクニール完備化は、S自体と同じ位数次元を持つ。^{[ 19 ]}

半順序集合と半順序集合間の単調関数のカテゴリーでは、完全束は順序埋め込みの単射対象を形成し、 Sのデデキント・マクニール完備化はSの単射包である。^{[ 20 ]} 

複数の研究者が、有限半順序集合のデデキント・マクニール完備化を構築するアルゴリズムを研究してきた。デデキント・マクニール完備化は、それが由来する半順序よりも指数関数的に大きくなる可能性があり、^{[ 12 ]} 、そのようなアルゴリズムの時間制限は一般的に、入力半順序の要素数nと完備化の要素数cの両方に依存する出力依存的な方法で示される。

• PlanetMathにおけるMacNeilleの完了
• n Labにおけるマクニールの完成