2つの関係 R, S が与えられたとき、xRy と ySz がともに成り立つような y が存在するような順序対 (x,z) からなる集合を R と S の合成関係と呼び、これを S∘R で表します。

2019年3月23日:公開

合成関係

集合\(X,Y,Z\)について、\(X\)から\(Y\)への関係\(R\)と、\(Y\)から\(Z\)への関係\(S\)が与えられているとき、それらに対して\(X\)から\(Z\)への関係\(T\)が存在して、任意の順序対\(\left( x,z\right) \in X\times Z\)に対して、\begin{equation*}
\left( x,z\right) \in T\ \Leftrightarrow \ \exists y\in Y:\left[ \left( x,y\right) \in R\ \wedge \ \left( y,z\right) \in S\right] \end{equation*}すなわち、\begin{equation*}
xTz\ \Leftrightarrow \ \exists y\in Y:\left( xRy\ \wedge \ ySz\right)
\end{equation*}が成り立つ場合には、\(T\)を\(R\)と\(S\)の合成関係(composition relation)と呼び、これを\(S\circ R\)で表します。

合成関係の定義より、\begin{equation*}
S\circ R=\{\left( x,z\right) \in X\times Z\ |\ \exists y\in Y:\left( xRy\ \wedge \ ySz\right) \}
\end{equation*}となります。つまり、\(xRy\)と\(ySz\)がともに成り立つような\(y\)が存在するような順序対\(\left( x,z\right) \)からなる集合が\(S\circ R\)です。

関係\(R,S\)の合成\(S\circ R\)を考える際には、\(R\)の終集合と\(S\)の始集合が一致している必要があります。上の定義においても、\(R\)の終集合と\(S\)の始集合はともに\(Y\)で一致しています。

関係\(R,S\)に対して\(S\circ R\)と\(R\circ S\)を区別する必要があります。\(R\)が\(X\)から\(Y\)への関係、\(S\)が\(Y\)から\(Z\)への関係であるとしましょう。このとき、\(R\)の終集合と\(S\)の始集合はともに\(Y\)で一致するため合成関係\(S\circ R\)は定義可能です。一方、\(S\)の終集合\(Z\)と\(R\)の始集合\(X\)は一致するとは限らないため合成関係\(R\circ S\)を定義できるとは限りません。

例(関係の合成)
\(X=\{1,2,3,4\},\ Y=\{a,b,c,d\},\ Z=\{5,6,7,8\}\)とします。その上で、\(X\)から\(Y\)への関係\(R\)を、\begin{equation*}
R=\{\left( 1,a\right) ,\left( 1,b\right) ,\left( 2,a\right) ,\left( 3,d\right) ,\left( 4,d\right) \}
\end{equation*}と定義し、\(Y\)から\(Z\)への関係\(S\)を、\begin{equation*}
S=\{\left( b,5\right) ,\left( b,6\right) ,\left( c,8\right) ,\left( d,7\right) \}
\end{equation*}と定義します。このとき、\(b\in Y\)について\(\left( 1,b\right) \in R\)と\(\left( b,5\right) \in S\)が成り立つため\(\left( 1,5\right) \in S\circ R\)です。また、やはり\(b\in Y\)について\(\left( 1,b\right) \in R\)と\(\left( b,6\right) \in S\)がともに成り立つため\(\left( 1,6\right) \in S\circ R\)です。同様に考えると、\begin{equation*}
S\circ R=\{\left( 1,5\right) ,\left( 1,6\right) ,\left( 3,7\right) ,\left( 4,7\right) \}
\end{equation*}となります。

 

二項関係の合成

二項関係どうしの合成を考えることもできます。同一の集合\(X\)上に定義された関係\(R,S\)について、\begin{eqnarray*}
S\circ R &=&\{\left( x,z\right) \in X^{2}\ |\ \exists y\in X:\left( xRy\ \wedge \ ySz\right) \} \\
R\circ S &=&\{\left( x,z\right) \in X^{2}\ |\ \exists y\in X:\left( xSy\ \wedge \ yRz\right) \}
\end{eqnarray*}などとなります。やはり\(R\circ S\)と\(S\circ R\)は一致するとは限りません。

例(方程式の合成)
\(\mathbb{R}\)上の二項関係\(R\)を、任意の順序対\(\left( x,y\right) \in \mathbb{R}\times \mathbb{R}\)に対して、\begin{equation*}
xRy\ \Leftrightarrow \ x^{2}+y^{2}=1
\end{equation*}を満たすものとして定義します。同様に、\(\mathbb{R}\)上の二項関係\(S\)を、任意の順序対\(\left( y,z\right) \in \mathbb{R}\times \mathbb{R}\)に対して、\begin{equation*}
ySz\ \Leftrightarrow \ 2y+3z=4
\end{equation*}を満たすものとして定義します。

\(S\circ R\)は\(xRy\)かつ\(ySz\)であるような\(y\)が存在するような\(\left( x,z\right) \)からなる集合です。2つの方程式\begin{eqnarray*}
xRy &:&x^{2}+y^{2}=1 \\
ySz &:&2y+3z=4
\end{eqnarray*}から\(y\)を消去して得られる方程式\begin{equation*}
4x^{2}+\left( 4-3z\right) ^{2}=4
\end{equation*}が成立するとき、先の2つの方程式をともに満たす\(y\)が存在します。したがって、\begin{equation*}
S\circ R=\{\left( x,z\right) \in \mathbb{R}^{2}\ |\ 4x^{2}+(4-3z)^{2}=4\}
\end{equation*}となります。

\(R\circ S\)は\(xSy\)かつ\(yRz\)であるような\(y\)が存在するような\(\left( x,z\right) \)からなる集合です。2つの方程式\begin{eqnarray*}
xSy &:&2x+3y=4 \\
yRz &:&y^{2}+z^{2}=1
\end{eqnarray*}から\(y\)を消去して得られる方程式\begin{equation*}
\left( 4-2x\right) ^{2}+9z^{2}=9
\end{equation*}が成立するとき、先の2つの方程式をともに満たす\(y\)が存在します。したがって、\begin{equation*}
R\circ S=\{\left( x,z\right) \in \mathbb{R}^{2}\ |\ \left( 4-2x\right) ^{2}+9z^{2}=9\}
\end{equation*}となります。

例(関係と逆関係の合成)
\(\mathbb{N}\)上の二項関係\(R\)を、任意の順序対\(\left( x,y\right) \in \mathbb{N} ^{2}\)に対して、\begin{equation*}
xRy\ \Leftrightarrow \ xx
\end{equation*}となります。このとき、任意の\(\left( a,b\right) \in \mathbb{N} ^{2}\)に対して、\begin{eqnarray*}
\left( a,b\right) \in R^{-1}\circ R &\Leftrightarrow &\exists c\in \mathbb{N} :\left( aRc\ \wedge \ cR^{-1}b\right) \quad \because \circ \text{の定義} \\
&\Leftrightarrow &\exists c\in \mathbb{N} :\left( a<c\ \wedge \ c>b\right) \quad \because R,R^{-1}\text{の定義} \\
&\Leftrightarrow &a\in \mathbb{N} \ \wedge \ b\in \mathbb{N} \\
&\Leftrightarrow &\left( a,b\right) \in \mathbb{N} ^{2}\quad \because \times \text{の定義}
\end{eqnarray*}すなわち、\(R^{-1}\circ R=\mathbb{N} ^{2}\)となります。他方で、\begin{eqnarray*}
\left( a,b\right) \in R\circ R^{-1} &\Leftrightarrow &\exists c\in \mathbb{N} :\left( aR^{-1}c\ \wedge \ cRb\right) \quad \because \circ \text{の定義} \\
&\Leftrightarrow &\exists c\in \mathbb{N} :\left( a>c\ \wedge \ c<b\right) \quad \because R,R^{-1}\text{の定義} \\
&\Leftrightarrow &a\not=1\ \wedge \ b\not=1 \\
&\Leftrightarrow &a\in \mathbb{N} \backslash \{1\}\wedge b\in \mathbb{N} \backslash \{1\} \\
&\Leftrightarrow &\left( z,b\right) \in \left( \mathbb{N} \backslash \{1\}\right) \times \left( \mathbb{N}
\backslash \{1\}\right) \quad \because \times \text{の定義}
\end{eqnarray*}すなわち、\(R\circ R^{-1}=\left( \mathbb{N} \backslash \{1\}\right) \times \left( \mathbb{N} \backslash \{1\}\right) \)となります。

次回は合成関係の性質について解説します。
次へ進む 演習問題(プレミアム会員限定)