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

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

順序埋め込みと格子補完

半順序集合（poset）は、要素の集合と、その要素のペアに関する二項関係 $x \leq y$ で構成されます。この関係は、反射的（任意のxに対して $x \leq x$ ）、推移的（ $x$ $\leq$ $y$ かつ $y$ $\leq$ $z$ であれば $x$ $\leq$ $z$ ）、反対称的（ $x$ $\leq$ $y$ かつ $y$ $\leq$ $x$ が両方とも成立する場合、 $x$ $=$ $y$ ）です。整数または実数に対する通常の数値順序はこれらの特性を満たします。ただし、数値に対する順序とは異なり、半順序には比較できない2 つの要素が含まれる場合があります。つまり、 $x$ $\leq$ $y$ も $y$ $\leq$ $x$ も成立しません。半順序のもう 1 つのよく知られた例は、集合のペアに対する包含順序 ⊆ です。 ^[2]

$S が$ 半順序集合である場合、 $S$ の完備化とは、 $S$ を $L$ に順序埋め込みする完全格子 $L を$ 意味します。^{[3]完全格子とは、} $Lの要素のすべての部分集合に$ 最小値と最大値がある格子です。これは、実数の類似した特性を一般化したものです。順序埋め込みは、 $Sの異なる要素を$ $L$ の異なる要素にマッピングする関数であり、 $S$ の各要素のペアは、 $L$ でも $S$ と同じ順序を持ちます。拡張された実数直線(実数と +∞ および −∞ の組み合わせ) は、この意味での有理数の完備化です。有理数の集合 {3、3.1、3.14、3.141、3.1415、3.14159、...} には有理数の最小上限はありませんが、実数では最小上限 $π$ があります。^[4]

与えられた半順序集合には、複数の異なる完備化が存在する場合がある。例えば、任意の半順序集合 $Sの 1 つの完備化は$ 、包含によって順序付けられた下向きに閉じた部分集合の集合である。 $Sは、各要素$ $x を$ $x$ 以下の要素の下側集合にマッピングすることによって、この (完全な) 格子に埋め込まれる。結果は分配格子であり、バーコフの表現定理で使用される。ただし、 $S$ の完備化を形成するために必要な要素よりもはるかに多くの要素を持つ場合がある。^{[5]すべての可能な格子完備化の中で、デデキント-マクニール完備化は、} $S$ が埋め込まれた最小の完全な格子である。 ^[6]

意味

半順序集合 $S$ の各部分集合 $A$ について、 $A$ $u を$ $A$ の上限集合とする。つまり、 $S$ の要素 $x は、$ $xが$ $A$ のどの要素よりも大きいか等しいときはいつでも $A$ $u$ に属する。対称的に、 $A$ $l を$ $A$ の下限集合、つまり $A$ のどの要素よりも小さいか等しい要素の集合とする。すると、 $S$ のデデキント・マクニール完備化は、次のすべての部分集合 $A$ から構成される。

（ Au ） l = A

;

​

それは包含関係によって順序付けられる：完備化において $A \leq B$ であるのは、集合として $A \subseteq B$ ^{である場合に限る。 [7]}

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

デデキントカットの定義にもっと近い、デデキント-マクニール完備化の別の定義が時々使われる。^[8]半順序集合 $S$ において、 $A$ $u$ $=$ $B$ かつ $A$ $=$ $B$ $l$ となる集合 $($ $A$ $,$ $B$ $)$ のペアをカットと定義する。 $($ $A$ $,$ $B$ $)$ がカットならば、 A は等式 $($ $A$ $u$ $)$ $l$ $=$ $A$ を満たし、逆に $($ $A$ $u$ $)$ $l$ $=$ $A$ ならば $($ $A$ $,$ $A$ $u$ $)$ はカットである。したがって、カットの下位集合への包含関係（または上位集合への包含関係の逆）によって部分的に順序付けられたカットの集合は、デデキント-マクニール完備化と同等の定義を与える。^[9]

代替定義では、完全格子の結合操作と会合操作の両方が対称的な記述を持つ。つまり、 $(A i 、 B i)$ が任意のカット族のカットである場合、これらのカットの会合はカット $(L 、 L u)$ $（L = \cap i A i）$ であり、結合はカット $(U l 、 U) （$ $U = \cap i B i）$ である。^[9]

例

が有理数全体の集合であり、通常の数値順序を持つ全順序集合として見ると、のデデキント・マクニール完備化の各要素はデデキント切断として見ることができ、のデデキント・マクニール完備化は実数上の全順序付けと2つの追加値を組み合わせたものとなる。^[10] $\mathbb {Q}$ $\mathbb {Q}$ $\mathbb {Q}$ $\pm \infty$

$S$ が反鎖（どの要素も比較できない集合）である場合、 $Sのデデキント・マクニール完備化は$ $S自身と、$ $S$ 内のすべての要素の下にあるボトム要素と $S$ 内のすべての要素の上にあるトップ要素の2つの追加要素から構成されます。^[11]

$O$ が任意の有限オブジェクトの集合であり、 $Aが$ $O$ 内のオブジェクトの単項属性の任意の有限集合である場合、高さ 2 の半順序を形成できます。半順序の要素はオブジェクトと属性であり、 $xが属性$ $y を$ 持つオブジェクトのときに $x \leq 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の両方に応じて規定される。$

カットセットの構築

Ganter & Kuznetsov (1998) は、入力された部分順序が一度に 1 つの要素を追加することによって構築される増分アルゴリズムについて説明しています。各ステップで、小さい部分順序の完成が拡張され、大きい部分順序の完成が形成されます。彼らの方法では、完成はカットの明示的なリストによって表されます。拡張された部分順序の各カットは、2 つのセットが新しい要素で交差するものを除き、前の部分順序からのカットであるか、前の部分順序からのカットの一方または他方の側に新しい要素を追加することによって形成されるため、彼らのアルゴリズムでは、この形式のセットのペアをテストするだけで、どれがカットであるかを判断できます。彼らの方法を使用して部分順序の完成に 1 つの要素を追加するのにかかる時間は $O (cnw)$ です。ここで、 $w は部分順序の幅、つまりその最大の$ 反鎖のサイズです。したがって、特定の部分順序の完成を計算する時間は $O (cn 2 w) = O(cn 3)$ です。^[12]

Jourdan、Rampon & Jard (1994) が指摘しているように、半順序集合内のすべてのカットをリストする問題は、より単純な問題、つまり、異なる半順序集合内のすべての最大アンチチェーンをリストする問題の特殊なケースとして定式化できます。 $P が$ 任意の半順序集合である場合、 $Q を、要素が$ $P$ のコピーを 2 つ含む半順序とします。 $P$ の各要素 $x$ に対して、 $Q は2 つの要素$ $x$ $0$ と $x$ $1$ を含み、 $x$ $i$ $<$ $y$ $j$ となるのは、 $x$ $<$ $y$ かつ $i$ $<$ $j$ $の場合のみです。このとき、 P$ のカットは、 $Q$ の最大アンチチェーンと 1 対 1 で対応します。つまり、カットの下位セットの要素は、アンチチェーンの添え字 0 の要素に対応し、カットの上位セットの要素は、アンチチェーンの添え字 1 の要素に対応します。 Jourdan ら最大アンチチェーンを見つけるアルゴリズムを記述する。このアルゴリズムは、 $P$ 内のすべてのカットをリストする問題に適用すると、時間 $O$ $($ $c$ $($ $nw$ $+$ $w$ $3$ $))$ かかる。これは、幅 $w$ が小さい場合の Ganter & Kuznetsov (1998) のアルゴリズムの改良版である。^{[21]あるいは、} $Q$ の最大アンチチェーンは、 $Q$ の比較可能性グラフの最大独立集合、または比較可能性グラフの補集合の最大クリークと同じであるため、クリーク問題または独立集合問題のアルゴリズムをこのバージョンのデデキント-マクニール完備化問題に適用することもできる。^[22]

被覆グラフの構築

デデキント-マクニール完備化の推移的簡約または被覆グラフは、その要素間の順序関係を簡潔に記述する。カットの各隣接頂点は、カットの上部または下部の集合から元の半順序の要素を 1 つ削除する必要があるため、各頂点の隣接頂点は最大で $n$ 個になる。したがって、被覆グラフには $c 個の$ 頂点と最大で $cn /2 個$ の隣接頂点があるが、この数は、要素間のすべての一対比較を指定する行列の $c 2$ 個の要素よりもはるかに小さい可能性がある。Nourine と Raynaud (1999) は、この被覆グラフを効率的に計算する方法を示している。より一般的には、 $B が任意の集合族である場合、彼らは$ $B$ の部分集合の和集合の格子の被覆グラフを計算する方法を示している。デデキント-マクニール格子の場合、 $B は主イデアルの$ 補集合の族と見なすことができ、 $B$ の部分集合の和集合はカットの下部集合の補集合である。彼らのアルゴリズムの主なアイデアは、 $Bのサブセットの和集合を増分的に生成し（$ $B$ の各セットについて、以前に生成されたすべての和集合との和集合を形成し）、結果として得られるセットの族をトライで表現し、トライ表現を使用して、カバー関係における隣接性について特定の候補セットのペアをテストすることです。これには $O (cn 2) の$ 時間がかかります。後の研究で、同じ著者は、同じ合計時間の制限で、アルゴリズムを完全に増分的に（部分順序に要素を1つずつ追加できるように）できることを示しました。^[23]

注記

^ Davey & Priestley (2002, p. 166); Schröder (2003, p. 119)。
^ ローマン（2007年）。
^ Schröder (2003)、定義 5.3.1、p. 119.
^ オリアリー（2015年）。
^ カルピネート、クラウディオ、ロマーノ、ジョヴァンニ（2004）、概念データ分析：理論と応用、ジョン・ワイリー・アンド・サンズ、p. 10、ISBN 978-0-470-85055-8。
^ ab Bishop (1978); Schröder (2003)、定理5.3.8、p. 121。
^ ab MacNeille (1937)、補題11.8、p.444; Davey & Priestley (2002)、補題3.9(i)、p.166。
^ これは、たとえば MacNeille (1937) が最初に使用した定義です。
^ マクニール（1937年）。
^ Davey & Priestley (2002)、例7.44(1)、p.168; Schröder (2003)、例5.3.3(2)、p.120。
^ Davey & Priestley (2002)、例7.44(2)、p.168。
^ abcd ガンター & クズネツォフ (1998)。
^ Schröder (2003)、命題 5.3.7、p. 121.
^ シュミット（1956年）。
^ バーコフ（1995）、定理27、p.130。
^ ガバイ、シェットマン、スクヴォルツォフ（2009年）。
^ コトラル (1944);船山（1944年）。
^ バーコフ（1995年）。
^ この結果は、1961 年にハーバード大学で KA ベイカーが書いた未発表の優等論文「部分的に順序付けられた集合における次元、結合独立性、および幅」に起因するとよく言われる。この論文は Novák (1969) によって出版された。
^ バナシェフスキー＆ブルンス（1967年）。
^ ジョーダン、ランポン、ジャード (1994)。
^ 半順序の反連鎖のアルゴリズムと比較グラフの独立集合のアルゴリズムの同等性については、Cameron (1985)、251 ページを参照してください。
^ ノウリン＆レイノー（2002年）。

参考文献

Banaschewski, B.; Bruns, G. (1967)、「マクニール完備化のカテゴリカルな特徴付け」、Archiv der Mathematik、18 (4): 369–377、doi :10.1007/BF01898828、MR 0221984、S2CID 121216988。
バーコフ、ギャレット(1995)、「VI.9 カットによる完成」、格子理論、コロキウム出版、第 25 巻 (第 3 版)、アメリカ数学会、pp. 126–128、ISBN 978-0-8218-1025-5。
ビショップ、アラン A. (1978)、「カットによる完了の普遍的なマッピング特性」、Algebra Universalis、8 (3): 349–353、doi :10.1007/bf02485405、MR 0469839、S2CID 121624631。
キャメロン、キャシー（1985）、「アンチチェーンシーケンス」、Order、2（3）：249–255、doi：10.1007 / BF00333130、MR 0824698
コトラル、ミシャ(1944)、「構造の構築方法と位相空間および抽象算術へのその応用」、Univ. Nac. Tucumán. Revista A.、4 : 105–157、MR 0014062。
Davey, BA; Priestley, Hilary A. (2002)、「7.38 デデキント・マクニール補完」、格子と秩序入門（第2版）、ケンブリッジ大学出版局、p. 166、ISBN 978-0-521-78451-1、Zbl 1002.06001。
船山根之助 (1944)、「分配格子のカットによる完成について」、帝国学士院紀要、東京、20 : 1–2、doi : 10.3792/pia/1195573210、MR 0014063、Zbl 0063.01484。
Gabbay, Dov M. ; Shehtman, Valentin; Skvortsov, Dimitrij (2009)、「3.4.12 残余格子の Dedekind–MacNeille 完成」、Quantification in Nonclassical Logic、第 1 巻、論理学と数学の基礎の研究、第 153 巻、Elsevier、pp. 177–178、ISBN 978-0-444-52012-8、Zbl 1211.03002。
Ganter, Bernhard; Kuznetsov, Sergei O. (1998)、「Dedekind-MacNeille 完備化の段階的構築」、Proc. 6th Int. Conf. Conceptual Structures: Theory, Tools and Applications (ICCS98)、Lecture Notes in Computer Science、vol. 1453、Springer-Verlag、pp. 295–302、doi :10.1007/BFb0054922、MR 1673860、Zbl 0928.06004。
Jourdan, Guy-Vincent; Rampon, Jean-Xavier; Jard, Claude (1994)、「ポセットの最大反鎖の格子のオンライン計算」(PDF)、Order、11 (3): 197–210、doi :10.1007/BF02115811、MR 1308475、S2CID 120755660、Zbl 0814.06004。
マクニール、HM (1937)、「部分順序集合」、アメリカ数学会誌、42 (3): 416–460、doi : 10.2307/1989739、JFM 63.0833.04、JSTOR 1989739、MR 1501929、Zbl 0017.33904。
Nourine, Lhouari; Raynaud, Olivier (1999)、「格子を構築するための高速アルゴリズム」、Information Processing Letters、71 (5–6): 199–204、CiteSeerX 10.1.1.502.3181、doi :10.1016/S0020-0190(99)00108-8、MR 1726978、Zbl 0998.06005。
Nourine, Lhouari; Raynaud, Olivier (2002)、「格子を構築するための高速増分アルゴリズム」、Journal of Experimental and Theoretical Artificial Intelligence、14 (2): 217–227、doi :10.1080/09528130210164152、S2CID 38160433、Zbl 1022.68027。
Novák、Vítězslav (1969)、「Über eine Eigenschaft der Dedekind-MacNeilleschen Hülle」、Mathematische Annalen、179 : 337–342、doi :10.1007/BF01350778、MR 0240010、S2CID 120963245。
オリアリー、マイケル L. (2015)、数学論理と集合論入門、ジョンワイリーアンドサンズ、p. 276、ISBN 978-0-470-90588-3
ローマン、スティーブン（2007）、上級線形代数、大学院数学テキスト、第135巻（第3版）、シュプリンガー、pp. 10-11、ISBN 978-0-387-72831-5
Schmidt, Jürgen (1956)、「Zur Kennzeichnung der Dedekind-MacNeilleschen Hülle einer geordneten Hülle」、Archiv der Mathematik (ドイツ語)、7 : 241–249、doi :10.1007/BF01900297、MR 0084484
Schröder、Bernd SW (2003)、「5.3 Embeddings/The Dedekind/MacNeille Completion」、Ordered Sets: An Introduction、Birkhäuser、pp. 119–122、ISBN 978-1-4612-6591-7。

外部リンク

PlanetMathにおける MacNeille 補完
n ラボでのマクニール完了

[1] Davey & Priestley (2002, p. 166); Schröder (2003, p. 119)。

[FOOTNOTERoman2007-2] ローマン（2007年）。

[3] Schröder (2003)、定義 5.3.1、p. 119.

[FOOTNOTEO'Leary2015-4] オリアリー（2015年）。

[5] カルピネート、クラウディオ、ロマーノ、ジョヴァンニ（2004）、概念データ分析：理論と応用、ジョン・ワイリー・アンド・サンズ、p. 10、ISBN 978-0-470-85055-8。

[smallest-completion-6] Bishop (1978); Schröder (2003)、定理5.3.8、p. 121。

[def-7] MacNeille (1937)、補題11.8、p.444; Davey & Priestley (2002)、補題3.9(i)、p.166。

[8] これは、たとえば MacNeille (1937) が最初に使用した定義です。

[FOOTNOTEMacNeille1937-9] マクニール（1937年）。

[10] Davey & Priestley (2002)、例7.44(1)、p.168; Schröder (2003)、例5.3.3(2)、p.120。

[11] Davey & Priestley (2002)、例7.44(2)、p.168。

[FOOTNOTEGanterKuznetsov1998-12] ガンター & クズネツォフ (1998)。

[13] Schröder (2003)、命題 5.3.7、p. 121.

[FOOTNOTESchmidt1956-14] シュミット（1956年）。

[15] バーコフ（1995）、定理27、p.130。

[FOOTNOTEGabbayShehtmanSkvortsov2009-16] ガバイ、シェットマン、スクヴォルツォフ（2009年）。

[17] コトラル (1944);船山（1944年）。

[FOOTNOTEBirkhoff1995-18] バーコフ（1995年）。

[19] この結果は、1961 年にハーバード大学で KA ベイカーが書いた未発表の優等論文「部分的に順序付けられた集合における次元、結合独立性、および幅」に起因するとよく言われる。この論文は Novák (1969) によって出版された。

[FOOTNOTEBanaschewskiBruns1967-20] バナシェフスキー＆ブルンス（1967年）。

[FOOTNOTEJourdanRamponJard1994-21] ジョーダン、ランポン、ジャード (1994)。

[22] 半順序の反連鎖のアルゴリズムと比較グラフの独立集合のアルゴリズムの同等性については、Cameron (1985)、251 ページを参照してください。

[FOOTNOTENourineRaynaud2002-23] ノウリン＆レイノー（2002年）。