推移閉包(二項関係)

2. $n$ についての帰納法で示す。$n=0$ は $R^{0}=\Delta_A$ の定義そのものである。$(a,c)\in R^{n+1}=R\circ R^{n}$ は、ある $b$ について $(a,b)\in R^{n}$ かつ $b\,R\,c$ となることである。帰納法の仮定から、これは「$a$ から $b$ への長さ $n$ の $R$ 鎖があり、$b\,R\,c$ である」ことであり、鎖の後ろに $c$ を付け加えれば $a$ から $c$ への長さ $n+1$ の $R$ 鎖になる。逆に長さ $n+1$ の鎖は、最後の 1 歩を外すと長さ $n$ の鎖と 1 歩に分かれる。
1. 長さ $1$ 以上の $R$ 鎖で結ばれる組 $(a,b)$ の全体を $T$ とする。

• $R\subseteq T$ である。$a\,R\,b$ なら $a,b$ は長さ $1$ の鎖である。
• $T$ は推移的である。$a$ から $b$ への鎖 $x_0,\dots,x_n$ と $b$ から $c$ への鎖 $y_0,\dots,y_m$ をつないだ $x_0,\dots,x_n=y_0,y_1,\dots,y_m$ は、$a$ から $c$ への長さ $n+m$ の鎖である。
• $R$ を含む推移的関係 $S$ は $T$ を含む。長さ $n$ の鎖で結ばれる $(a,b)$ が $S$ に属することを $n$ の帰納法で示す。$n=1$ なら $a\,R\,b$ から $a\,S\,b$ である。$n\ge2$ なら、帰納法の仮定から $x_0\,S\,x_{n-1}$ であり、$x_{n-1}\,R\,x_n$ から $x_{n-1}\,S\,x_n$ なので、推移律から $a\,S\,b$ である。
  よって $T$ は $R$ を含む最小の推移的関係であり、$T=R^{+}$ である。2 と合わせて $R^{+}=\bigcup_{n\ge1}R^{n}$、$R^{*}=R^{+}\cup R^{0}=\bigcup_{n\ge0}R^{n}$ を得る。

3. $R^{*}$ は $\Delta_A$ を含むので反射的である。推移性は、長さ $0$ の鎖も許して 1 と同じく鎖をつなげばよい。$R$ を含む前順序 $S$ は、推移的なので $R^{+}$ を含み、反射的なので $\Delta_A$ を含むから、$R^{*}\subseteq S$ である。$\square$

1. $R\subseteq R^{+}$ は定義から従う。$R\subseteq S$ なら $S^{+}$ は $R$ を含む推移的関係なので $R^{+}\subseteq S^{+}$ である。$R^{+}$ は推移的なので、$R^{+}$ を含む最小の推移的関係は $R^{+}$ 自身であり、$(R^{+})^{+}=R^{+}$ である。$R$ が推移的なら同じ理由で $R^{+}=R$ であり、逆に $R^{+}=R$ なら $R$ は推移的である。閉集合 $R=R^{+}$ がちょうど推移的関係であることもこれで分かる。
2. $a$ から $b$ への長さ $n$ の $R^{-1}$ 鎖 $a=x_0,\dots,x_n=b$ を逆順に読むと、$x_k\,R\,x_{k-1}$ なので $b$ から $a$ への長さ $n$ の $R$ 鎖である。逆も同様である。thm-trc-chains の 1 から $a\,(R^{-1})^{+}\,b\iff b\,R^{+}\,a\iff a\,(R^{+})^{-1}\,b$ である。$R$ が対称的なら $R^{-1}=R$ なので $(R^{+})^{-1}=(R^{-1})^{+}=R^{+}$ であり、$R^{+}$ は対称的である（二項関係 の命題「性質の包含による言い換え」の 2）。
3. 長さ $1$ の鎖は $R$ の組である。長さ $n\ge2$ の鎖 $x_0,\dots,x_n$ は、$x_0$ から $x_{n-1}$ への長さ $n-1\ge1$ の鎖と最後の 1 歩 $x_{n-1}\,R\,x_n$ に分かれるので、$(x_0,x_n)\in R\circ R^{+}$ である。逆に $R\circ R^{+}$ の組は長さ $2$ 以上の鎖を与える。最初の 1 歩で分ければ $R^{+}\circ R$ についても同様である。
4. $a\,R^{+}\,b$ とし、$a$ から $b$ への $R$ 鎖のうち長さ $m$ が最小のもの $x_0,\dots,x_m$ をとる。$m> n$ とすると、$x_1,\dots,x_m$ は $n$ 元集合の $m$ 個の元なので、$1\le i< j\le m$ で $x_i=x_j$ となるものがある。$x_{i+1},\dots,x_j$ を取り除いた列 $x_0,\dots,x_i,x_{j+1},\dots,x_m$ は、$x_i=x_j\,R\,x_{j+1}$（$j< m$ のとき）なので $a$ から $b$ への $R$ 鎖であり（$j=m$ なら最後の元は $x_i=x_m=b$）、その長さ $m-(j-i)$ は $i\ge1$ なので $1$ 以上で $m$ より小さい。これは $m$ の最小性に反する。よって $m\le n$ であり、$(a,b)\in\bigcup_{k=1}^{n}R^{k}$ である。
5. thm-trc-chains の 1 から、$a\,R^{+}\,a$ は $a$ から $a$ への長さ $1$ 以上の鎖、すなわち閉路があることである。$R^{+}$ が非反射的かつ推移的なら、$a\,R^{*}\,b$ かつ $b\,R^{*}\,a$ で $a\neq b$ とすると $a\,R^{+}\,b$、$b\,R^{+}\,a$ から $a\,R^{+}\,a$ となって矛盾するので、$R^{*}$ は反対称律も満たし、半順序である。$\square$

1. $R^{*}$ は thm-trc-chains の 3 により推移的で、$R\cup\Delta_A$ を含むので $(R\cup\Delta_A)^{+}\subseteq R^{*}$ である。逆に $R\subseteq R\cup\Delta_A$ から prop-trc-basic の 1 により $R^{+}\subseteq(R\cup\Delta_A)^{+}$ であり、$\Delta_A\subseteq(R\cup\Delta_A)^{+}$ なので $R^{*}\subseteq(R\cup\Delta_A)^{+}$ である。
2. $S:=R\cup R^{-1}$ は対称的なので、prop-trc-basic の 2 により $S^{+}$ は対称的で、推移的でもある。1 を $S$ に当てはめると $(S\cup\Delta_A)^{+}=S^{+}\cup\Delta_A$ であり、これは反射的・対称的・推移的なので同値関係である。$R$ を含む同値関係 $E$ は対称的なので $S$ を含み、反射的かつ推移的なので $(S\cup\Delta_A)^{+}$ を含む。$\square$

途中の元がすべて $\{1,\dots,k\}$ に属する長さ $1$ 以上の $R$ 鎖を「$k$ 以下を経由する鎖」と呼び、$k$ についての帰納法で示す。$k=0$ では途中の元がない鎖、すなわち長さ $1$ の鎖だけが該当し、これは $R_0=R$ の組と同じである。
$k\ge1$ とし、$k-1$ で主張が成り立つとする。$(i,j)\in R_k$ とする。$(i,j)\in R_{k-1}$ なら帰納法の仮定から $k-1$ 以下を経由する鎖があり、これは $k$ 以下を経由する鎖でもある。$(i,k),(k,j)\in R_{k-1}$ なら、$i$ から $k$ への鎖と $k$ から $j$ への $k-1$ 以下を経由する鎖をつなぐと、途中の元は $\{1,\dots,k-1\}$ の元と $k$ だけなので、$k$ 以下を経由する鎖が得られる。
逆に $i$ から $j$ への $k$ 以下を経由する鎖 $x_0,\dots,x_m$ があるとする。途中の元に $k$ が現れなければ、それは $k-1$ 以下を経由する鎖なので $(i,j)\in R_{k-1}\subseteq R_k$ である。現れるなら、途中で $k$ が最初に現れる位置を $p$、最後に現れる位置を $q$ とする（$1\le p\le q\le m-1$）。$x_0,\dots,x_p$ は途中に $k$ を含まないので $i$ から $k$ への $k-1$ 以下を経由する鎖であり、同様に $x_q,\dots,x_m$ は $k$ から $j$ への $k-1$ 以下を経由する鎖である。帰納法の仮定から $(i,k),(k,j)\in R_{k-1}$ であり、$(i,j)\in R_k$ である。
$k=n$ ではすべての長さ $1$ 以上の鎖が該当するので、thm-trc-chains の 1 から $R_n=R^{+}$ である。$\square$