$$\newcommand{rrefl}[0]{R_{\text{Refl}}}
\newcommand{rtrans}[0]{R_{\text{trans}}}
$$
本記事は筆者がMathlogを試すことも兼ねた記事です。内容の正確性は保証しません。
演習 2.2.6
$R$を$S$上の関係とし、$R'=R\cup\{(s,s) | s\in S\}$とし、$R$の反射的閉包を$\rrefl$とする。
$R'=\rrefl$であることを示す。
- $\rrefl \subset R'$
$R'$は定義から明らかに反射的かつ$R$を含む。反射的閉包の定義は反射的関係でかつ$R$を含むような関係の中で最小のものであるから、 $\rrefl \subset R'$である。 - $R' \subset \rrefl$
$(s,t)\in R'$ とすると、定義から $(s,t) \in R$ または $s = t$。
$(s,t) \in R$ の場合、$R \subset \rrefl$より $(s,t) \in \rrefl$
$s=t$の場合、$(s,t)=(s,s) \in \rrefl$
以上から$R' \subset \rrefl$
演習 2.2.7
$S$上の二項関係$R^+$を
$$
\begin {align}
R_0 &= R \\
R_{i+1} &= R_i \cup \{(s,u)| \exists t \in R_i , (s,t)\in R_i \wedge (t,u) \in R_i \} \\
R^+ &= \bigcup_i R_i
\end {align}
$$
で定義し、$\rtrans$を$R$の推移的閉包とする。$R^+ = \rtrans$を示す。
- $\rtrans \subset R^+$
$(s,t), (t,u) \in R^+$ とすると、ある$i, j$について$(s,t) \in R_i$かつ$(t,u)\in R_j$である。$m = max(i,j)$とすると、${R_i}$は単調増加なので、 $(s,t), (t,u) \in R_m$ となるので、 $(s,u) \in R_{m+1} \subset R^+$ 。ゆえに$R^+$は推移的。また$R$を含むことは明らか。推移的閉包は、定義から、そのような関係のうち最小のものであるから、 $\rtrans \subset R^+$ - $R^+ \subset \rtrans$
任意の$i$について $R_i \subset \rtrans$であることを示せば十分。
$i=0$の場合、$R_0=R\in\rtrans$より分かる。
$i=n$で成り立つと仮定し $i=n+1$でも成り立つことを示す。
$(s,u)\in R_{n+1}$とする。$(s,u)\in R_n$である場合は自明。$\exists t. (s,t), (t,u) \in R_i$の場合、帰納法の仮定から $(s,t), (t,u) \in \rtrans$ となる。 $\rtrans$ は推移的なので $(s,u) \in \rtrans$ である。
以上から、 $R^+ \subset \rtrans$