関係の合成

• $R\subset A\times B$, $S\subset B\times C$とする。$R,S$を合成した関係$R\circ S$は以下のように定義される
  • $x(R\circ S)y\iff \exists z\in B(xRz\wedge zSy)$
• 関係の合成には、結合律が成り立つ
  • $R\circ (S\circ T)=(R\circ S)\circ T$
• $R$が$A$上の二項関係で$n$が自然数のとき、「$R$の(関係としての)$n$乗」という関係$R^n$が次のように定義できる
  • $R^0=\{(a,a)|a\in A\}$
  • $R^{n+1}=R^n\circ R=R\circ R^n$