二項関係全体の成す束と閉包作用素
自分用のノート
ある関係を含む最小の同値関係を取ってくることがあった。
それは一体どのような形なのか気になったので整理する。
ちょっと勉強してきたので書き直す。
閉包作用素とMoore集合について：
https://mathlog.info/articles/p9hqeT28X8LfihyNs8Iq
関係全体の成す完備束
集合$X$上の二項関係を$\mathcal{P}(X \times X)$の元として実装する。
$R \in \mathcal{P}(X \times X)$、$a,b \in X$に対し、$a R b :⇔ (a,b) \in R$
$X$上の二項関係全体$\mathcal{P}(X \times X)$を$R(X)$と書くことにする。
$=$も$X$上の二項関係であるが、そのまま書くと読みづらいので、$D=\{(a,a)\ |\ a \in X\}$と書くことにする。
$R(X)$は$\subset$を順序として、完備束となる。
$R(X) = \mathcal{P}(X \times X)$の為。
$1$は全ての物を関係付ける二項関係
$0$は全ての物を無関係にする二項関係
合成とop
二項関係$R$に対し、$R^{op} := \{(b,a)\ |\ (a,b) \in R\}$と定義する。
$D^{op}=D$
$X$上の二項関係$R_0,R_1$に対し、その合成を以下で定義する。
$R_0 \circ R_1 := \{(a,c) \in X \times X\ |\ \exists b \in X; (a,b) \in R_1 \ \text{かつ}\ (b,c) \in R_0 \}$
$R \circ R$を$R^2$と書く。
$R^0 = D$とする。
関係の合成は結合律が成り立つ。
$S \subset R$の時、$S^{op} \subset R^{op}$
$(a,b) \in S^{op}$を取ると、$(b,a) \in S \subset R$であるから、$(a,b) \in R^{op}$
$S \subset R$かつ$S' \subset R'$の時、$S \circ S' \subset R \circ R'$
$(a,b) \in S \circ S'$を取る。
ある$c \in X$が存在し、$(a,c) \in S'$かつ$(c,b) \in S$
$S' \subset R'$より$(a,c) \in R'$、$S \subset R$より$(c,b) \in R$
従って、$(a,b) \in R \circ R'$
$(R_0 \circ R_1)^{op} = R_1^{op} \circ R_0^{op}$
[$(R_0 \circ R_1)^{op} = R_1^{op} \circ R_0^{op}$]
[$\subset$]
$(a,b) \in (R_0 \circ R_1)^{op}$を取る。
$(b,a) \in R_0 \circ R_1$より、ある$c \in X$が存在し、$(b,c) \in R_1$かつ$(c,a) \in R_0$
即ち、$(c,b) \in R_1^{op}$かつ$(a,c) \in R_0^{op}$
従って、$(a,b) \in R_1^{op} \circ R_0^{op}$
[$\supset$]
$(a,b) \in R_1^{op} \circ R_0^{op}$を取る。
ある$c \in X$が存在し、$(a,c) \in R_0^{op}$かつ$(c,b) \in R_1^{op}$
即ち、$(c,a) \in R_0$かつ$(b,c) \in R_1$
よって、$(b,a) \in R_0 \circ R_1$
従って、$(a,b) \in (R_0 \circ R_1)^{op}$
$R \circ D = R = D \circ R$
[$R \circ D = R$]
[$\subset$]
$(x, z) \in R \circ D$を取る。
関係の合成の定義より、ある $y \in X$ が存在して、
$$(x, y) \in D \land (y, z) \in R$$
ここで $D$ の定義より、$(x, y) \in D \implies x = y$ であるから、
$$(x, z) \in R$$
従って、$R \circ D \subset R$
[$\supset$]
$(x, z) \in R$を取る。
$(x, x) \in D$であるから、$y = x$とすると、
$$(x, y) \in D \land (y, z) \in R$$
関係の合成の定義より、
$$(x, z) \in R \circ D$$
従って、$R \subset R \circ D$
[$D \circ R = R$]
[$\subset$]
$(x, z) \in D \circ R$を取る。
関係の合成の定義より、ある $y \in X$ が存在して、
$$(x, y) \in R \land (y, z) \in D$$
ここで $D$ の定義より、$(y, z) \in D \implies y = z$ であるから、
$$(x, z) \in R$$
従って、$D \circ R \subset R$
[$\supset$]
$(x, z) \in R$を取る。
$(z, z) \in D$であるから、$y = z$とすると、
$$(x, y) \in R \land (y, z) \in D$$
関係の合成の定義より、
$$(x, z) \in D \circ R$$
従って、$R \subset D \circ R$
$D^n = D$
二項関係の族$(R_i)_{i \in I} \subset R(X)$に対し、
$$ \bigg(\bigcap_{i \in I}R_i \bigg)^{op} = \bigcap_{i \in I}R_i^{op} $$
$$ \bigg(\bigcup_{i \in I}R_i \bigg)^{op} = \bigcup_{i \in I}R_i^{op} $$
[$ \bigg(\bigcap_{i \in I}R_i \bigg)^{op} = \bigcap_{i \in I}R_i^{op} $]
[$\subset$]
$(a,b) \in \bigg(\bigcap_{i \in I}R_i \bigg)^{op}$を取る。
$(b,a) \in \bigcap_{i \in I}R_i$である。
よって、全ての$i \in I$に対し、$(b,a) \in R_i$
即ち、全ての$i \in I$に対し、$(a,b) \in R_i^{op}$
従って、$(a,b) \in \bigcap_{i \in I}R_i^{op}$
[$\supset$]
$(a,b) \in \bigcap_{i \in I}R_i^{op}$を取る。
全ての$i \in I$に対し、$(a,b) \in R_i^{op}$である。
よって、全ての$i \in I$に対し、$(b,a) \in R_i$
即ち、$(b,a) \in \bigcap_{i \in I}R_i$
従って、$(a,b) \in \bigg(\bigcap_{i \in I}R_i \bigg)^{op}$
[$ \bigg(\bigcup_{i \in I}R_i \bigg)^{op} = \bigcup_{i \in I}R_i^{op} $]
[$\subset$]
$(a,b) \in \bigg(\bigcup_{i \in I}R_i \bigg)^{op}$を取る。
$(b,a) \in \bigcup_{i \in I}R_i$である。
よって、ある$i \in I$が存在し、$(b,a) \in R_i$
即ち、ある$i \in I$が存在し、$(a,b) \in R_i^{op}$
従って、$(a,b) \in \bigcup_{i \in I}R_i^{op}$
[$\supset$]
$(a,b) \in \bigcup_{i \in I}R_i^{op}$を取る。
ある$i \in I$が存在し、$(a,b) \in R_i^{op}$である。
よって、ある$i \in I$が存在し、$(b,a) \in R_i$
即ち、$(b,a) \in \bigcup_{i \in I}R_i$
従って、$(a,b) \in \bigg(\bigcup_{i \in I}R_i \bigg)^{op}$
従って、$\cdot^{op}$は$R(X)$の自己完備束同型になっている。
二項関係の族$(R_i)_{i \in I} \subset R(X)$と二項関係$R$に対し、
$$ \bigg(\bigcap_{i \in I}R_i \bigg) \circ R \subset \bigcap_{i \in I}(R_i\circ R) $$
$$ R \circ \bigg(\bigcap_{i \in I}R_i \bigg) \subset \bigcap_{i \in I}(R \circ R_i) $$
$$ \bigg(\bigcup_{i \in I}R_i \bigg) \circ R = \bigcup_{i \in I}(R_i \circ R) $$
$$ R \circ \bigg(\bigcup_{i \in I}R_i \bigg) = \bigcup_{i \in I}(R \circ R_i) $$
[$\bigg(\bigcap_{i \in I}R_i \bigg) \circ R \subset \bigcap_{i \in I}(R_i \circ R)$]
$(a,b) \in \bigg(\bigcap_{i \in I}R_i \bigg) \circ R$を取る。
この時、ある$c \in X$が存在し、$(c,b) \in \bigcap_{i \in I}R_i$かつ$(a,c) \in R$
全ての$i \in I$に対し、$(c,b) \in R_i$
即ち、全ての$i \in I$に対し、$(c,b) \in R_i$かつ$(a,c) \in R$
即ち、全ての$i \in I$に対し、$(a,b) \in R_i \circ R$
従って、$(a,b) \in \bigcap_{i \in I}(R_i \circ R)$
[$R \circ \bigg(\bigcap_{i \in I}R_i \bigg) \subset \bigcap_{i \in I}(R \circ R_i)$]
$(a,b) \in R \circ \bigg(\bigcap_{i \in I}R_i \bigg)$を取る。
この時、ある$c \in X$が存在し、$(c,b) \in R$かつ$(a,c) \in \bigcap_{i \in I}R_i$
全ての$i \in I$に対し、$(a,c) \in R_i$
即ち、全ての$i \in I$に対し、$(c,b) \in R$かつ$(a,c) \in R_i$
即ち、全ての$i \in I$に対し、$(a,b) \in R \circ R_i$
従って、$(a,b) \in \bigcap_{i \in I}(R \circ R_i)$
[$\bigg(\bigcup_{i \in I}R_i \bigg) \circ R = \bigcup_{i \in I}(R_i \circ R)$]
[$\subset$]
$(a,b) \in \bigg(\bigcup_{i \in I}R_i \bigg) \circ R$を取る。
ある$c \in X$が存在し、$(c,b) \in \bigcup_{i \in I}R_i$かつ$(a,c) \in R$
ある$i \in I$が存在し、$(c,b) \in R_i$かつ$(a,c) \in R$
即ち、ある$i \in I$が存在し、$(a,b) \in R_i \circ R$
従って、$(a,b) \in \bigcup_{i \in I}(R_i \circ R)$
[$\supset$]
$(a,b) \in \bigcup_{i \in I}(R_i\circ R)$を取る。
ある$i \in I$が存在し、$(a,b) \in R_i \circ R$
即ち、ある$c \in X$が存在し、$(c,b) \in R_i$かつ$(a,c) \in R$
$(c,b) \in R_i \subset \bigcup_{i \in I}R_i$かつ$(a,c) \in R$
従って、$(a,b) \in \bigg(\bigcup_{i \in I}R_i \bigg) \circ R$
[$R \circ \bigg(\bigcup_{i \in I}R_i \bigg) = \bigcup_{i \in I}(R \circ R_i)$]
[$\subset$]
$(a,b) \in R \circ \bigg(\bigcup_{i \in I}R_i \bigg)$を取る。
ある$c \in X$が存在し、$(c,b) \in R$かつ$(a,c) \in \bigcup_{i \in I}R_i$ ある$i \in I$が存在し、$(c,b) \in R$かつ$(a,c) \in R_i$ 即ち、ある$i \in I$が存在し、$(a,b) \in R \circ R_i$
従って、$(a,b) \in \bigcup_{i \in I}(R \circ R_i)$
[$\supset$]
$(a,b) \in \bigcup_{i \in I}(R \circ R_i)$を取る。
ある$i \in I$が存在し、$(a,b) \in R \circ R_i$
即ち、ある$c \in X$が存在し、$(c,b) \in R$かつ$(a,c) \in R_i$ $(a,c) \in R_i \subset \bigcup_{i \in I}R_i$かつ$(c,b) \in R$
従って、$(a,b) \in R \circ \bigg(\bigcup_{i \in I}R_i \bigg)$
[反例：$\bigg(\bigcap_{i \in I}R_i \bigg) \circ R \subsetneq \bigcap_{i \in I}(R_i\circ R)$となる例]
$X = \{1,2,3\}$、$I = \{1,2\}$とし、
$$R_1 = \{(1,1)\},\quad R_2 = \{(2,1)\},\quad R = \{(1,3),(2,3)\}$$
とする。
$$\xymatrix{ R_1: & & 1 \ar@(ul,ur)[] & & R_2: & & 1 & & R: & & 1 \ar@{->}[rdd] & \\ & & & & & & & & & & & \\ & 2 & & 3 & & 2 \ar@{->}[ruu] & & 3 & & 2 \ar@{->}[rr] & & 3 }$$
左辺：
$R_1 \cap R_2 = \emptyset$より、
$$\bigg(\bigcap_{i \in I}R_i\bigg) \circ R = \emptyset \circ R = \emptyset$$
右辺：
$R_1 \circ R$を計算する。
$(c,b) \in R_1$かつ$(a,c) \in R$となるのは$c=1,\ a=1,\ b=3$のみ。
よって$R_1 \circ R = \{(1,3)\}$
$R_2 \circ R$を計算する。
$(c,b) \in R_2$かつ$(a,c) \in R$となるのは$c=2,\ a=1,\ b=3$のみ。
よって$R_2 \circ R = \{(1,3)\}$
従って、
$$\bigcap_{i \in I}(R_i \circ R) = \{(1,3)\} \cap \{(1,3)\} = \{(1,3)\}$$
以上より、
$$\emptyset = \bigg(\bigcap_{i \in I}R_i\bigg) \circ R \subsetneq \bigcap_{i \in I}(R_i \circ R) = \{(1,3)\}$$
従って、関係$R$を合成することは、$R(X)$上の自己完備上半束準同型になっている。
$R(X)$のMoore集合
$R$が反射関係とは、全ての$a \in X$に対し、$aRa$であること。
$R$が推移関係とは、$aRb$かつ$bRc⇒ aRc$であること。
$R$が対称関係とは、$aRb ⇒ bRa$であること。
$R$が反対称関係とは、$aRb$かつ$bRa ⇒ a=b$であること。
$R$が前順序関係とは、反射関係かつ推移関係であること。
$R$が半順序関係とは、反射関係かつ推移関係かつ反対称関係であること。
$R$が同値関係とは、反射関係かつ推移関係かつ対称関係であること。
$1$は反対称律と半順序律以外全てを満たし、$0$は推移/対称/反対称を満たす。
($X$が空集合なら全て満たす。)
反射律・推移律・対称律は共通部分を取る操作で保たれる。
[証明]
[反射律]
$(R_i)_{i \in I}$を反射関係の族とする。
全ての$i \in I$に対し、$R_i$は反射律を満たすので、$(a,a) \in R_i$
よって、$(a,a) \in \bigcap_{i \in I}R_i$
[推移律]
$(R_i)_{i \in I}$を推移関係の族とする。
$(a,b),(b,c) \in \bigcap_{i \in I}R_i$を取る。
全ての$i \in I$に対し、$(a,b),(b,c) \in R_i$である。
$R_i$は推移律を満たすので、全ての$i \in I$に対し、$(a,c) \in R_i$
従って、$(a,c) \in \bigcap_{i \in I}R_i$
[対称律]
$(R_i)_{i \in I}$を対称関係の族とする。
$(a,b) \in \bigcap_{i \in I}R_i$を取る。
全ての$i \in I$に対し、$(a,b) \in R_i$である。
$R_i$は対称律を満たすので、全ての$i \in I$に対し、$(b,a) \in R_i$
従って、$(b,a) \in \bigcap_{i \in I}R_i$
上の命題から、反射関係(resp.推移関係、対称関係)全体は$R(X)$のMoore集合になることが分かる。
$X$上の反射関係全体・推移関係全体・対称関係全体をそれぞれ$\R,\T,\S$と置く。
$\R \cap \T$は前順序関係全体の成すMoore集合、$\R \cap \T \cap \S$は同値関係全体の成すMoore集合である。
疑問なのは、$\cl_\R\cl_\T = \cl_\T\cl_\R = \cl_{\R \cap \T}$か? とかである。
関係の特徴付け
$R$が反射律を満たす ⇔ $D \subset R$
$R$が推移律を満たす ⇔ $R^2 \subset R$ ⇔ $\forall n \in \mathbb{N}_{\ge 1},\ R^n \subset R$
$R$が対称律を満たす ⇔ $R^{op} \subset R$ ⇔ $R^{op} = R$
$R$が反対称律を満たす ⇔ $R \cap R^{op} \subset D$
[$R$が反射律を満たす ⇔ $D \subset R$]
[⇒]
$(a,a) \in D$をとる。
$R$は反射律を満たすから、$(a,a) \in R$
[⇐]
$a \in X$を取ると、$(a,a) \in D \subset R$
[$R$が推移律を満たす ⇔ $R^2 \subset R$]
[⇒]
$(a,c) \in R^2$を取る。
ある$b \in X$が存在して、$(a,b) \in R$かつ$(b,c) \in R$である。
$R$は推移関係だから、$(a,c) \in R$
[⇐]
$(a,b) \in R$かつ$(b,c) \in R$とする。
この時、合成の定義より、$(a,c) \in R^2$だから、$(a,c) \in R$
[$R^2 \subset R ⇔ \forall n \in \mathbb{N}_{\ge 1},\ R^n \subset R$]
[⇐]
自明
[⇒]
[$n=1$の時]
$R \subset R$
[$k< n$で成り立つなら$n$で成り立つ]
$R^{n-1} \subset R$であり、合成は順序を保つから、$R^n \subset R^2$
よって、$R^n \subset R$
数学的帰納法より、$\forall n \in \mathbb{N}_{\ge 1},\ R^n \subset R$
[$R$が対称律を満たす ⇔ $R^{op} \subset R$]
[⇒]
$(a,b) \in R^{op}$を取ると、$(b,a) \in R$であり、$R$は対称律を満たすから、$(a,b) \in R$
[⇐]
$(a,b) \in R$とすると、$(b,a) \in R^{op}$であり、よって、$(b,a) \in R$
[$R^{op} \subset R$ ⇔ $R^{op} = R$]
[⇐]
自明
[⇒]
$(a,b) \in R$を取ると、$(b,a) \in R^{op} \subset R$
よって、$(a,b) \in R^{op}$
[$R$が反対称律を満たす ⇔ $R \cap R^{op} \subset D$]
[⇒]
$(a,b) \in R \cap R^{op}$を取る。
$(a,b) \in R^{op}$だから、$(b,a) \in R$
$R$は反対称関係だから、$a=b$
よって、$(a,b) \in D$
[⇐]
$(a,b) \in R$かつ$(b,a) \in R$とすると、$(a,b) \in R \cap R^{op}$
よって、$(a,b) \in D$
従って、$a=b$
$\cl_\R(R) = R \cup D$
$\cl_\T(R) = \bigcup_{n \in \mathbb{N}_{\ge 1}}R^n$
$\cl_\S(R) = R \cup R^{op}$
[$\cl_\R(R) = R \cup D$]
[$\subset$]
$R \cup D$は反射関係であり、$R$を含む。
$R$を含む最小の反射関係が$\cl_\R(R)$だから、
$\cl_\R(R) \subset R \cup D$
[$\supset$]
$\cl_\R(R)$は$R$を含み、反射関係であるから$D$も含む。
従って、$\cl_\R(R) \supset R \cup D$
[$\cl_\T(R) = \bigcup_{n \in \mathbb{N}_{\ge 1}}R^n$]
$S = \bigcup_{n \in \mathbb{N}_{\ge 1}}R^n$と置く。
[$\subset$]
$S^2 = (\bigcup_{n \in \mathbb{N}_{\ge 1}}R^n) \circ S$
$ = \bigcup_{n \in \mathbb{N}_{\ge 1}}(R^n \circ S)$
$ = \bigcup_{n \in \mathbb{N}_{\ge 1}}(R^n \circ \bigcup_{k \in \mathbb{N}_{\ge 1}}R^k)$
$ = \bigcup_{n \in \mathbb{N}_{\ge 1}}\bigcup_{k \in \mathbb{N}_{\ge 1}}(R^n \circ R^k)$
$ = \bigcup_{n \in \mathbb{N}_{\ge 1}}\bigcup_{k \in \mathbb{N}_{\ge 1}}R^{n+k}$
$ = \bigcup_{n \in \mathbb{N}_{\ge 1}}R^{n}$
$ = S$
従って、$S$は推移関係であり、かつ$R$を含む。
$\cl_\T(R)$は$R$を含む最小の推移関係であるから、$\cl_\T(R) \subset S$
[$\supset$]
全ての$n \in \mathbb{N}_{\ge 1}$に対し、$\cl_\T(R) \supset R^n$を示す。
$n$に関する帰納法で示す。
[$n=1$の場合]
$\cl_\T(R)$ は $R$ を含む関係であるため、定義より明らかに以下が成り立つ。
$$R^1 = R \subset \cl_\T(R)$$
[$k< n$の時成り立つ ⇒ $n$で成り立つ]
$R^n = R^{n-1} \circ R$である。
ここで、関係の合成の単調性より、帰納法の仮定 $R^{n-1} \subset \cl_\T(R)$ と $R \subset \cl_\T(R)$ を合成すると、
$$R^n=R^{n-1} \circ R \subset \cl_\T(R) \circ \cl_\T(R) \subset \cl_\T(R)$$
が導かれる。
したがって、
$R^{n} \subset \cl_\T(R)$
となり、$n$のときも成り立つ。
[$\cl_\S(R) = R \cup R^{op}$]
[$\subset$]
$(R \cup R^{op})^{op} = R^{op} \cup R = R \cup R^{op}$だから、$R \cup R^{op}$は対称関係であり、$R$を含む。
$R$を含む最小の対称関係が$\cl_\S(R)$だから、
$\cl_\S(R) \subset R \cup R^{op}$
[$\supset$]
$\cl_\S(R) \supset R$だから、$\cl_\S(R)=(\cl_\S(R))^{op} \supset R^{op}$
よって、$\cl_\S(R) \supset R \cup R^{op}$
閉包作用素同士の関係
$\R$と$\T$は互いを保つ。
[$\R$と$\T$は互いを保つ]
[$\T$は$\R$を保つ]
$R \in \R$を取ると、$D \subset R$である。
$D = \bigcup_{n \in \mathbb{N}_{\ge 1}}D^n \subset \bigcup_{n \in \mathbb{N}_{\ge 1}}R^n = \cl_\T(R)$
よって、$\cl_\T(R) \in \R$
[$\R$は$\T$を保つ]
$R \in \T$を取る。
$R^2 \subset R$である。
$(\cl_\R(R))^2 = (R \cup D)^2 = R^2 \cup R \cup D \subset R \cup D = \cl_\R(R)$
よって、$\cl_\R(R) \in \T$
$\R$と$\S$は互いを保つ。
[$\R$と$\S$は互いを保つ]
[$\S$は$\R$を保つ]
$R \in \R$を取る。
$D \subset R$である。
$D \subset R^{op}$である。
よって、$D \subset R \cup R^{op} = \cl_\S(R)$である。
従って、$\cl_\S(R) \in \R$
[$\R$は$\S$を保つ]
$R \in \S$を取る。
$R^{op} \subset R$である。
$(\cl_\R(R))^{op} = (R \cup D)^{op} = R^{op} \cup D \subset R \cup D = \cl_\R(R)$
従って、$\cl_\R(R) \in \S$
$\T$は$\S$を保つ。
[$\T$は$\S$を保つ]
$R \in \S$を取る。
$R^{op} \subset R$である。
$(\cl_\T(R))^{op} = (\bigcup_{n \in \mathbb{N}_{\ge 1}}R^n)^{op} = \bigcup_{n \in \mathbb{N}_{\ge 1}}(R^n)^{op} \subset \bigcup_{n \in \mathbb{N}_{\ge 1}}R^n = \cl_\T(R)$
よって、$\cl_\T(R) \in \S$
一般には、$\S$は$\T$を保たない。
[反例]
$X = \{1, 2, 3\}$
$R = \{(1,2),(2,3),(1,3)\}$とする。
$R$は推移律を満たす。
$\cl_\S(R) = \{(1,2), (2,3), (1,3), (2,1), (3,2), (3,1)\}$ となる。
$\cl_\S(R)$は推移律を満たさない。
例えば、$(2,1),(1,2) \in \cl_\S(R)$だが、$(2,2) \not\in \cl_\S(R)$
$\cl_\T\cl_\R = \cl_\R\cl_\T = \cl_{\R \cap \T}$
$\cl_\T\cl_\S\cl_\R = \cl_\T\cl_\R\cl_\S = \cl_\R\cl_\T\cl_\S = \cl_\S\cl_{\R \cap \T} = \cl_{\R \cap \T \cap \S}$
この記事を高評価した人
この記事に送られたバッジ
投稿者
