二項関係どうしの合成関係

二項関係どうしの合成関係

集合\(A\)から集合\(B\)への二項関係\(R\)と、集合\(B\)から集合\(C\)への二項関係\(S\)が与えられた状況を想定します。すなわち、\begin{eqnarray*}R &\subset &A\times B \\
S &\subset &B\times C
\end{eqnarray*}です。このとき、集合\(A\)から集合\(C\)への二項関係\begin{equation*}T\subset A\times C
\end{equation*}を、任意の\(a\in A\)および\(c\in C\)に対して、\begin{equation*}\left( a,c\right) \in T\Leftrightarrow \exists b\in B:\left[ \left(
a,b\right) \in R\wedge \left( b,c\right) \in S\right] \end{equation*}すなわち、\begin{equation*}
T\left( a,c\right) \Leftrightarrow \exists b\in B:\left[ R\left( a,b\right)
\wedge S\left( b,c\right) \right] \end{equation*}を満たすものとして定義します。つまり、新たに定義した二項関係\(T\)のもとで\(a\)が\(c\)と関係を持つことは、\(R\)のもとで\(a\)と関係を持つとともに\(S\)のもとで\(c\)と関係を持つような\(b\)が存在することは必要十分です。このような二項関係を\(R\)と\(S\)の合成関係（composition relation）と呼び、これを、\begin{equation*}S\circ R
\end{equation*}で表記します。定義より、任意の\(a\in A\)および\(c\in C\)に対して、\begin{equation*}\left( a,c\right) \in S\circ R\Leftrightarrow \exists b\in B:\left[ \left(
a,b\right) \in R\wedge \left( b,c\right) \in S\right] \end{equation*}すなわち、\begin{equation*}
\left( S\circ R\right) \left( a,c\right) \Leftrightarrow \exists b\in B:
\left[ R\left( a,b\right) \wedge S\left( b,c\right) \right] \end{equation*}という関係が成り立ちます。したがって、\begin{equation*}
S\circ R=\left\{ \left( a,c\right) \in A\times C\ |\ \exists b\in B:\left[
R\left( a,b\right) \wedge S\left( b,c\right) \right] \right\}
\end{equation*}です。

始集合と終集合が同一の集合であるような二項関係、すなわち自己関係\(R\subset A\times A\)については、2つの二項関係\begin{eqnarray*}R &\subset &A\times A \\
R &\subset &A\times A
\end{eqnarray*}の合成関係\(R\circ R\subset A\times A\)が定義可能であり、これは任意の\(x,y\in A\)に対して、\begin{equation*}\left( R\circ R\right) \left( x,y\right) \Leftrightarrow \exists z\in A:
\left[ R\left( x,z\right) \wedge R\left( z,y\right) \right] \end{equation*}を満たします。したがって、\begin{equation*}
R\circ R=\left\{ \left( x,y\right) \in A\times A\ |\ \exists z\in A:\left[
R\left( x,z\right) \wedge R\left( z,y\right) \right] \right\}
\end{equation*}です。

二項関係どうしは合成できるとは限らない

2つの二項関係\begin{eqnarray*}
R &\subset &A\times B \\
S &\subset &B\times C
\end{eqnarray*}が与えられた場合、\(R\)の終集合と\(S\)の始集合は同一の集合\(B\)であるため合成関係\begin{equation*}S\circ R\subset A\times C
\end{equation*}は常に定義可能である一方、\(R\)の終集合\(C\)と\(S\)の始集合\(A\)は一致するとは限らないため合成関係\begin{equation*}R\circ S\subset B\times B
\end{equation*}は定義可能であるとは限りません。

二項関係の合成は交換律を満たさない

始集合と終集合が同一の集合であるような2つの二項関係\begin{eqnarray*}
R &\subset &A\times A \\
S &\subset &A\times A
\end{eqnarray*}が与えられたとき、2つの二項関係\begin{eqnarray*}
S\circ R &\subset &A\times A \\
R\circ S &\subset &A\times A
\end{eqnarray*}がともに定義可能ですが、これらは異なる二項関係です。実際、\begin{eqnarray*}
S\circ R &=&\left\{ \left( x,y\right) \in A\times A\ |\ \exists z\in
A:\left( x,z\right) \in R\wedge \left( z,y\right) \in S\right\} \\
R\circ S &=&\left\{ \left( x,y\right) \in A\times A\ |\ \exists z\in
A:\left( x,z\right) \in S\wedge \left( z,y\right) \in R\right\}
\end{eqnarray*}であり、この2つの集合は一致するとは限りません。したがって、2つの二項関係\(R,S\)を合成する際には順番に注意する必要があります。

二項関係の合成は結合律を満たす

集合\(A,B,C,D\)に加えて3つの二項関係\begin{eqnarray*}R &\subset &A\times B \\
S &\subset &B\times C \\
T &\subset &C\times D
\end{eqnarray*}で与えられているものとします。

\(R\)の終集合と\(S\)の始集合はともに\(B\)であるため、\(R\)と\(S\)の合成関係\begin{equation*}S\circ R\subset A\times C
\end{equation*}が定義可能です。得られた合成関係\(S\circ R\)の終集合と残された二項関係\(T\)の始集合はともに\(C\)であるため、\(S\circ R\)と\(T\)の合成関係\begin{equation}T\circ \left( S\circ R\right) \subset A\times D \quad \cdots (1)
\end{equation}が定義可能です。

\(S\)の終集合と\(T\)の始集合はともに\(C\)であるため、\(S\)と\(T\)の合成関係\begin{equation*}T\circ S\subset B\times D
\end{equation*}が定義可能です。残された二項関係\(R\)の終集合と合成関係\(T\circ S\)の始集合はともに\(B\)であるため、\(R\)と\(T\circ S\)の合成関係\begin{equation}\left( T\circ S\right) \circ R\subset A\times D \quad \cdots (2)
\end{equation}が定義可能です。

つまり、3つの二項関係\(R,S,T\)を合成する場合、隣り合うどの2つの二項関係を最初に合成するかに応じて、最終的に\(\left( 1\right) \)または\(\left( 2\right) \)が得られます。実は、\(\left( 1\right) \)と\(\left( 2\right) \)は二項関係として等しくなることが保証されます。つまり、\begin{equation*}T\circ \left( S\circ R\right) =\left( T\circ S\right) \circ R
\end{equation*}が成り立つということです。二項関係の合成に関する以上の性質を結合律（associative law）と呼びます。

合成可能な3つの二項関係\(R,S,T\)が与えられたとき、二項関係の合成\(\circ \)の結合律より、\begin{equation*}T\circ \left( S\circ R\right) =\left( T\circ S\right) \circ R
\end{equation*}が成り立つことが明らかになりました。つまり、\(T\circ \left( S\circ R\right) \)と\(\left( T\circ S\right) \circ R\)は二項関係として等しいため両者を区別する必要はなく、これらをまとめて、\begin{equation*}T\circ S\circ R
\end{equation*}と表記できるものと定めます。

集合\(A,B,C,D,E\)に加えて4つの二項関係\begin{eqnarray*}R &\subset &A\times B \\
S &\subset &B\times C \\
T &\subset &C\times D \\
U &\subset &D\times E
\end{eqnarray*}が与えられたとき、二項関係の合成\(\circ \)に関する結合律を繰り返し適用することにより、\begin{eqnarray*}\left( \left( U\circ T\right) \circ S\right) \circ R &=&\left( U\circ \left(
T\circ S\right) \right) \circ R\quad \because \text{結合律}
\\
&=&U\circ \left( \left( T\circ S\right) \circ R\right) \quad \because \text{結合律} \\
&=&U\circ \left( T\circ \left( S\circ R\right) \right) \quad \because \text{結合律}
\end{eqnarray*}を得ます。つまり、合成可能な4つの二項関係\(R,S,T,U\)を合成する場合、\(R,S,T,U\)の間にある3個の\(\circ \)の中のどれを最初に作用させる場合でも、最終的に得られる合成関係は二項関係として等しくなることが保証されるため、これら4つの合成関係を区別せずに、\begin{equation*}U\circ T\circ S\circ R
\end{equation*}で表記します。

任意の有限個の二項関係の合成についても同様の議論が成立します。つまり、合成可能な有限\(n\)個の二項関係\(R_{1},\cdots ,R_{n}\)の間にある\(n-1\)個の\(\circ \)の中のどれを最初に作用させる場合でも、最終的に得られる合成関係は二項関係として等しくなることが保証されるため、それらの合成関係を区別せずに、\begin{equation*}R_{1}\circ \cdots \circ R_{n}
\end{equation*}で表記します。

合成関係の逆関係

集合\(A,B,C\)に加えて2つの二項関係\begin{eqnarray*}R &\subset &A\times B \\
S &\subset &B\times C
\end{eqnarray*}が与えられているとき、これらの合成は、\begin{equation*}
S\circ R\subset A\times C
\end{equation*}であり、さらにその逆関係は、\begin{equation}
\left( S\circ R\right) ^{-1}\subset C\times A \quad \cdots (1)
\end{equation}となります。一方、\(R\)と\(S\)それぞれの逆関係は、\begin{eqnarray*}R^{-1} &\subset &B\times A \\
S^{-1} &\subset &C\times B
\end{eqnarray*}ですが、\(S^{-1}\)の終集合と\(R^{-1}\)の始集合はともに\(B\)であるため、以下の合成関係\begin{equation}R^{-1}\circ S^{-1}\subset C\times A \quad \cdots (2)
\end{equation}が定義可能です。\(\left(1\right) \)と\(\left( 2\right) \)はともに\(C\)から\(A\)への関係ですが、実は、これらは一致します。

演習問題