二項関係 ⑤

Def.

Prop&Proof

集合の外延性により、
$$ S\circ R\subseteq A\times C $$
かつ
$$ A\times C\subseteq S\circ R $$
を示せば十分である。

1. まず、
   $$ S\circ R\subseteq A\times C $$
   を示す。任意に $z\in S\circ R$ をとる。
   合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して
   $$ z=(a,c)\land (a,b)\in R\land (b,c)\in S $$
   が成り立つ。特に、
   $$ z=(a,c) $$
   である。
   また、$a\in A$ かつ $c\in C$ であるから、直積の定義より
   $$ (a,c)\in A\times C $$
   である。したがって、
   $$ z\in A\times C $$
   である。ゆえに、
   $$ S\circ R\subseteq A\times C $$
   が成り立つ。
   $ $
2. 次に、
   $$ A\times C\subseteq S\circ R $$
   を示す。任意に $z\in A\times C$ をとる。
   直積の定義より、ある $a\in A$ と $c\in C$ が存在して
   $$ z=(a,c) $$
   が成り立つ。
   いま、仮定より
   $$ B\neq\varnothing $$
   であるから、ある $b\in B$ が存在する。
   $ $
   i) この $b$ について、$a\in A$ かつ $b\in B$ であるから、直積の定義より
   $$ (a,b)\in A\times B $$
   　である。
   　また、$R=A\times B$ であるから、
   $$ (a,b)\in R $$
   　である。
   $ $
   ii) 同様に、$b\in B$ かつ $c\in C$ であるから、直積の定義より
   $$ (b,c)\in B\times C $$
   　である。
   　また、$S=B\times C$ であるから、
   $$ (b,c)\in S $$
   　である。
   $ $
   したがって、
   $$ (a,b)\in R\land (b,c)\in S $$
   が成り立つ。

-よって、合成関係の定義より、
$$ (a,c)\in S\circ R $$
である。さらに、$z=(a,c)$ であるから、
$$ z\in S\circ R $$
である。ゆえに、
$$ A\times C\subseteq S\circ R $$
が成り立つ。-1. と 2. より、
$$ S\circ R=A\times C $$
である。
$$ \Box$$

合成関係の定義より、
$$ (a,c)\in S\circ R \Longleftrightarrow \exists b\in B\ \bigl((a,b)\in R\land (b,c)\in S\bigr) $$
が成り立つ。
したがって、この同値な命題の両辺を否定すると、
$$ (a,c)\notin S\circ R \Longleftrightarrow \neg\exists b\in B\ \bigl((a,b)\in R\land (b,c)\in S\bigr) $$
を得る。
ここで、命題
$$ P(b):\Longleftrightarrow \bigl((a,b)\in R\land (b,c)\in S\bigr) $$
を考える。存在記号の否定法則より、
$$ \neg\exists b\in B\ P(b) \Longleftrightarrow \forall b\in B\ \neg P(b) $$
である( 証明はコチラ )。したがって、
$$ \neg\exists b\in B\ \bigl((a,b)\in R\land (b,c)\in S\bigr) \Longleftrightarrow \forall b\in B\ \neg\bigl((a,b)\in R\land (b,c)\in S\bigr) $$
である。
さらに、任意の $b\in B$ について、ド・モルガンの法則より、
$$ \neg\bigl((a,b)\in R\land (b,c)\in S\bigr) \Longleftrightarrow (a,b)\notin R\lor (b,c)\notin S $$
が成り立つ( 証明はコチラ )。
よって、
$$ \forall b\in B\ \neg\bigl((a,b)\in R\land (b,c)\in S\bigr) \Longleftrightarrow \forall b\in B\ \bigl((a,b)\notin R\lor (b,c)\notin S\bigr) $$
が成り立つ。
以上を合わせると、
$$ (a,c)\notin S\circ R \Longleftrightarrow \forall b\in B\ \bigl((a,b)\notin R\lor (b,c)\notin S\bigr) $$
が成り立つ。
$$ \Box$$

$A=\{1,2,3\}$ とする。また、
$$ R=\{(1,2)\}\subseteq A\times A $$
$$ S=\{(2,3)\}\subseteq A\times A $$
と定める。

1. まず、$S\circ R$ を求める。
   合成関係の定義より、任意の $(a,c)\in A\times A$ に対して、
   $$ (a,c)\in S\circ R \Longleftrightarrow \exists b\in A\ ((a,b)\in R\land (b,c)\in S) $$
   である。
   ここで、
   $$ (1,2)\in R,\qquad (2,3)\in S $$
   であるから、
   $$ (1,3)\in S\circ R $$
   である。
   また、$R$ の元は $(1,2)$ のみであり、$S$ の元は $(2,3)$ のみであるから、$S\circ R$ に属する順序対は $(1,3)$ のみである。
   したがって、
   $$ S\circ R=\{(1,3)\} $$
   である。
   $ $
2. 次に、$R\circ S$ を求める。
   合成関係の定義より、任意の $(a,c)\in A\times A$ に対して、
   $$ (a,c)\in R\circ S \Longleftrightarrow \exists b\in A\ ((a,b)\in S\land (b,c)\in R) $$
   である。
   ここで、$(a,b)\in S$ が成り立つためには、
   $$ (a,b)=(2,3) $$
   でなければならない。
   したがって、
   $$ b=3 $$
   である。
   しかし、$(b,c)\in R$ も同時に成り立つためには、
   $$ (3,c)\in R $$
   でなければならない。
   ところが、
   $$ R=\{(1,2)\} $$
   であるから、そのような $c\in A$ は存在しない。
   よって、任意の $(a,c)\in A\times A$ について、
   $$ (a,c)\notin R\circ S $$
   である。
   したがって、
   $$ R\circ S=\varnothing $$
   である。

-以上より、
$$ S\circ R=\{(1,3)\} $$
かつ
$$ R\circ S=\varnothing $$
である。ゆえに、
$$ S\circ R\ne R\circ S $$
である。
したがって、二項関係の合成は一般に可換ではない。
$$ \Box$$

集合の外延性により示す。
任意の $z$ をとる。
$$ z\in T\circ (S\circ R)\ \Leftrightarrow\ z\in (T\circ S)\circ R $$
を示せば十分である。
$ $

1. まず、合成関係の定義より、
   $$ \begin{align} &z\in T\circ (S\circ R)\\ \ &\Leftrightarrow\ \exists a\in A\ \exists c\in C\ \exists d\in D\ \bigl(z=(a,d)\land (a,c)\in S\circ R\land (c,d)\in T\bigr) \end{align} $$
   である。
   さらに、合成関係の定義より、
   $$ \begin{align} &(a,c)\in S\circ R\\ \ &\Leftrightarrow\ \exists b\in B\ \bigl((a,b)\in R\land (b,c)\in S\bigr) \end{align} $$
   である。したがって、
   $$ \begin{align} &z\in T\circ (S\circ R)\\ \ &\Leftrightarrow\ \exists a\in A\ \exists c\in C\ \exists d\in D\ \exists b\in B\ \bigl(z=(a,d)\land (a,b)\in R\land (b,c)\in S\land (c,d)\in T\bigr) \end{align} $$
   である。
   存在記号の順序は入れ替えても同値( 証明はコチラ )であるから、
   $$ \begin{align} &z\in T\circ (S\circ R)\\ \ &\Leftrightarrow\ \exists a\in A\ \exists b\in B\ \exists c\in C\ \exists d\in D\ \bigl(z=(a,d)\land (a,b)\in R\land (b,c)\in S\land (c,d)\in T\bigr) \end{align} $$
   である。
   $ $
2. 一方、合成関係の定義より、
   $$ \begin{align} &z\in (T\circ S)\circ R\\ \ &\Leftrightarrow\ \exists a\in A\ \exists b\in B\ \exists d\in D\ \bigl(z=(a,d)\land (a,b)\in R\land (b,d)\in T\circ S\bigr) \end{align} $$
   である。
   さらに、合成関係の定義より、
   $$ (b,d)\in T\circ S \ \Leftrightarrow\ \exists c\in C\ \bigl((b,c)\in S\land (c,d)\in T\bigr) $$
   である。
   したがって、
   $$ \begin{align} &z\in (T\circ S)\circ R\\ \ &\Leftrightarrow\ \exists a\in A\ \exists b\in B\ \exists d\in D\ \exists c\in C\ \bigl(z=(a,d)\land (a,b)\in R\land (b,c)\in S\land (c,d)\in T\bigr) \end{align} $$
   である。
   存在記号の順序は入れ替えても同値( 証明はコチラ )であるから、
   $$ \begin{align} &z\in (T\circ S)\circ R\\ \ &\Leftrightarrow\ \exists a\in A\ \exists b\in B\ \exists c\in C\ \exists d\in D\ \bigl(z=(a,d)\land (a,b)\in R\land (b,c)\in S\land (c,d)\in T\bigr) \end{align} $$
   である。

-以上より、両者は同じ条件
$$ \exists a\in A\ \exists b\in B\ \exists c\in C\ \exists d\in D\ \bigl(z=(a,d)\land (a,b)\in R\land (b,c)\in S\land (c,d)\in T\bigr) $$
と同値である。
したがって、
$$ z\in T\circ (S\circ R)\ \Leftrightarrow\ z\in (T\circ S)\circ R $$
が成り立つ。
ゆえに、集合の外延性により
$$ T\circ (S\circ R)=(T\circ S)\circ R $$
である。
$$ \Box$$