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

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

演習 2.2.6

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

1. $\rrefl \subset R'$
   $R'$は定義から明らかに反射的かつ$R$を含む。反射的閉包の定義は反射的関係でかつ$R$を含むような関係の中で最小のものであるから、 $\rrefl \subset R'$である。
2. $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$を示す。

1. $\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^+$
2. $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$