二項関係 ⑥
Prop&Proof
$A,B,C$ を集合とし、$R_1,R_2\subseteq A\times B,\ S\subseteq B\times C$ を二項関係とする。
このとき、
$$
S\circ (R_1\cup R_2)=(S\circ R_1)\cup(S\circ R_2)
$$
が成り立つ。
集合の外延性により、
$$
S\circ (R_1\cup R_2)\subseteq (S\circ R_1)\cup(S\circ R_2)
$$
かつ
$$
(S\circ R_1)\cup(S\circ R_2)\subseteq S\circ (R_1\cup R_2)
$$
を示せばよい。
- $S\circ (R_1\cup R_2)\subseteq (S\circ R_1)\cup(S\circ R_2)$ を示す。
任意に
$$ z\in S\circ (R_1\cup R_2) $$
をとる。
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c) $$
かつ
$$ (a,b)\in R_1\cup R_2\land (b,c)\in S $$
が成り立つ。和集合の定義より、
$$ (a,b)\in R_1\lor (a,b)\in R_2 $$
である。
ここで場合分けを行う。
$ $
i) $(a,b)\in R_1$ の場合
このとき、
$$ (a,b)\in R_1\land (b,c)\in S $$
である。
したがって、合成関係の定義より、
$$ (a,c)\in S\circ R_1 $$
である。ゆえに、和集合の定義より、
$$ (a,c)\in (S\circ R_1)\cup(S\circ R_2) $$
である。よって、
$$ z\in (S\circ R_1)\cup(S\circ R_2) $$
である。
$ $
ii) $(a,b)\in R_2$ の場合
このとき、
$$ (a,b)\in R_2\land (b,c)\in S $$
である。
したがって、合成関係の定義より、
$$ (a,c)\in S\circ R_2 $$
である。
ゆえに、和集合の定義より、
$$ (a,c)\in (S\circ R_1)\cup(S\circ R_2) $$
である。よって、
$$ z\in (S\circ R_1)\cup(S\circ R_2) $$
である。
$ $
以上より、いずれの場合も、
$$ z\in (S\circ R_1)\cup(S\circ R_2) $$
が成り立つ。
$z\in S\circ (R_1\cup R_2)$ は任意であったから、
$$ S\circ (R_1\cup R_2)\subseteq (S\circ R_1)\cup(S\circ R_2) $$
である。
$ $ - $(S\circ R_1)\cup(S\circ R_2)\subseteq S\circ (R_1\cup R_2)$ を示す。
任意に
$$ z\in (S\circ R_1)\cup(S\circ R_2) $$
をとる。
和集合の定義より、
$$ z\in S\circ R_1\lor z\in S\circ R_2 $$
である。
ここで場合分けを行う。
$ $
i) $z\in S\circ R_1$ の場合
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c) $$
かつ
$$ (a,b)\in R_1\land (b,c)\in S $$
が成り立つ。和集合の定義より、
$$ (a,b)\in R_1\cup R_2 $$
である。したがって、
$$ (a,b)\in R_1\cup R_2\land (b,c)\in S $$
である。
合成関係の定義より、
$$ (a,c)\in S\circ (R_1\cup R_2) $$
である。よって、
$$ z\in S\circ (R_1\cup R_2) $$
である。
$ $
ii) $z\in S\circ R_2$ の場合
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c) $$
かつ
$$ (a,b)\in R_2\land (b,c)\in S $$
が成り立つ。
和集合の定義より、
$$ (a,b)\in R_1\cup R_2 $$
である。したがって、
$$ (a,b)\in R_1\cup R_2\land (b,c)\in S $$
である。合成関係の定義より、
$$ (a,c)\in S\circ (R_1\cup R_2) $$
である。よって、
$$ z\in S\circ (R_1\cup R_2) $$
である。
$ $
以上より、いずれの場合も、
$$ z\in S\circ (R_1\cup R_2) $$
が成り立つ。
$z\in (S\circ R_1)\cup(S\circ R_2)$ は任意であったから、
$$ (S\circ R_1)\cup(S\circ R_2)\subseteq S\circ (R_1\cup R_2) $$
である。
-1. と 2. より、
$$
S\circ (R_1\cup R_2)=(S\circ R_1)\cup(S\circ R_2)
$$
が成り立つ。
$$ \Box$$
この命題は、合成関係が前半に用いる関係の和集合に対して分配することを表している。
特に、
$$
S\circ(R_1\cup R_2)
$$
では、先に用いる関係が $R_1\cup R_2$ である。
$(a,c)\in S\circ(R_1\cup R_2)$ であるとは、ある $b\in B$ が存在して、
$$
(a,b)\in R_1\cup R_2
$$
かつ
$$
(b,c)\in S
$$
が成り立つことである。ここで、
$$
(a,b)\in R_1\cup R_2
$$
は
$$
(a,b)\in R_1\lor (a,b)\in R_2
$$
と同値である。したがって、中間元 $b$ に到達する前半部分が $R_1$ に属する場合と $R_2$ に属する場合に分かれる。
その結果、
$$
S\circ (R_1\cup R_2)=(S\circ R_1)\cup(S\circ R_2)
$$
が成り立つのである。
$A,\ B,\ C$ を集合とし、$R\subseteq A\times B,\ S_1,S_2\subseteq B\times C$ を二項関係とする。
このとき、
$$
(S_1\cup S_2)\circ R=(S_1\circ R)\cup(S_2\circ R)
$$
が成り立つ。
集合の外延性により、
$$
(S_1\cup S_2)\circ R\subseteq (S_1\circ R)\cup(S_2\circ R)
$$
かつ
$$
(S_1\circ R)\cup(S_2\circ R)\subseteq (S_1\cup S_2)\circ R
$$
を示せばよい。
- $(S_1\cup S_2)\circ R\subseteq (S_1\circ R)\cup(S_2\circ R)$ を示す。
任意に $z\in (S_1\cup S_2)\circ R$ をとる。
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c) $$
かつ
$$ (a,b)\in R\land (b,c)\in S_1\cup S_2 $$
が成り立つ。和集合の定義より、
$$ (b,c)\in S_1\lor (b,c)\in S_2 $$
である。
ここで場合分けを行う。
$ $
i) $(b,c)\in S_1$ の場合
このとき、
$$ (a,b)\in R\land (b,c)\in S_1 $$
である。
したがって、合成関係の定義より、
$$ (a,c)\in S_1\circ R $$
である。ゆえに、和集合の定義より、
$$ (a,c)\in (S_1\circ R)\cup(S_2\circ R) $$
である。$z=(a,c)$ であるから、
$$ z\in (S_1\circ R)\cup(S_2\circ R) $$
である。
$ $
ii) $(b,c)\in S_2$ の場合
このとき、
$$ (a,b)\in R\land (b,c)\in S_2 $$
である。
したがって、合成関係の定義より、
$$ (a,c)\in S_2\circ R $$
である。ゆえに、和集合の定義より、
$$ (a,c)\in (S_1\circ R)\cup(S_2\circ R) $$
である。$z=(a,c)$ であるから、
$$ z\in (S_1\circ R)\cup(S_2\circ R) $$
である。
$ $
以上より、いずれの場合も、
$$ z\in (S_1\circ R)\cup(S_2\circ R) $$
が成り立つ。$z\in (S_1\cup S_2)\circ R$ は任意であったから、
$$ (S_1\cup S_2)\circ R\subseteq (S_1\circ R)\cup(S_2\circ R) $$
である。
$ $ - $(S_1\circ R)\cup(S_2\circ R)\subseteq (S_1\cup S_2)\circ R$ を示す。
任意に $z\in (S_1\circ R)\cup(S_2\circ R)$ をとる。
和集合の定義より、
$$ z\in S_1\circ R\lor z\in S_2\circ R $$
である。
ここで場合分けを行う。
$ $
i) $z\in S_1\circ R$ の場合
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c) $$
かつ
$$ (a,b)\in R\land (b,c)\in S_1 $$
が成り立つ。
和集合の定義より、
$$ (b,c)\in S_1\cup S_2 $$
である。したがって、
$$ (a,b)\in R\land (b,c)\in S_1\cup S_2 $$
である。
合成関係の定義より、
$$ (a,c)\in (S_1\cup S_2)\circ R $$
である。$z=(a,c)$ であるから、
$$ z\in (S_1\cup S_2)\circ R $$
である。
$ $
ii) $z\in S_2\circ R$ の場合
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c) $$
かつ
$$ (a,b)\in R\land (b,c)\in S_2 $$
が成り立つ。
和集合の定義より、
$$ (b,c)\in S_1\cup S_2 $$
である。したがって、
$$ (a,b)\in R\land (b,c)\in S_1\cup S_2 $$
である。
合成関係の定義より、
$$ (a,c)\in (S_1\cup S_2)\circ R $$
である。$z=(a,c)$ であるから、
$$ z\in (S_1\cup S_2)\circ R $$
である。
$ $
以上より、いずれの場合も、
$$ z\in (S_1\cup S_2)\circ R $$
が成り立つ。
$z\in (S_1\circ R)\cup(S_2\circ R)$ は任意であったから、
$$ (S_1\circ R)\cup(S_2\circ R)\subseteq (S_1\cup S_2)\circ R $$
である。
-1. と 2. より、
$$
(S_1\cup S_2)\circ R=(S_1\circ R)\cup(S_2\circ R)
$$
が成り立つ。
$$ \Box$$
合成 $Q\circ P$ では、右側の $P$ を先に用い、左側の $Q$ を後に用いる。
この命題では、
$$
(S_1\cup S_2)\circ R
$$
の左側、すなわち後に用いる関係が和集合 $S_1\cup S_2$ になっている。
$(a,c)\in(S_1\cup S_2)\circ R$ であるとは、ある $b\in B$ が存在して、
$$
(a,b)\in R
$$
かつ
$$
(b,c)\in S_1\cup S_2
$$
が成り立つことである。ここで、
$$
(b,c)\in S_1\cup S_2
$$
は
$$
(b,c)\in S_1\lor (b,c)\in S_2
$$
と同値である。
したがって、中間元 $b$ を通った後半部分が $S_1$ に属する場合と $S_2$ に属する場合に分かれる。
そのため、
$$
(S_1\cup S_2)\circ R=(S_1\circ R)\cup(S_2\circ R)
$$
が成り立つ。
$A,\ B,\ C$ を集合とし、$R_1,R_2\subseteq A\times B,\ S_1,S_2\subseteq B\times C$ を二項関係とする。
このとき、
$$
(S_1\cup S_2)\circ(R_1\cup R_2)
=
(S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2)
$$
が成り立つ。
集合の外延性により、
$$
(S_1\cup S_2)\circ(R_1\cup R_2)
\subseteq
(S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2)
$$
かつ
$$
(S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2)
\subseteq
(S_1\cup S_2)\circ(R_1\cup R_2)
$$
を示せばよい。
- $(S_1\cup S_2)\circ(R_1\cup R_2)\subseteq (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2)$ を示す。
任意に
$$ z\in (S_1\cup S_2)\circ(R_1\cup R_2) $$
をとる。
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c) $$
かつ
$$ (a,b)\in R_1\cup R_2\land (b,c)\in S_1\cup S_2 $$
が成り立つ。
和集合の定義より、
$$ (a,b)\in R_1\lor (a,b)\in R_2 $$
かつ
$$ (b,c)\in S_1\lor (b,c)\in S_2 $$
である。
ここで場合分けを行う。
$ $
i) $(a,b)\in R_1$ かつ $(b,c)\in S_1$ の場合
このとき、
$$ (a,b)\in R_1\land (b,c)\in S_1 $$
である。
したがって、合成関係の定義より、
$$ (a,c)\in S_1\circ R_1 $$
である。
よって、和集合の定義より、
$$ (a,c)\in (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2) $$
である。$z=(a,c)$ であるから、
$$ z\in (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2) $$
である。
$ $
ii) $(a,b)\in R_2$ かつ $(b,c)\in S_1$ の場合
このとき、
$$ (a,b)\in R_2\land (b,c)\in S_1 $$
である。
したがって、合成関係の定義より、
$$ (a,c)\in S_1\circ R_2 $$
である。
よって、和集合の定義より、
$$ (a,c)\in (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2) $$
である。$z=(a,c)$ であるから、
$$ z\in (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2) $$
である。
$ $
iii) $(a,b)\in R_1$ かつ $(b,c)\in S_2$ の場合
このとき、
$$ (a,b)\in R_1\land (b,c)\in S_2 $$
である。
したがって、合成関係の定義より、
$$ (a,c)\in S_2\circ R_1 $$
である。
よって、和集合の定義より、
$$ (a,c)\in (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2) $$
である。$z=(a,c)$ であるから、
$$ z\in (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2) $$
である。
$ $
iv) $(a,b)\in R_2$ かつ $(b,c)\in S_2$ の場合
このとき、
$$ (a,b)\in R_2\land (b,c)\in S_2 $$
である。
したがって、合成関係の定義より、
$$ (a,c)\in S_2\circ R_2 $$
である。
よって、和集合の定義より、
$$ (a,c)\in (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2) $$
である。$z=(a,c)$ であるから、
$$ z\in (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2) $$
である。
$ $
以上より、いずれの場合も、
$$ z\in (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2) $$
が成り立つ。
$z\in (S_1\cup S_2)\circ(R_1\cup R_2)$ は任意であったから、
$$ (S_1\cup S_2)\circ(R_1\cup R_2) \subseteq (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2) $$
である。
$ $ - $(S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2)\subseteq (S_1\cup S_2)\circ(R_1\cup R_2)$ を示す。
任意に
$$ z\in (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2) $$
をとる。和集合の定義より、
$$ z\in S_1\circ R_1 \lor z\in S_1\circ R_2 \lor z\in S_2\circ R_1 \lor z\in S_2\circ R_2 $$
である。
ここで場合分けを行う。
$ $
i) $z\in S_1\circ R_1$ の場合
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c) $$
かつ
$$ (a,b)\in R_1\land (b,c)\in S_1 $$
が成り立つ。
和集合の定義より、
$$ (a,b)\in R_1\cup R_2 $$
かつ
$$ (b,c)\in S_1\cup S_2 $$
である。したがって、
$$ (a,b)\in R_1\cup R_2\land (b,c)\in S_1\cup S_2 $$
である。
合成関係の定義より、
$$ (a,c)\in (S_1\cup S_2)\circ(R_1\cup R_2) $$
である。$z=(a,c)$ であるから、
$$ z\in (S_1\cup S_2)\circ(R_1\cup R_2) $$
である。
$ $
ii) $z\in S_1\circ R_2$ の場合
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c) $$
かつ
$$ (a,b)\in R_2\land (b,c)\in S_1 $$
が成り立つ。
和集合の定義より、
$$ (a,b)\in R_1\cup R_2 $$
かつ
$$ (b,c)\in S_1\cup S_2 $$
である。したがって、
$$ (a,b)\in R_1\cup R_2\land (b,c)\in S_1\cup S_2 $$
である。
合成関係の定義より、
$$ (a,c)\in (S_1\cup S_2)\circ(R_1\cup R_2) $$
である。$z=(a,c)$ であるから、
$$ z\in (S_1\cup S_2)\circ(R_1\cup R_2) $$
である。
$ $
iii) $z\in S_2\circ R_1$ の場合
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c) $$
かつ
$$ (a,b)\in R_1\land (b,c)\in S_2 $$
が成り立つ。
和集合の定義より、
$$ (a,b)\in R_1\cup R_2 $$
かつ
$$ (b,c)\in S_1\cup S_2 $$
である。したがって、
$$ (a,b)\in R_1\cup R_2\land (b,c)\in S_1\cup S_2 $$
である。
合成関係の定義より、
$$ (a,c)\in (S_1\cup S_2)\circ(R_1\cup R_2) $$
である。$z=(a,c)$ であるから、
$$ z\in (S_1\cup S_2)\circ(R_1\cup R_2) $$
である。
$ $
iv) $z\in S_2\circ R_2$ の場合
合成関係の定義より、ある $a\in A,\ b\in B,\ c\in C$ が存在して、
$$ z=(a,c) $$
かつ
$$ (a,b)\in R_2\land (b,c)\in S_2 $$
が成り立つ。
和集合の定義より、
$$ (a,b)\in R_1\cup R_2 $$
かつ
$$ (b,c)\in S_1\cup S_2 $$
である。したがって、
$$ (a,b)\in R_1\cup R_2\land (b,c)\in S_1\cup S_2 $$
である。
合成関係の定義より、
$$ (a,c)\in (S_1\cup S_2)\circ(R_1\cup R_2) $$
である。$z=(a,c)$ であるから、
$$ z\in (S_1\cup S_2)\circ(R_1\cup R_2) $$
である。
$ $
以上より、いずれの場合も、
$$ z\in (S_1\cup S_2)\circ(R_1\cup R_2) $$
が成り立つ。
$z\in (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2)$ は任意であったから、
$$ (S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2) \subseteq (S_1\cup S_2)\circ(R_1\cup R_2) $$
である。
-1. と 2. より、
$$
(S_1\cup S_2)\circ(R_1\cup R_2)
=
(S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2)
$$
が成り立つ。
$$ \Box$$
合成 $Q\circ P$ では、右側の $P$ を先に用い、左側の $Q$ を後に用いる。
したがって、
$$
(S_1\cup S_2)\circ(R_1\cup R_2)
$$
では、前半に使う関係が $R_1\cup R_2$ であり、後半に使う関係が $S_1\cup S_2$ である。
前半について
$$
(a,b)\in R_1\cup R_2
$$
は
$$
(a,b)\in R_1\lor (a,b)\in R_2
$$
と同値である。また、後半について
$$
(b,c)\in S_1\cup S_2
$$
は
$$
(b,c)\in S_1\lor (b,c)\in S_2
$$
と同値である。したがって、
$$
R_1\text{ から }S_1,\quad R_2\text{ から }S_1,\quad R_1\text{ から }S_2,\quad R_2\text{ から }S_2
$$
の $4$ 通りが現れ、
$$
(S_1\cup S_2)\circ(R_1\cup R_2)
=
(S_1\circ R_1)\cup(S_1\circ R_2)\cup(S_2\circ R_1)\cup(S_2\circ R_2)
$$
が成り立つ。
この記事を高評価した人
この記事に送られたバッジ
投稿者
