閉包系の交叉が閉包系になる十分条件

[⇒]
$P$を鎖完備な半順序集合とする。
$(S_i)_{i \in I}$を$P$上の閉包系の族とする。
$(\cl_i)_{i \in I}$を各$S_i$に対応する閉包作用素とする。

$S = \bigcap_{i \in I}S_i$と置く。

$x \in P$を取る。

$↑^Px \cap S$が最小元を持つことを示す。

$A = \{0, 1\}$をアルファベットとし、$P = A^*$を「$0$と$1$からなる有限文字列の全体」とする。(空文字列$\epsilon$も含む)

$P$上の半順序$\le$ を、「接頭辞であること」として定義する。
すなわち、$s \le t$とは、ある文字列$u \in P$が存在して$t = su$となることとする。

この半順序集合 $P$ は、根($\epsilon$)を一番下とする、上に無限に伸びる完全二分木になる。

[$P$は鎖完備でない]
$\indent$$C = \{\epsilon, 0, 00, 000, 0000, \dots \}$と置く。
$\indent$$C$は鎖であるが、上界すら持たず、当然上限も持ちえない。
$\indent$ゆえに $P$ は鎖完備ではない。

[$P$の閉包系は$P$のみである]
$\indent$$P$自身はもちろん閉包系である。

$\indent$$P$の閉包系$S$を取る。
$\indent$$S \neq P$と仮定する。

$\indent$$S \neq P$と仮定すると、ある$x \in P \setminus S$が存在する。
$\indent$$S$は閉包系であるから、定義より$\uparrow^P x \cap S$は最小元を持つ。
$\indent$これを$y$とする。

$\indent$$x \notin S$かつ$y \in S$であるから、$x \neq y$
よって、$x < y$

$\indent$$y$は接頭辞として$x$を持つ文字列であるから、$x$の直後に$0$か$1$のどちらかが続く。

$\indent$[$y \ge x0$の場合]
$\dindent$ここで、二分木のもう一方の枝である $x1$ に注目する。

$\dindent$$x1 \in P$であり、$S$は閉包系だから、同様に $\uparrow^P x1 \cap S$ も最小元を持つ。
$\dindent$$\uparrow^P x1 \cap S$は空ではないから、$z \ge x1$なる$z \in S$が取れる。

$\dindent$この時、$z \ge x1 > x$であるから、$z \in \uparrow^P x \cap S$

$\dindent$$y$は$\uparrow^P x \cap S$の最小元だから、$y \le z$

$\dindent$しかし、$y \ge x0$と$z \ge x1$は最初の分岐が異なるから、一方が他方の接頭辞になることは決してなく、$y$と$z$は比較不能。

$\dindent$これは$y \le z$に矛盾。

$\indent$[$y \ge x1$の場合]
$\dindent$同様に矛盾

$\indent$従って、$S=P$

[$P$の閉包系の任意交叉は閉包系]
$\indent$$P$の閉包系は$P$のみであるから、任意交叉が再び閉包系になる。

$P$を鎖完備な半順序集合とする。

$x \in P$を取る。

$P$の部分集合$S$($S\ \cap ↑^Px \not= \varnothing$)を取る。

$X=\set{z \in P\ |\ x \le z\ \text{かつ}\ \forall s \in ↑^Px \cap S, z \le s}$と置く。

$T \underset{total}{\subset} X$を取る。($T \not= \varnothing$)

$P$は鎖完備だから、$T$は上限$t_0 \in P$を持つ。

[$t_0 \in X$]
[$x \le t_0$]
$T$の適当な元$t$に対し、$x \le t \le t_0$
より、$x \le t_0$

[$\forall s \in ↑^Px \cap S, t_0 \le s$]
$s \in ↑^Px \cap S$を取る。
$s$は$T$の上界。
$t_0$は$T$の最小上界であるから、$t_0 \le s$

従って、$t_0 \in X$

よって、Zornの補題より、$X$は極大元を持つ。

従って、$P$は局所極大条件を満たす。

[⇒]
$x \in P$を取る。
$U \subset ↑^Px$を取る。($U \not= \varnothing$)

$S = U$として局所極大条件を適用すれば、
$X=\set{z \in P\ |\ x \le z\ \text{かつ}\ \forall s \in ↑^Px \cap S, z \le s}$
$=\set{z \in P\ |\ x \le z\ \text{かつ}\ \forall s \in U, z \le s}$
$=↓^PU \cap ↑^Px$
が極大元を持つ。

[⇐]
$x \in P$を取る。
$S \subset P$を取る。($S\ \cap ↑^Px \not= \varnothing$)

$U = ↑^Px \cap S$と置くと、$U \subset ↑^Px$である。

よって仮定より、$↓^P U \cap ↑^P x$
$=\set{z \in P\ |\ x \le z\ \text{かつ}\ \forall s \in ↑^Px \cap S, z \le s}$
は極大元を持つ。

上で作った二分木の例は局所極大条件を満たす。

$x \in P$を取る。
$U \subset ↑^Px$を取る。($U \not= \varnothing$)

$X = ↓^PU \cap ↑^Px$と置く。

[$X$は全順序]
$\indent$$a,b \in X$を取る。
$\indent$適当な$u \in U$に対し$a,b \le u$であるから、$P$の構造的に、$a$と$b$は比較可能。

$U$の元の文字長の最小値を$n$とする。

$X$に最大元が無いと仮定すると、より大きい元を$X$の中から取り続けられる。
これを有限回続けることで、いつか長さ$n$を超える元$z$を$X$から取れる。
しかし、これは$z$は$U$の文字長$n$の元の下界ではないことを言っていて、それは$X \subset ↓^PU \cap ↑^Px$に矛盾。

従って、$X$は最大元(極大元)を持つ。