反射推移的閉包の作り方とそれが定義を満たしていることの証明
$ Rが$ X上の2項関係であるとき、$ R^n (n = 0,1,2...)を
$ R^0 = \{(x, x) | x \in X\}
$ R^{n+1} = R^n R
によって定義し、$ R^* = \bigcup_{n \in Nat}R^nとする。
以下では$ R^*が「$ Rを含み反射律と推移律を満たす最小の関係」であること（これが反射推移的閉包の定義）を示す。
1. $ R \subseteq R^*の証明
明らかに$ R^1 = Rなので$ R \subseteq R^*
2. 反射性の証明
$ R^0と反射律の定義より明らか。
3. 推移性の証明
$ x, y, zを$ X上の変数とし、$ (x, y), (y, z) \in R^*と仮定する。このとき$ (x, z) \in R^*となることを示したい。
仮定より、$ (x, y) \in R^m, (y, z) \in R^mを満たす$ m, n \in Natが存在する。
関係の合成は結合律を満たすので
$ R^{m+n} = R^m R^n
となり、関係の定義と$ (x, y) \in R^m, (y, z) \in R^mより$ (x, z) \in R^{m+n}。
$ R^{m+n} \subseteq R^*より$ (x, z) \in R^*
4. 最小であることの証明
任意の$ Rを含む反射推移的関係$ Tについて$ R^* \subseteq Tであることを示せばよい。
これには$ \forall{n \in Nat}.R^n \subseteq Tを示せば十分。
自然数に関する帰納法で証明する。
a. $ n = 0のとき
$ R^0 = Rと$ Tの定義より明らかに$ R^0 \subseteq T
b. $ k \in Natについて$ R^k \subseteq Tと仮定
$ \forall{x, z \in X}. (x, z) \in R^{k+1} \Rightarrow (x, z) \in Tを示せばよい。
$ x, zを$ X上の変数とせよ。$ (x, z) \in R^{k+1}と仮定すると$ R^{k+1} = R^k Rより、
$ (x, y) \in R^k, (y, z) \in Rを満たす$ yが存在する。
帰納法の仮定とaの結果より$ (x, y) \in T, (y, z) \in Tであり、$ Tは推移的なので$ (x, z) \in T
よって$ \forall{x, z \in X}. (x, z) \in R^{k+1} \Rightarrow (x, z) \in T
帰納法により$ \forall{n \in Nat}.R^n \subseteq Tが示された。よって任意の$ Tについて$ R^* \subseteq T
Q.E.D
おまけ
反射推移的閉包は以下のようにも構成できる。
$ R^0 = \{(x, x) | x \in X\}
$ R^1 = R
$ R^{n+1} = R^n \cup \{(x, z) | \exists{y}.(x, y), (y, z) \in R^n\}
$ R^* = \bigcup_{n \in Nat}R^n
この$ R^*と最初に作った$ R^*が等しいことは簡単に確かめられる（と思う）。