型システム入門 演習問題 解答

本記事は筆者がMathlogを試すことも兼ねた記事です。内容の正確性は保証しません。

演習 2.2.6

$R$を$S$上の関係とし、$R^{\prime }=R\cup \{(s,s)|s\in S\}$とし、$R$の反射的閉包を$R_{\text{Refl}}$とする。
$R^{\prime }=R_{\text{Refl}}$であることを示す。

1. $R_{\text{Refl}}\subset R^{\prime }$
   $R^{\prime }$は定義から明らかに反射的かつ$R$を含む。反射的閉包の定義は反射的関係でかつ$R$を含むような関係の中で最小のものであるから、 $R_{\text{Refl}}\subset R^{\prime }$である。
2. $R^{\prime }\subset R_{\text{Refl}}$
   $(s,t)\in R^{\prime }$ とすると、定義から $(s,t)\in R$ または $s=t$。
   $(s,t)\in R$ の場合、$R\subset R_{\text{Refl}}$より $(s,t)\in R_{\text{Refl}}$
   $s=t$の場合、$(s,t)=(s,s)\in R_{\text{Refl}}$

      以上から$R' \subset \rrefl$
    

演習 2.2.7

$S$上の二項関係$R^{+}$を
$$\begin{array}{rl}{R}_0& =R\\ R_{i+1}& =R_i\cup \{(s,u)|\mathrm{\exists }t\in R_i,(s,t)\in R_i\wedge (t,u)\in R_i\}\\ R^{+}& =\bigcup _i{R}_i\end{array}$$
で定義し、$R_{\text{trans}}$を$R$の推移的閉包とする。$R^{+}=R_{\text{trans}}$を示す。

1. $R_{\text{trans}}\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^+$
2. $R^{+}\subset R_{\text{trans}}$
   任意の$i$について $R_i\subset R_{\text{trans}}$であることを示せば十分。
   $i=0$の場合、$R_0=R\in R_{\text{trans}}$より分かる。
   $i=n$で成り立つと仮定し $i=n+1$でも成り立つことを示す。
   $(s,u)\in R_{n+1}$とする。$(s,u)\in R_n$である場合は自明。$\mathrm{\exists }t.(s,t),(t,u)\in R_i$の場合、帰納法の仮定から $(s,t),(t,u)\in R_{\text{trans}}$ となる。 $R_{\text{trans}}$ は推移的なので $(s,u)\in R_{\text{trans}}$ である。
   以上から、 $R^{+}\subset R_{\text{trans}}$