文献あり

デデキント・マクニール完備化

260

Wikipediaを眺めていたらデデキント・マクニール完備化 (Dedekind-MacNeille completion) という概念を知ったので，勉強したことを書き残しておきます．
デデキント・マクニール完備化とは，半順序集合に対して，それを含む最小の完備束を構成する操作のことです．

[Wikipedia](https://en.wikipedia.org/wiki/Dedekind%E2%80%93MacNeille_completion)に載っていた[画像](https://commons.wikimedia.org/wiki/File:Dedekind-Macneille_completion.svg) Wikipedia に載っていた画像

上の画像が何をしているのかイメージできるようになることを目標に解説していきます．
詳しくは後述しますが，デデキント・マクニール完備化は冪集合の部分集合として構成されます．

半順序集合!FORMULA[0][37205][0]を，冪集合!FORMULA[1][754177012][0]に含まれるある完備束!FORMULA[2][1329949504][0]に埋め込む半順序集合 $S$ を，冪集合 $2^{S}$ に含まれるある完備束 $DM (S)$ に埋め込む

準備

上界・下界

$S$ を半順序集合とし， $A$ を $S$ の部分集合とする．
このとき $A$ の上界全体の集合を $A^{u}$ と書き， $A$ の下界全体の集合を $A^{l}$ と書く．
$\begin{aligned} A^{u} & := {u \in S ∣ 任意の a \in A に対して a \leq u が成り立つ}, \\ A^{l} & := {l \in S ∣ 任意の a \in A に対して l \leq a が成り立つ} . \end{aligned}$

$(S, \leq)$ を半順序集合とし， $x, y \in S$ とする．このとき，次の3条件は同値である．

$x \leq y$ .
${x}^{l} \subset {y}^{l}$ .
${x}^{u} \supset {y}^{u}$ .

(1)

\Leftrightarrow

(2) のみ示す．（(1)

\Leftrightarrow

(3) も同様）

$(\Rightarrow)$ ： $z \in {x}^{l}$ を任意に取ると， $z \leq x \leq y$ より $z \in {y}^{l}$ が成り立つ．
$(\Leftarrow)$ ：反射律より $x \in {x}^{l} \subset {y}^{l}$ となるから $x \leq y$ である．

$(S, \leq)$ を半順序集合とし， $A, B$ を $S$ の部分集合とする．このとき，次のことが成り立つ．

$A \subset A^{ul}$ と $A \subset A^{lu}$ が成り立つ．
$A \subset B$ であれば， $A^{u} \supset B^{u}$ と $A^{l} \supset B^{l}$ が成り立つ．
$A \subset B$ であれば， $A^{ul} \subset B^{ul}$ と $A^{lu} \subset B^{lu}$ が成り立つ．
$A^{ulu} = A^{u}$ と $A^{lul} = A^{l}$ が成り立つ．

$a \in A$ を任意に取る．このとき任意の $u \in A^{u}$ に対して $a \leq u$ が成り立つから， $a$ は $A^{u}$ の下界であり $a \in A^{ul}$ を得る．同様に，任意の $l \in A^{l}$ に対して $l \leq a$ が成り立つから， $a$ は $A^{l}$ の上界であり $a \in A^{lu}$ も成り立つ．
$u \in B^{u}$ と $a \in A$ を任意に取ると， $A \subset B$ より $a \in B$ だから $a \leq u$ が成り立ち， $u \in A^{u}$ を得る． $A^{l} \supset B^{l}$ も同様に示せる．
(2)より $A^{u} \supset B^{u}$ が成り立つから，再び(2)を使えば $A^{ul} \subset B^{ul}$ を得る． $A^{lu} \subset B^{lu}$ も同様に示せる．
(1)より $A \subset A^{ul}$ が成り立つから，(2)より $A^{u} \supset A^{ulu}$ である．また，(1)より $A^{u} \subset A^{ulu}$ でもある． $A^{lul} = A^{l}$ も同様に示せる．

特に次の3性質が成り立つことに注意しておきます．

A \mapsto A^{ul}

は閉包作用素．

$A \subset A^{ul}$ である．
$A \subset B$ ならば， $A^{ul} \subset B^{ul}$ である．
$(A^{ul})^{ul} = A^{ul}$ である．

前命題 (1),(2) より $(\cdot)^{u} : 2^{X} ⇄ 2^{X} : (\cdot)^{l}$ は Galois接続である．
(4) が成り立つことや $A \mapsto A^{ul}$ が閉包作用素となること（に対応する主張）は，一般のGalois接続に対しても全く同様に示される．

$\emptyset^{ul} = \emptyset$ を満たさない半順序集合 $S$ の例を一つ挙げよ．

$\emptyset^{u} = S$ だから，最小元をもつ半順序集合を考えればよい．たとえば大小関係による半順序集合 $N$ は $0$ を最小元にもつから
$\emptyset^{ul} = N^{l} = {0}$
である．

完備束

任意の部分集合が上限と下限をもつような半順序集合を完備束といいますが，この定義は「次の2条件 (1), (2) のどちらか一方を満たすこと」と弱めることができます．

半順序集合 $S$ について，次の2条件は同値である．

$S$ の任意の部分集合が上限をもつ．
$S$ の任意の部分集合が下限をもつ．

(1)

\Rightarrow

(2) のみ示す（逆も同様）

$S$ の任意の部分集合 $A$ に対して，下記2点より $sup_{S} (A^{l})$ が $A$ の下限となる．

$sup_{S} (A^{l}) = min (A^{lu})$ と $A^{lu} \supset A$ より， $sup_{S} (A^{l})$ は $A$ の下界である．
$A$ の下界 $x \in S$ を任意に取ると， $x \in A^{l}$ より $x \leq sup_{S} (A^{l})$ が成り立つ．

この証明から，次のこともわかります．

完備束 $L$ とその部分集合 $A$ に対して， $sup_{L} (A) = inf_{L} (A^{u})$ と $inf_{L} (A) = sup_{L} (A^{l})$ が成り立つ．

順序埋め込み

半順序集合 $S, L$ と写像 $ι : S \to L$ を考える．

$ι$ が単調増加であるとは， $x \leq y$ を満たす任意の $x, y \in S$ に対して $ι (x) \leq ι (y)$ が成り立つことをいう．
$ι$ が順序を反映するとは， $ι (x) \leq ι (y)$ を満たす任意の $x, y \in S$ に対して $x \leq y$ が成り立つことをいう．
$ι$ が順序埋め込みであるとは， $ι$ が単調増加かつ順序を反映することをいう．

順序を反映する写像は単射

半順序集合 $S, L$ と順序を反映する写像 $ι : S \to L$ について， $ι$ は単射である．

$x, y \in S$ が $ι (x) = ι (y)$ を満たすとき，反射律より $ι (x) \leq ι (y)$ かつ $ι (x) \geq ι (y)$ が成り立つ．すると $ι$ が順序を反映することから $x \leq y$ かつ $x \geq y$ となり，反対称律より $x = y$ を得る．

デデキント・マクニール完備化

定義と最小性

デデキント・マクニール完備化の定義を述べる前に，次の命題を示しておきます．

閉包作用素による完備束の像は完備束

$L$ を完備束とし，写像 $Cl : L ∋ x \mapsto x^{*} \in L$ は次の3条件を満たすとする．

任意の $x \in L$ に対して， $x \leq x^{*}$ が成り立つ．
$x \leq y$ を満たす任意の $x, y \in L$ に対して， $x^{*} \leq y^{*}$ が成り立つ．
任意の $x \in L$ に対して， $x^{* *} \leq x^{*}$ が成り立つ．

このとき，次のことが成り立つ．

任意の $x \in L$ に対して， $x^{* *} = x^{*}$ が成り立つ．
${Cl}^{\to} (L) = {x \in L ∣ x^{*} = x}$ である．（ただし， ${Cl}^{\to} (L)$ は $Cl$ による $L$ の像とした．（矢印記法））
${Cl}^{\to} (L)$ の部分集合 $S$ に対して，（ ${Cl}^{\to} (L)$ における） $S$ の上限・下限がともに存在して
$\begin{aligned} {sup}_{{Cl}^{\to} (L)} (S) & = {sup}_{L} (S)^{*}, \\ {inf}_{{Cl}^{\to} (L)} (S) & = {inf}_{L} (S) \end{aligned}$
が成り立つ．よって， ${Cl}^{\to} (L)$ は（ $L$ の半順序部分集合として）完備束である．

条件1より $x \leq x^{*}$ だから，条件2より $x^{*} \leq x^{* *}$ となる．これと条件3を合わせればよい．
任意の $x \in {Cl}^{\to} (L)$ に対して， $x = y^{*}$ を満たす $y \in L$ を取れば $x^{*} = y^{* *} = y^{*} = x$ となる．逆の包含は明らか．
まず上限について，任意の $x \in S$ に対して
$x \leq {sup}_{L} (S) \leq {sup}_{L} (S)^{*}$
が成り立つから， ${sup}_{L} (S)^{*}$ は $S$ の上界である．また $S$ の上界 $u \in {Cl}^{\to} (L)$ を任意に取ると， $sup_{L} (S) \leq u$ より
${sup}_{L} (S)^{*} \leq u^{*} = u$
が成り立つから， ${sup}_{L} (S)^{*}$ は $S$ の上界の最小元であり $sup_{{Cl}^{\to} (L)} (S) = sup_{L} (S)^{*}$ を得る．
下限については， $inf_{L} (S) \in {Cl}^{\to} (L)$ であることを示せばよい．任意の $x \in S$ に対して， $inf_{L} (S) \leq x$ より $inf_{L} (S)^{*} \leq x^{*} = x$ が成り立つ（ $x \in S \subset {Cl}^{\to} (L)$ に注意）．よって $inf_{L} (S)^{*}$ は $L$ における $S$ の下界だから $inf_{L} (S)^{*} \leq inf_{L} (S)$ を得る．

$L = 2^{S}$ ， $Cl (A) = A^{ul}$ に対して上の命題を使えば，次の完備束 $DM (S)$ が得られます．

デデキント・マクニール完備化

半順序集合 $S$ に対して，そのデデキント・マクニール完備化 $DM (S)$ を
$DM (S) := {A \in 2^{S} ∣ A^{ul} = A}$
で定める．

半順序集合 $S$ のデデキント・マクニール完備化 $DM (S)$ は（包含関係に関して）完備束である．

前命題から従う．

半順序集合 $S$ は，そのデデキント・マクニール完備化 $DM (S)$ に埋め込むことができます．
つまり， $x \in S$ と ${x}^{l} \in DM (S)$ を同一視することによって， $S$ を $DM (S)$ の半順序部分集合とみなせます.

$S$ を半順序集合とし，各 $x \in S$ に対して $ι (x) := {x}^{l}$ とおく．

任意の $x \in S$ に対して， $ι (x) \in DM (S)$ が成り立つ．
写像 $ι : S \to DM (S)$ は順序埋め込みである．

既に示した通り ${x}^{l} = {x}^{lul}$ が成り立つから， $ι (x) = ι (x)^{ul}$ である．
既に示した通り， $x, y \in S$ について $x \leq y$ であることと ${x}^{l} \subset {y}^{l}$ であることは同値である．

またデデキント・マクニール完備化 $DM (S)$ は，次の意味で $S$ を含む最小の完備束になっています．

デデキント・マクニール完備化の最小性

半順序集合 $S$ と完備束 $L$ および順序埋め込み $j : S \to L$ に対して， $j = j^{'} \circ ι$ を満たす順序埋め込み $j^{'} : DM (S) \to L$ が存在する．

写像 $j^{'} : DM (S) ∋ A \mapsto sup_{L} (j^{\to} (A)) \in L$ が所望の性質を満たすことを確認する．まず任意の $x \in S$ に対して，下記2点より $j (x) = (j^{'} \circ ι) (x)$ が成り立つ．

任意の $y \in ι (x)$ に対して $y \leq x$ より $j (y) \leq j (x)$ が成り立つから， $j (x)$ は $j^{\to} (ι (x))$ の上界である．
反射律 $x \in ι (x)$ より $j (x) \in j^{\to} (ι (x))$ であることを踏まえると， $j^{\to} (ι (x))$ の任意の上界 $u \in L$ に対して $j (x) \leq u$ が成り立つ．

また，下記2点より $j^{'}$ は順序埋め込みである．

$A, B \in DM (S)$ が $A \subset B$ を満たすとき， $j^{\to} (A) \subset j^{\to} (B)$ より $j^{'} (A) \leq j^{'} (B)$ である．
$A, B \in DM (S)$ が $j^{'} (A) \leq j^{'} (B)$ を満たすとし， $a \in A$ と $u \in B^{u}$ を任意に取る．このとき $j$ の単調増加性より $j (u)$ は $j^{\to} (B)$ の上界となるので
$j (a) \leq {sup}_{L} (j^{\to} (A)) = j^{'} (A) \leq j^{'} (B) = {inf}_{L} (j^{\to} (B)^{u}) \leq j (u)$
より $a \leq u$ が成り立ち， $a \in B^{ul} = B$ である．

半順序集合 $S$ とその部分集合 $A \in DM (S)$ に対して
$A = ⋃ ι^{\to} (A) = ⋂ ι^{\to} (A^{u})$
が成り立つことを示せ．

次の2式を示せば十分．

$A \subset ⋃ ι^{\to} (A) \subset A^{ul}$ .
$a \in A$ のとき，反射律より $a \in ι (a)$ が成り立つから $a \in ⋃ {ι (a^{'}) ∣ a^{'} \in A} = ⋃ ι^{\to} (A)$ である．また $x \in ⋃ ι^{\to} (A)$ のとき， $x \in ι (a)$ を満たす $a \in A$ が存在する．このとき任意の $u \in A^{u}$ に対して $x \leq a \leq u$ が成り立つから， $x \in A^{ul}$ となる．
$A \subset ⋂ ι^{\to} (A^{u}) \subset A^{ul}$ .
$a \in A$ のとき，任意の $u \in A^{u}$ に対して $a \leq u$ より $a \in ι (u)$ が成り立つから
$a \in ⋂ {ι (u) ∣ u \in A^{u}} = ⋂ ι^{\to} (A^{u})$
である．また $x \in ⋂ ι^{\to} (A^{u})$ のとき，任意の $u \in A^{u}$ に対して $x \in ι (u)$ より $x \leq u$ が成り立つから， $x \in A^{ul}$ となる．

$S, T$ を半順序集合とし， $f : S \to T$ を単調増加写像とする．このとき，ある単調増加写像 $DM (f) : DM (S) \to DM (T)$ が存在して，任意の $x \in S$ に対して
$DM (f) ({s \in S ∣ s \leq x}) = {t \in T ∣ t \leq f (x)}$
が成り立つことを示せ．

解答例

（デデキント・マクニール完備化の最小性の証明で「 $j$ が順序を反映すること」は「 $j^{'}$ が順序を反映すること」を示すためにしか使わなかったことに注意して， $j = ι_{T} \circ f$ に対して同じ議論をすればよい．）

$ι_{S} : S ∋ x \mapsto {s \in S ∣ s \leq x} \in DM (S)$ ， $ι_{T} : T ∋ y \mapsto {t \in T ∣ t \leq y} \in DM (T)$ とし，
$DM (f) (A) := {sup}_{DM (T)} ((ι_{T} \circ f)^{\to} (A))$
で定める写像 $DM (f) : DM (S) \to DM (T)$ が所望の性質を満たすことを確認する．

$x \in S$ を任意に取る．このとき任意の $s \in ι_{S} (x)$ に対して
$(ι_{T} \circ f) (s) \leq (ι_{T} \circ f) (x)$
が成り立つことに注意すれば
$\begin{aligned} DM (f) (ι_{S} (x)) & = {sup}_{DM (T)} ((ι_{T} \circ f)^{\to} (ι_{S} (x))) \\ = (ι_{T} \circ f) (x) . \end{aligned}$
$A \subset B$ を満たす $A, B \in DM (S)$ を任意に取る．このとき
$(ι_{T} \circ f)^{\to} (A) \subset (ι_{T} \circ f)^{\to} (B)$
より $DM (f) (A) \subset DM (f) (B)$ を得る．

例

N

のデデキント・マクニール完備化

$DM (N)$ は $N \cup {\infty}$ と順序同型である．（ $Q, N \cup {\infty}$ は大小関係によって全順序集合とみなしている）

$N$ の部分集合 $A$ に対して，次のことが成り立つ．

$A$ が上に有界である場合： $A^{u}$ の最小元 $n$ が存在して $A^{ul} = {0, 1, \dots, n}$ が成り立つ．
$A$ が上に有界でない場合： $A^{ul} = \emptyset^{l} = N$ が成り立つ．

したがって $DM (N) = {{0, 1, \dots, n} ∣ n \in N} \cup {N}$ である．すると，次の写像 $j : N \cup {\infty} \to DM (N)$ は明らかに順序同型である．
$j (n) := {\begin{cases} {0, 1, \dots, n} & (n \in N), \\ N & (n = \infty) . \end{cases}$

Q

のデデキント・マクニール完備化

$DM (Q)$ は $\overset{―}{R} = R \cup {- \infty, \infty}$ と順序同型である．（ $Q, \overset{―}{R}$ は大小関係によって全順序集合とみなしている）

順序埋め込み $ι : Q ∋ x \mapsto (- \infty, x] \cap Q \in DM (Q)$ と包含写像 $j : Q \to \overset{―}{R}$ に対して， $j = j^{'} \circ ι$ を満たす順序埋め込み $j^{'} : DM (Q) \to \overset{―}{R}$ が存在し，この $j^{'}$ の全射性が次のように示せる．

$y \in R$ を任意に取り， $A := (- \infty, y] \cap Q$ とおく．このとき $Q$ の稠密性より
$A^{ul} = ([y, \infty) \cap Q)^{l} = (- \infty, y] \cap Q = A$
が成り立つから， $A \in DM (Q)$ であり拡大実数 $j^{'} (A) \in \overset{―}{R}$ を考えることができる． $y = j^{'} (A)$ を示すため $ε \in (0, \infty)$ を任意に取ると， $y - ε < x_{-} \leq y \leq x_{+} < y + ε$ を満たす有理数 $x_{-}, x_{+} \in Q$ が存在し， $j^{'}$ が順序埋め込みであることから
$y - ε < x_{-} = j^{'} ((- \infty, x_{-}] \cap Q) \leq j^{'} (A) \leq j^{'} ((- \infty, x_{+}] \cap Q) = x_{+} < y + ε$
が成り立つ．よって $ε$ の任意性より $y = j^{'} (A)$ を得る．
$\emptyset^{ul} = Q^{l} = \emptyset$ より $\emptyset \in DM (Q)$ であることに注意すると，拡大実数 $j^{'} (\emptyset) \in \overset{―}{R}$ を考えることができる．ところで $j^{'}$ は順序埋め込みだから，任意の有理数 $x \in Q$ に対して
$x = j (x) = j^{'} ((- \infty, x] \cap Q) \geq j^{'} (\emptyset)$
が成り立ち， $j^{'} (\emptyset) = - \infty$ を得る．同様にして $j^{'} (Q) = \infty$ も成り立つ．

他にも簡単な例をいくつか挙げておきます．
（どのような半順序を考えているか説明するのは大変なので，ハッセ図で済ませます．）

反鎖

デデキント・マクニール完備化によって最大元と最小元が増えた

反鎖のデデキント・マクニール完備化

2個以上の元をもつ集合 $S$ を等号 $=$ によって半順序集合とみなす．このとき，デデキント・マクニール完備化 $DM (S)$ は $S \cup {⊥, ⊤}$ と順序同型であることを示せ．ただし， $⊥, ⊤$ は $S$ に属さないある元であり， $S \cup {⊥, ⊤}$ は次の半順序
$x \leq y ⟺ x = ⊥ または y = ⊤ または x = y$
によって $S$ を含む半順序集合とみなしている．