二項関係 ④

Prop&Proof.

集合の外延性により、任意の $z$ について
$$ z\in (A\times B)^{-1}\ \Leftrightarrow\ z\in B\times A $$
を示せば十分である。
$ $
任意の $z$ をとる。まず、逆関係の定義より、
$$ z\in (A\times B)^{-1} \ \Leftrightarrow\ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land (a,b)\in A\times B\bigr) $$
が成り立つ。
ここで、$a\in A,\ b\in B$ のもとで、直積の定義より
$$ (a,b)\in A\times B $$
である。
したがって、
$$ z\in (A\times B)^{-1} \ \Leftrightarrow\ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\bigr) $$
である。
一方、直積の定義より、
$$ z\in B\times A \ \Leftrightarrow\ \exists b\in B\ \exists a\in A\ \bigl(z=(b,a)\bigr) $$
である。
さらに、存在記号の順序を入れ替えても同値( 証明はコチラ )であるから、
$$ \exists b\in B\ \exists a\in A\ \bigl(z=(b,a)\bigr) \ \Leftrightarrow\ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\bigr) $$
である。
したがって、
$$ z\in B\times A \ \Leftrightarrow\ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\bigr) $$
である。
ゆえに、
$$ z\in (A\times B)^{-1}\ \Leftrightarrow\ z\in B\times A $$
が成り立つ。
以上より、集合の外延性により
$$ (A\times B)^{-1}=B\times A $$
である。
$$ \Box$$

$R^{-1}\subseteq S^{-1}$ を示す。
任意に $z\in R^{-1}$ をとる。逆関係の定義より、
$$ z\in R^{-1} \ \Leftrightarrow\ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land (a,b)\in R\bigr) $$
である。
したがって、ある $a\in A$ と $b\in B$ が存在して
$$ z=(b,a)\land (a,b)\in R $$
が成り立つ。
ここで、仮定
$$ R\subseteq S $$
より、
$$ (a,b)\in S $$
が成り立つ。
したがって、逆関係の定義より
$$ (b,a)\in S^{-1} $$
である。
しかも $z=(b,a)$ であるから、
$$ z\in S^{-1} $$
が成り立つ。
以上より、任意の $z\in R^{-1}$ に対して $z\in S^{-1}$ が成り立つので、
$$ R^{-1}\subseteq S^{-1} $$
である。
$$ \Box$$

集合の外延性により、任意の $z$ について
$$ z\in (R\cup S)^{-1}\ \Leftrightarrow\ z\in R^{-1}\cup S^{-1} $$
を示せば十分である。
$ $
任意の $z$ をとる。まず、逆関係の定義より、
$$ z\in (R\cup S)^{-1} \ \Leftrightarrow\ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land (a,b)\in R\cup S\bigr) $$
が成り立つ。
ここで、和集合の定義より、
$$ (a,b)\in R\cup S\ \Leftrightarrow\ (a,b)\in R\lor (a,b)\in S $$
であるから、
$$ z\in (R\cup S)^{-1} \ \Leftrightarrow\ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land \bigl((a,b)\in R\lor (a,b)\in S\bigr)\bigr) $$
となる。
したがって、存在記号と論理和の性質( 証明はコチラ )より、
$$ z\in (R\cup S)^{-1} \ \Leftrightarrow\ \Bigl(\exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land (a,b)\in R\bigr)\Bigr) \lor \Bigl(\exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land (a,b)\in S\bigr)\Bigr) $$
が成り立つ。
一方、逆関係の定義より、
$$ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land (a,b)\in R\bigr) \ \Leftrightarrow\ z\in R^{-1} $$
$$ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land (a,b)\in S\bigr) \ \Leftrightarrow\ z\in S^{-1} $$
であるから、
$$ z\in (R\cup S)^{-1} \ \Leftrightarrow\ z\in R^{-1}\lor z\in S^{-1} $$
となる。これは和集合の定義より
$$ z\in (R\cup S)^{-1}\ \Leftrightarrow\ z\in R^{-1}\cup S^{-1} $$
と同値である。
$ $
したがって、任意の $z$ について上の同値が成り立つので、集合の外延性により
$$ (R\cup S)^{-1}=R^{-1}\cup S^{-1} $$
である。
$$ \Box$$

集合の外延性により、任意の $z$ について
$$ z\in (R\cap S)^{-1}\ \Leftrightarrow\ z\in R^{-1}\cap S^{-1} $$
を示せば十分である。
$ $

1. 任意の $z$ をとる。まず、逆関係の定義より、
   $$ z\in (R\cap S)^{-1} \ \Leftrightarrow\ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land (a,b)\in R\cap S\bigr) $$
   が成り立つ。
   ここで、共通部分の定義より、
   $$ (a,b)\in R\cap S\ \Leftrightarrow\ (a,b)\in R\land (a,b)\in S $$
   であるから、
   $$ z\in (R\cap S)^{-1} \ \Leftrightarrow\ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land (a,b)\in R\land (a,b)\in S\bigr) $$
   となる。したがって、
   $$ z\in (R\cap S)^{-1} \ \Rightarrow\ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land (a,b)\in R\bigr) $$
   かつ
   $$ z\in (R\cap S)^{-1} \ \Rightarrow\ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land (a,b)\in S\bigr) $$
   が成り立つ。
   逆関係の定義より、これは
   $$ z\in (R\cap S)^{-1} \ \Rightarrow\ z\in R^{-1}\land z\in S^{-1} $$
   すなわち、共通部分の定義より
   $$ z\in (R\cap S)^{-1} \ \Rightarrow\ z\in R^{-1}\cap S^{-1} $$
   を意味する。
   $ $
2. 逆に、$z\in R^{-1}\cap S^{-1}$ と仮定する。
   すると
   $$ z\in R^{-1}\land z\in S^{-1} $$
   である。
   したがって、逆関係の定義より、
   $$ \exists a\in A\ \exists b\in B\ \bigl(z=(b,a)\land (a,b)\in R\bigr) $$
   かつ
   $$ \exists c\in A\ \exists d\in B\ \bigl(z=(d,c)\land (c,d)\in S\bigr) $$
   が成り立つ。ここで、$z=(b,a)$ かつ $z=(d,c)$ であるから
   $$ (b,a)=(d,c) $$
   であり、順序対の等号( 証明はコチラ )より
   $$ b=d\land a=c $$
   が成り立つ。したがって、
   $$ (a,b)\in R\land (a,b)\in S $$
   であるから、
   $$ (a,b)\in R\cap S $$
   が成り立つ。
   ゆえに、
   $$ z=(b,a)\land (a,b)\in R\cap S $$
   を満たす $a\in A,\ b\in B$ が存在するので、逆関係の定義より
   $$ z\in (R\cap S)^{-1} $$
   である。

-以上より、任意の $z$ について
$$ z\in (R\cap S)^{-1}\ \Leftrightarrow\ z\in R^{-1}\cap S^{-1} $$
が成り立つ。よって、集合の外延性により
$$ (R\cap S)^{-1}=R^{-1}\cap S^{-1} $$
である。
$$ \Box$$

集合の外延性により、任意の $z$ について
$$ z\in (R\setminus S)^{-1}\ \Leftrightarrow\ z\in R^{-1}\setminus S^{-1} $$
を示せば十分である。
$ $

1. 任意の $z$ をとる。まず、
   $$ z\in (R\setminus S)^{-1}\ \Rightarrow\ z\in R^{-1}\setminus S^{-1} $$
   を示す。
   $z\in (R\setminus S)^{-1}$ と仮定する。逆関係の定義より、ある $a\in A,\ b\in B$ が存在して
   $$ z=(b,a)\land (a,b)\in R\setminus S $$
   が成り立つ。
   差集合の定義より、
   $$ (a,b)\in R\land (a,b)\notin S $$
   である。$(a,b)\in R$ であるから、逆関係の定義より
   $$ z=(b,a)\in R^{-1} $$
   が成り立つ。
   次に、$z\in S^{-1}$ と仮定して矛盾を導く。
   $z\in S^{-1}$ であるから、逆関係の定義より、ある $c\in A$、$d\in B$ が存在して
   $$ z=(d,c)\land (c,d)\in S $$
   が成り立つ。
   ところが、
   $$ z=(b,a)\land z=(d,c) $$
   であるから、順序対の等号( 証明はコチラ )より
   $$ b=d,\qquad a=c $$
   が成り立つ。したがって、
   $$ (a,b)=(c,d)\in S $$
   となる。これは $(a,b)\notin S$ に矛盾する。
   ゆえに
   $$ z\notin S^{-1} $$
   である。したがって、
   $$ z\in R^{-1}\setminus S^{-1} $$
   が成り立つ。
   $ $
2. 次に、
   $$ z\in R^{-1}\setminus S^{-1}\ \Rightarrow\ z\in (R\setminus S)^{-1} $$
   を示す。$z\in R^{-1}\setminus S^{-1}$ と仮定する。差集合の定義より、
   $$ z\in R^{-1}\land z\notin S^{-1} $$
   である。
   $z\in R^{-1}$ であるから、逆関係の定義より、ある $a\in A, b\in B$ が存在して
   $$ z=(b,a)\land (a,b)\in R $$
   が成り立つ。
   ここで、もし $(a,b)\in S$ ならば、逆関係の定義より
   $$ (b,a)\in S^{-1} $$
   となる。しかも $z=(b,a)$ であるから
   $$ z\in S^{-1} $$
   となるが、これは $z\notin S^{-1}$ に矛盾する。
   したがって、
   $$ (a,b)\notin S $$
   である。よって、
   $$ (a,b)\in R\setminus S $$
   が成り立つ。再び逆関係の定義より、
   $$ z=(b,a)\in (R\setminus S)^{-1} $$
   である。

-以上より、任意の $z$ について
$$ z\in (R\setminus S)^{-1}\ \Leftrightarrow\ z\in R^{-1}\setminus S^{-1} $$
が成り立つ。ゆえに、集合の外延性により
$$ (R\setminus S)^{-1}=R^{-1}\setminus S^{-1} $$
である。
$$ \Box$$