閉包作用素と閉包系(Moore集合)
自分用のノート
数学において××を含む最小の○○というのを考えることはよくある。
そのようなものは閉包と呼ばれ、閉包を取る写像は閉包作用素と呼ばれる。
閉包作用素が複数ある場合、それらの順番を入れ替えても良いかは気になる所である。
定義
半順序集合$P$上の閉包作用素とは以下を満たす写像のこと。
- $\cl:P→P$
- $a \le \cl(a)$ (拡大律)
- $a \le b ⇒ \cl(a) \le \cl(b)$ (単調律)
- $\cl(\cl(a)) = \cl(a)$ (冪等律)
$\cl(a)$を$\cl$による$a$の閉包と呼ぶ。
$\cl(a) = a$なる$a \in P$を、$\cl$による閉元と呼ぶ。
$P$の$\cl$による閉元全体を$P^{\cl}$と書く。
半順序集合$P$上の開核作用素とは以下を満たす写像のこと。
- $\mathrm{in}:P→P$
- $\mathrm{in}(a) \le a$ (縮小律)
- $a \le b ⇒ \mathrm{in}(a) \le \mathrm{in}(b)$ (単調律)
- $\mathrm{in}(\mathrm{in}(a)) = \mathrm{in}(a)$ (冪等律)
$\In(a)$を$\In$による$a$の開核と呼ぶ。
$\In(a) = a$なる$a \in P$を、$\In$による開元と呼ぶ。
$P$の$\In$による開元全体を$P^{\In}$と書く。
$\cl,\In$は冪等性を持つため、
- $\cl(P) = P^{\cl}$
- $\In(P) = P^\In$
が成り立つ。
[証明]
[$\cl(P) = P^{\cl}$]
[$\subset$]
$p \in \cl(P)$を取る。
$p = \cl(q)$と表せる。($q \in P$)
この時、$\cl(p) = \cl(\cl(q)) = \cl(q) = p$であるから、$p \in P^\cl$
[$\supset$]
$p \in P^\cl$を取る。
$p = \cl(p)$と表せるから、$p \in \cl(P)$
半順序集合$P$と$S \subset P$に対し、
$S$が閉包系(Moore集合)であるとは、任意の$x \in P$に対し、$↑^Px \cap S$が最小元を持つことを言う。
$S$が開核系(余Moore集合)であるとは、任意の$x \in P$に対し、$↓^Px \cap S$が最大元を持つことを言う。
完備束においては、
$S$が閉包系 ⇔ $S$の任意の部分集合の下限が$S$に入っている
$S$が開核系 ⇔ $S$の任意の部分集合の上限が$S$に入っている
[$S$が閉包系 ⇔ $S$の任意の部分集合の下限が$S$に入っている]
[⇒]
$A \subset S$を取る。
$a = \bigwedge A$と置く。
$m=\min(↑^La \cap S)$と置く。
任意の$x \in A$に対し、$a \le x$かつ$x \in S$であるから、$x \in ↑^La \cap S$
よって、$m \le x$
ゆえに、$m$は$A$の下界
従って、$m \le a$
一方、$m \in ↑^La \cap S$だから、$a \le m$
従って、$a=m \in S$
ゆえに$\bigwedge A \in S$
[⇐]
$x \in L$を取る。
$\bigwedge(↑^Lx \cap S) \in S$であるから、この下限は最小元。
[$S$が開核系 ⇔ $S$の任意の部分集合の上限が$S$に入っている]
略
(特に$P$が何かのべき集合の時にMoore集合族と呼ばれる。)
半順序集合$P$上の閉包作用素$\cl$と$x \in P$に対し、
$\cl(x) = \min(↑^Px \cap P^{\cl})$
証明
[$\cl(x) \in ↑^Px \cap P^\cl$]
$x \le \cl(x)$より、$\cl(x) \in ↑^Px$
$\cl(\cl(x)) = \cl(x)$より、$\cl(x) \in P^\cl$
[$\cl(x)$は$↑^Px \cap P^\cl$の下界]
$c \in ↑^Px \cap P^\cl$を取る。
$c \in P^\cl$だから、$\cl(c) = c$
$c \in ↑^Px$より、$x \le c$だから、$\cl(x) \le \cl(c) = c$
半順序集合$P$上の開核作用素$\In$と$x \in P$に対し、
$\In(x) = \max(↓^Px \cap P^\In)$
証明
[$\In(x) \in ↓^Px \cap P^\In$]
$\In(x) \le x$より、$\In(x) \in ↓^Px$
$\In(\In(x)) = \In(x)$より、$\In(x) \in P^\In$
[$\In(x)$は$↓^Px \cap P^\In$の上界]
$c \in ↑^Px \cap P^\In$を取る。
$c \in P^\In$だから、$\cl(c) = c$
$c \in ↓^Px$より、$c \le x$だから、$\In(x) \ge \In(c) = c$
半順序集合$P$が閉包作用素$\cl$を持つとき、$P^\cl$は閉包系であり、
逆に$P$の閉包系$M$に対し、$M=P^\cl$となる閉包作用素$\cl$がただ一つ存在する。
[$P^\cl$は閉包系]
半順序集合$P$上の閉包作用素を$\cl$とする。
任意の$x \in P^\cl$に対し、$↑^Px \cap P^\cl$が最小元を持つことを示せばよい。
$\cl(x) = \min(↑^Px \cap P^\cl)$であるから、これが最小値。
[閉包系$M$から閉包作用素$\cl$を構成する]
閉包系$M \subset P$が与えられたとする。
写像 $\cl: P \to P$ を以下のように定義する。
$\cl(x) := \min(↑^Px \cap M)$
これが閉包作用素の3条件を満たし、かつ$P^\cl = M$となることを示す。
[閉包作用素]
[拡大性]
$x \in P$を取る。
$\min(↑^Px \cap M) \in ↑^Px \cap M$であるから、
$x \le \min(↑^Px \cap M) = \cl(x)$
[単調性]
$x \le y$ とすると、$↑^Px \supset ↑^Py$
よって、$\min(↑^Px \cap M) \le \min(↑^Py \cap M)$
従って、$\cl(x) \le \cl(y)$
[冪等性]
$x \in P$を取る。
$\cl(\cl(x)) = \min(↑^P\cl(x) \cap M)$であり、
$\cl(x) \le \cl(x)$かつ$\cl(x) \in M$であるから、$\cl(x) \in ↑^P\cl(x) \cap M$である。
よって、$↑^P\cl(x) \cap M$の最小元は$\cl(x)$
従って、$\cl(\cl(x)) = \cl(x)$
[$P^\cl = M$]
[$\supset$]
$x \in M$を取る。
$x \in ↑^Lx$であり、$x$は$↑^Lx$の最小元。
従って、$\cl(x) = x$ となり、$x \in P^\cl$
[$\subset$]
$x \in P^\cl$を取る。
$\cl(x) = x$である。
$\cl(x) \in M$であるから、$x = \cl(x) \in M$ となる。
[$P^{\cl}=P^{\cl'} ⇒ \cl=\cl'$]
$P^{\cl}=P^{\cl'}$とする。
任意の$x \in L$に対し、
$\cl(x)=\min(↑^Px \cap P^{\cl})=\min(↑^Px \cap P^{\cl'})=\cl'(x)$
開核作用素についても同様。
従って半順序集合上で、閉包作用素と閉包系、開核作用素と開核系は一対一に対応する。
完備束$L$の閉包系の族$(A_i)_{i \in I}$に対し、$\bigcap_{i \in I}A_i$も$L$の閉包系である。
完備束$L$の開核系の族$(A_i)_{i \in I}$に対し、$\bigcap_{i \in I}A_i$も$L$の開核系である。
[Moore]
$(x_j)_{j \in J} \subset L$を取る。
全ての$i \in I$に対し、$(x_j)_{j \in J} \subset A_i$であるから、
全ての$i \in I$に対し、$\bigwedge_{j \in J}x_i \in A_i$
従って、$\bigwedge_{j \in J}x_i \in \bigcap_{i \in I}A_i$
[余Moore]
略
半順序集合に関してはどうなのだ?
必ずしも成り立たない。
https://mathlog.info/articles/Eg39AIgnaorvpXRBmYMC
可換条件
完備束$L$の閉包系$A,B$を取る。$C=A \cap B$と置くと、$C$も閉包系である。
それらに対応する閉包作用素を$\cl_A,\cl_B,\cl_C$と置く。
$\cl_A\cl_B = \cl_B\cl_A = \cl_C$となるのはどのような時だろうか?
完備束$L$の閉包系$A,B$を取る。
$A$が$B$を保つとは、$\forall b \in B, \cl_A(b) \in B$が成り立つこと。
($\cl_A(B) \subset B$が成り立つこと)
完備束$L$の閉包系$A,B$を取る。
$A$が$B$を保つ ⇔ $\cl_A\cl_B = \cl_{A \cap B}$
[⇒]
$x \in L$を取る。
$z = \cl_A(\cl_B(x))$と置く。
$z = \min(↑^Lx \cap A \cap B)$を示せばよい。
[$x \le z$]
$x \le \cl_B(x) \le \cl_A(\cl_B(x)) = z$
[$z \in A \cap B$]
$\cl_B(x) \in B$であり、$A$は$B$を保つから、$\cl_A(\cl_B(x)) \in B$
また、$\cl_A(\cl_B(x)) \in A$でもある。
従って、$z \in A \cap B$
[$z$は$↑^Lx \cap A \cap B$の下界]
$w \in ↑^Lx \cap A \cap B$を取る。
$x \le w$であるから、$\cl_B(x) \le \cl_B(w) = w$
よって、$z =\cl_A(\cl_B(x)) \le \cl_A(w) = w$
中から下界を取ってきたので、$z$は$↑^Lx \cap A \cap B$の最小元。
[⇐]
$y \in B$を取る。
$\cl_B(y) = y$であるから、$\cl_A(\cl_B(y)) = \cl_A(y)$
仮定より、$\cl_{A \cap B}(y) = \cl_A(y)$
$\cl_{A \cap B}(y) \in A \cap B \subset B$である。
よって、任意の$B$の元を$\cl_A$で送ると、$B$に入っている。
即ち、$A$は$B$を保つ。
2つの閉包作用素の合成は必ずしも閉包作用素にならない。
反例
拡大律と単調律は満たされるが冪等律が成り立たない。
$L = \{1, 2, 3, 4, 5\}$と置く。$L$は完備束である。
$\cl_1:1 \to 2, \quad 2 \to 2, \quad 3 \to 4, \quad 4 \to 4, \quad 5 \to 5$
$\cl_2:1 \to 1, \quad 2 \to 3, \quad 3 \to 3, \quad 4 \to 5, \quad 5 \to 5$
と定めると、これらは閉包作用素。
$\cl = \cl_1\cl_2$とすると、
$\cl(1) = 2 \not= 3 = \cl(\cl(1))$であるから、
これは閉包作用素でない。
完備束$L$の閉包系$A,B$を取る。
$\cl_A\cl_B$が閉包作用素 ⇔ $\cl_A\cl_B = \cl_{A \cap B}$
[$\cl_A\cl_B$が閉包作用素 ⇔ $\cl_A\cl_B = \cl_{A \cap B}$]
[⇐]
明らか。
[⇒]
$L^{\cl_A\cl_B}=A \cap B$を示す。
[$\subset$]
$x \in L^{\cl_A\cl_B}$を取る。
$\cl_A$と$\cl_B$の拡大性より、
$x \le \cl_B(x) \le \cl_A(\cl_B(x)) = x$
従って、$\cl_B(x) = x$
ゆえに、$\cl_A(x) = x$
よって、$x \in A \cap B$
[$\supset$]
$x \in A \cap B$を取る。
この時、$\cl_A(x) = x$かつ$\cl_B(x)=x$である。
よって、$\cl_A(\cl_B(x)) = \cl_A(x) = x$
従って、$x \in L^{\cl_A\cl_B}$
完備束$L$の閉包系$A,B$を取る。
$\cl_A\cl_B$が閉包作用素ならば以下が成り立つ。
- $\cl_A\cl_A\cl_B=\cl_A\cl_B$
- $\cl_B\cl_A\cl_B=\cl_A\cl_B$
証明
$x \in L$を取る。
$\cl_A(\cl_B(x)) \in A \cap B$より、
$\cl_A(\cl_B(x))$は$\cl_A$による閉元でもあり、$\cl_B$による閉元でもある。
従って、
$\cl_A(\cl_A(\cl_B(x)))=\cl_A(\cl_B(x))$
$\cl_B(\cl_A(\cl_B(x)))=\cl_A(\cl_B(x))$
完備束$L$の閉包系$A,B$を取る。
$\cl_A\cl_B$が閉包作用素 ⇔ $\forall x \in L,\ \cl_B(\cl_A(x)) \le \cl_A(\cl_B(x))$
[$\cl_A\cl_B$が閉包作用素 ⇔ $\forall x \in L,\ \cl_B(\cl_A(x)) \le \cl_A(\cl_B(x))$]
[⇒]
$x \in L$を取る。
$x \le \cl_B(x)$である。
$\cl_A$の拡大性より、$\cl_A(x) \le \cl_A(\cl_B(x))$
$\cl_B$の拡大性より、$\cl_B(\cl_A(x)) \le \cl_B(\cl_A(\cl_B(x)))=\cl_A(\cl_B(x))$
[⇐]
冪等律が成り立つことを確認する。
$x \in L$を取る。
$\forall y \in L, \cl_B(\cl_A(y)) \le \cl_A(\cl_B(y))$であるから、$y = \cl_B(x)$として、
$$\cl_B(\cl_A(\cl_B(x))) \le \cl_A(\cl_B(\cl_B(x))) $$
$\cl_A$の単調性より、
$$\cl_A(\cl_B(\cl_A(\cl_B(x)))) \le \cl_A(\cl_A(\cl_B(\cl_B(x)))) = \cl_A(\cl_B(x))$$
また、$\cl_A,\cl_B$の拡大性より、$\cl_A(\cl_B(\cl_A(\cl_B(x)))) \ge \cl_A(\cl_B(x))$だから、
$\cl_A(\cl_B(\cl_A(\cl_B(x)))) = \cl_A(\cl_B(x))$
完備束$L$の閉包系$A,B$を取る。
$\cl_A\cl_B = \cl_B\cl_A ⇒ \cl_A\cl_B = \cl_B\cl_A = \cl_{A \cap B}$
[$A$が$B$を保つ]
$b \in B$を取る。
$B = L^{\cl_B} = \cl_B(L)$だから、
$b = \cl_B(x)$となる$x \in L$が取れる。
$\cl_A(\cl_B(x)) = \cl_B(\cl_A(x)) \in B$であるから、$\cl_A(\cl_B(x)) \in B$
従って、$\cl_A(b) \in B$
応用
二項関係全体の成す束と閉包作用素： https://mathlog.info/articles/9V0pOHnGtSzJ5hN67TXT
この記事を高評価した人
この記事に送られたバッジ
投稿者
