WIIS

教材一覧
教材一覧
教材検索
RELATION

合成関係

目次

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

合成関係

集合\(A\)から集合\(B\)への関係\(R\)と、集合\(B\)から集合\(C\)への関係\(S\)が与えられた状況を想定します。すなわち、\(R\subset A\times B\)かつ\(S\subset B\times C\)です。このとき、\(\left( a,b\right) \in R\)と\(\left( b,c\right) \in S\)をともに満たす\(b\in B\)が存在するような順序対\(\left( a,c\right) \in A\times C\)からなる集合\begin{equation*}\left\{ \left( a,c\right) \in A\times C\ |\ \exists b\in B:\left[ \left(
a,b\right) \in R\wedge \left( b,c\right) \in S\right] \right\}
\end{equation*}は\(A\times C\)の部分集合であるため、これは\(A\)から\(C\)への関係です。そこで、このような関係を\(R\)と\(S\)の合成関係(composition relation)と呼び、これを、\begin{equation*}S\circ R
\end{equation*}と表記します。定義より、任意の順序対\(\left( a,c\right) \in A\times 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*}という関係が成り立ちます。つまり、合成関係\(S\circ R\)のもとで\(a\)が\(c\)と関係を持つことは、関係\(R\)のもとで\(a\)が\(b\)と関係を持つとともに、関係\(S\)のもとで\(b\)と\(c\)が関係を持つような\(b\)が存在することと必要十分です。

例(合成関係)
3つの企業の社員からなる集合をそれぞれ\(A,B,C\)で表します。その上で、\(A\)から\(B\)への関係\(R\)を、それぞれの\(\left(a,b\right) \in A\times B\)について、\begin{equation*}R\left( a,b\right) \Leftrightarrow a\text{は}b\text{と知り合い}
\end{equation*}を満たすものとして定義し、\(B\)から\(C\)への関係\(S\)を、それぞれの\(\left( b,c\right) \in B\times C\)について、\begin{equation*}S\left( b,c\right) \Leftrightarrow b\text{は}c\text{と知り合い}
\end{equation*}を満たすものとして定義します。このとき、合成関係\(S\circ R\)は\(A\)から\(C\)への関係であり、それぞれの\(\left( a,c\right) \in A\times C\)について、\begin{eqnarray*}\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] \quad \because
\text{合成関係の定義} \\
&\Leftrightarrow &\exists b\in B:\left( a\text{は}b\text{と知り合い}\wedge b\text{は}c\text{と知り合い}\right) \quad \because R\text{および}S\text{の定義} \\
&\Leftrightarrow &a\text{と}c\text{の共通の知り合いが}B\text{にいる}
\end{eqnarray*}となります。つまり、合成関係\(S\circ R\)は、企業\(B\)に共通の知り合いがいるような企業\(A\)の社員\(a\)と企業\(C\)の社員\(c\)からなる順序対\(\left( a,c\right) \)からなる集合です。
例(合成関係)
集合\(A,B,C\)をそれぞれ、\begin{eqnarray*}A &=&\left\{ 1,2,3,4\right\} \\
B &=&\left\{ p,q,r,s\right\} \\
C &=&\left\{ 5,6,7,8\right\}
\end{eqnarray*}と定義します。\(A\)から\(B\)への関係\(R\)が、\begin{equation*}R=\left\{ \left( 1,p\right) ,\left( 1,q\right) ,\left( 2,p\right) ,\left(
3,s\right) ,\left( 4,s\right) \right\}
\end{equation*}で与えられており、\(B\)から\(C\)への関係\(S\)が、\begin{equation*}S=\{\left( q,5\right) ,\left( q,6\right) ,\left( s,7\right) ,\left(
r,8\right) \}
\end{equation*}で与えられているものとします。このとき、合成関係\(S\circ R\)は\(A\)から\(C\)への関係であり、\begin{eqnarray*}S\circ R &=&\left\{ \left( a,c\right) \in A\times C\ |\ \exists b\in B:\left[
\left( a,b\right) \in R\wedge \left( b,c\right) \in S\right] \right\} \\
&=&\left\{ \left( 1,5\right) ,\left( 1,6\right) ,\left( 3,7\right) ,\left(
4,7\right) \right\}
\end{eqnarray*}となります。

関係\(R,S\)に対して\(S\circ R\)と\(R\circ S\)を区別する必要があります。集合\(A,B,C\)が与えられたとき、\(R\)が\(A\)から\(B\)への関係、\(S\)が\(B\)から\(C\)への関係であるものとします。このとき、\(R\)の終集合と\(S\)の始集合はともに\(B\)で一致するため合成関係\(S\circ R\)が定義可能です。一方、\(S\)の終集合\(C\)と\(R\)の始集合\(A\)は一致するとは限らないため、合成関係\(R\circ S\)は定義できるとは限りません。一方、集合\(A\)上に定義された2つの二項関係\(R,S\)に関しては、\(R\)および\(S\)の始集合と終集合が\(A\)で一致するため、合成関係である\(R\circ S\)と\(S\circ R\)が常に定義可能です。

例(二項関係どうしの合成関係)
二項関係も関係であるため、その合成関係が定義可能です。具体的には、集合\(A\)上の二項関係\(R,S\)はともに直積\(A\times A\)の部分集合として定義されますが、それらの合成関係\(S\circ R\)もまた集合\(A\)上の二項関係であり、\begin{eqnarray*}S\circ R &=&\left\{ \left( x,z\right) \in A\times A\ |\ \exists y\in B:\left[
\left( x,y\right) \in R\wedge \left( y,z\right) \in S\right] \right\} \\
&=&\left\{ \left( x,z\right) \in A\times A\ |\ \exists y\in B:\left[ R\left(
x,y\right) \wedge S\left( y,z\right) \right] \right\}
\end{eqnarray*}となります。また、\(S\circ R\)とは合成の順番を逆にした合成関係\(R\circ S\)もまた\(A\)上の二項関係であり、\begin{eqnarray*}R\circ S &=&\left\{ \left( x,z\right) \in A\times A\ |\ \exists y\in B:\left[
\left( x,y\right) \in S\wedge \left( y,z\right) \in R\right] \right\} \\
&=&\left\{ \left( x,z\right) \in A\times A\ |\ \exists y\in B:\left[ S\left(
x,y\right) \wedge R\left( y,z\right) \right] \right\}
\end{eqnarray*}と定義されます。両者は一致するとは限りません。

例(二項関係どうしの合成関係)
すべての人間からなる集合\(A\)上の二項関係\(R\)を、それぞれの順序対\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\text{は}y\text{の子供である}
\end{equation*}を満たすものとして定義します。このとき、合成関係\(R\circ R\)もまた\(A\)上の二項関係であり、それぞれの順序対\(\left( x,z\right) \in A\times A\)に対して、\begin{eqnarray*}\left( R\circ R\right) \left( x,z\right) &\Leftrightarrow &\exists y\in A:
\left[ R\left( x,y\right) \wedge R\left( y,z\right) \right] \quad \because
\text{合成関係の定義} \\
&\Leftrightarrow &\exists y\in A:\left[ x\text{は}y\text{の子供である}\wedge y\text{は}z\text{の子供である}\right] \quad \because R\text{の定義} \\
&\Leftrightarrow &x\text{は}z\text{の孫である}
\end{eqnarray*}となります。

例(二項関係どうしの合成関係)
実数空間\(\mathbb{R} \)上の二項関係\(R\)を、それぞれの順序対\(\left( x,y\right)\in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x^{2}+y^{2}=1
\end{equation*}を満たすものとして定義し、やはり\(\mathbb{R} \)上の二項関係\(S\)を、それぞれの順序対\(\left( y,z\right)\in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}S\left( y,z\right) \Leftrightarrow 2y+3z=4
\end{equation*}を満たすものとして定義します。このとき、合成関係\(S\circ R\)もまた\(\mathbb{R} \)上の二項関係であり、それぞれの順序対\(\left( x,z\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{eqnarray*}\left( S\circ R\right) \left( x,z\right) &\Leftrightarrow &\exists y\in \mathbb{R} :\left[ R\left( x,y\right) \wedge S\left( y,z\right) \right] \quad \because
S\circ R\text{の定義} \\
&\Leftrightarrow &\exists y\in \mathbb{R} :\left[ x^{2}+y^{2}+1\wedge 2y+3z=4\right] \quad \because R,S\text{の定義} \\
&\Leftrightarrow &4x^{2}+\left( 4-3z\right) ^{2}=4\quad \because y\text{を消去}
\end{eqnarray*}となります。一方、合成関係\(R\circ S\)もまた\(\mathbb{R} \)上の二項関係であり、それぞれの順序対\(\left( x,z\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{eqnarray*}\left( R\circ S\right) \left( x,z\right) &\Leftrightarrow &\exists y\in \mathbb{R} :\left[ S\left( x,y\right) \wedge R\left( y,z\right) \right] \quad \because
S\circ R\text{の定義} \\
&\Leftrightarrow &\exists y\in \mathbb{R} :\left[ 2x+3y=4\wedge y^{2}+z^{2}=1\right] \quad \because R,S\text{の定義} \\
&\Leftrightarrow &\left( 4-2x\right) ^{2}+9z^{2}=9\quad \because y\text{を消去}
\end{eqnarray*}となります。

 

関係の合成に関する結合律

集合\(A,B,C,D\)に対して、関係\(R,S,T\)の始集合と終集合がそれぞれ、\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}を得ます。つまり、関係\(R,S,T\)の中の隣り合うどの2つを最初に合成するか応じて、最終的に\(\left( 1\right) \)もしくは\(\left( 2\right) \)という合成関係が得られます。これらはともに\(A\)から\(D\)への関係ですが、実は、両者は一致します(演習問題にします)。

命題(関係の合成に関する結合律)
集合\(A,B,C,D\)について、\(A\)から\(B\)への関係\(R\)、\(B\)から\(C\)への関係\(S\)、\(C\)から\(D\)への関係\(T\)がそれぞれ任意に与えられたとき、\begin{equation*}T\circ \left( S\circ R\right) =\left( T\circ S\right) \circ R
\end{equation*}が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

集合の合成を表す記号\(\circ \)を関係を被演算子とする演算子とみなしたとき、上の命題は、\(\circ \)が結合律(associative law)を満たすことを示唆しています。つまり、上の命題中の条件を満たす関係\(R,S,T\)の中の隣り合うどの2つを最初に合成しても最終的に得られる合成関係が等しいため、それらを区別せずに、\begin{equation*}T\circ S\circ R
\end{equation*}で表します。

例(関係の合成に関する結合律)
集合\(A,B,C,D,E\)について、関係\(R,S,T,U\)の始集合と終集合がそれぞれ、\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 \\
&=&U\circ \left( \left( T\circ S\right) \circ R\right) \\
&=&U\circ \left( T\circ \left( S\circ R\right) \right)
\end{eqnarray*}という関係が得られます。そこで、これら4つの合成関係を区別せずに、\begin{equation*}
U\circ T\circ S\circ R
\end{equation*}で表すことができます。5つ以上の関係についても同様に考えます。

 

合成関係の逆関係

集合\(A,B,C\)に対して、関係\(R,S\)の始集合と終集合がそれぞれ、\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\)への関係ですが、実は、これらは一致します。

命題(合成関係の逆関係)
集合\(A,B,C\)について、\(A\)から\(B\)への関係\(R\)と、\(R\)から\(C\)への関係\(S\)がそれぞれ任意に与えられたとき、\begin{equation*}(S\circ R)^{-1}=R^{-1}\circ S^{-1}
\end{equation*}という関係が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(合成関係の逆関係)
集合\(A,B,C\)がそれぞれ、\begin{eqnarray*}A &=&\left\{ 1,2,3,4\right\} \\
B &=&\left\{ p,q,r,s\right\} \\
C &=&\left\{ 5,6,7,8\right\}
\end{eqnarray*}で与えられており、\(A\)から\(B\)への関係\(R\)が、\begin{equation*}R=\left\{ \left( 1,p\right) ,\left( 1,q\right) ,\left( 2,p\right) ,\left(
3,s\right) ,\left( 4,s\right) \right\}
\end{equation*}で与えられており、\(B\)から\(C\)への関係\(S\)が、\begin{equation*}S=\left\{ \left( q,5\right) ,\left( q,6\right) ,\left( r,8\right) ,\left(
s,7\right) \right\}
\end{equation*}で与えられています。このとき、\begin{equation*}
S\circ R=\left\{ \left( 1,5\right) ,\left( 1,6\right) ,\left( 3,7\right)
,\left( 4,7\right) \right\}
\end{equation*}であるため、\begin{equation*}
\left( S\circ R\right) ^{-1}=\left\{ \left( 5,1\right) ,\left( 6,1\right)
,\left( 7,3\right) ,\left( 7,4\right) \right\}
\end{equation*}となります。一方、\begin{eqnarray*}
R^{-1} &=&\left\{ \left( p,1\right) ,\left( q,1\right) ,\left( p,2\right)
,\left( s,3\right) ,\left( s,4\right) \right\} \\
S^{-1} &=&\left\{ \left( 5,q\right) ,\left( 6,q\right) ,\left( 8,r\right)
,\left( 7,s\right) \right\}
\end{eqnarray*}であるため、\begin{equation*}
R^{-1}\circ S^{-1}=\left\{ \left( 5,1\right) ,\left( 6,1\right) ,\left(
7,3\right) ,\left( 7,4\right) \right\}
\end{equation*}となります。以上より、\begin{equation*}
\left( S\circ R\right) ^{-1}=R^{-1}\circ S^{-1}
\end{equation*}が成り立ちますが、この結果は先の命題と整合的です。

 

演習問題

問題(合成関係)
自然数空間\(\mathbb{N} \)上の二項関係\(R\)が、\begin{equation*}R=\left\{ \left( 1,4\right) ,\left( 3,7\right) ,\left( 4,5\right) ,\left(
4,6\right) ,\left( 7,6\right) \right\}
\end{equation*}で与えられています。関連して、以下の問いに答えてください。

  1. \(R\)の定義域\(D\left( R\right) \)と値域\(R\left( R\right) \)をそれぞれ求めてください。
  2. \(R\)の逆関係\(R^{-1}\)を求めてください。
  3. 合成関係\(R\circ R\)を求めてください。
  4. 合成関係\(R^{-1}\circ R\)を求めてください。
  5. 合成関係\(R\circ R^{-1}\)を求めてください。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(合成関係)
集合\(A,B\)がそれぞれ、\begin{eqnarray*}A &=&\left\{ 1,2,3,4\right\} \\
B &=&\left\{ 1,3,5\right\}
\end{eqnarray*}で与えられているものとします。その上で、\(A\)から\(B\)への関係\(R\)を、それぞれの順序対\(\left( a,b\right) \in A\times B\)に対して、\begin{equation*}\left( a,b\right) \in R\Leftrightarrow a<b
\end{equation*}を満たすものとして定義します。関連して以下の問いに答えてください。

  1. \(R\)の要素を列挙してください。
  2. \(R\)の定義域\(D\left( R\right) \)と値域\(R\left( R\right) \)の要素をそれぞれ列挙してください。
  3. 逆関係\(R^{-1}\)の要素を列挙してください。
  4. 合成関係\(R\circ R\)の要素を列挙してください。
  5. 合成関係\(R^{-1}\circ R\)の要素を列挙してください。
  6. 合成関係\(R\circ R^{-1}\)の要素を列挙してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(合成関係)
自然数空間\(\mathbb{N} \)上の二項関係\(R\)を、それぞれの順序対\(\left( x,y\right)\in \mathbb{N} \times \mathbb{N} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x<y
\end{equation*}を満たすものとして定義します。このとき、\(R^{-1}\circ R\)と\(R^{-1}\circ R\)をそれぞれ求めてください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(合成関係)
自然数空間\(\mathbb{N} \)上の関係\(R\)が、任意の順序対\(\left( x,y\right) \in \mathbb{N} \times \mathbb{N} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x+2y=12
\end{equation*}を満たすものとして定義されています。ただし、\(\mathbb{N} =\left\{ 1,2,3,\cdots \right\} \)です。関連して以下の問いに答えてください。

  1. \(R\)の要素を列挙してください。
  2. \(R\)の定義域\(D\left( R\right) \)と値域\(R\left( R\right) \)の要素をそれぞれ列挙してください。
  3. 逆関係\(R^{-1}\)の要素を列挙してください。
  4. 合成関係\(R\circ R\)の要素を列挙してください。
  5. 合成関係\(R^{-1}\circ R\)の要素を列挙してください。\(R^{-1}\circ R\)
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(合成関係)
実数空間\(\mathbb{R} \)上の関係\(R\)が、任意の順序対\(\left( x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow 0\leq x-y\leq 1
\end{equation*}を満たすものとして定義されています。関連して以下の問いに答えてください。

  1. \(R\)を直積\(\mathbb{R} \times \mathbb{R} \)の部分集合として記述してください。
  2. \(R^{-1}\)を直積\(\mathbb{R} \times \mathbb{R} \)の部分集合として記述してください。
  3. \(R\circ R^{-1}\)を直積\(\mathbb{R} \times \mathbb{R} \)の部分集合として記述すると、\begin{equation*}R \circ R^{-1}= \left\{ \left( x,z \right) \in \mathbb{R} \times \mathbb{R} \ |\ \left \vert x-z\right\vert \leq 1\right \}\end{equation*}
  4. になることを証明してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

次回から同値関係について学びます。

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

二項関係
関係の定義

複数の物事が互いに関わり合っている状態を関係と呼びますが、数学において関係とは、2つの集合の直積の部分集合として定式化されます。

二項関係
二項関係

始集合と終集合が一致する関係を二項関係と呼びます。二項関係は与えられた集合の直積の部分集合として定義されます。

二項関係
関係どうしの演算

関係は集合として定義されるため、関係に対して通常の集合演算が適用可能です。補関係、共通関係、和関係、差関係などの概念を定義します。

合成写像
合成写像

集合 A から集合 B への写像 f:A→B と、集合 B から集合 C への写像 g:B→C が与えられたとき、A のそれぞれの要素 a に対して C の要素である g(f(a)) を像として定める写像を作ることができるため、これを f と g の合成写像と呼びます。

二項関係
二項関係の推移律

集合A上の二項関係Rのもとで、Aの任意の要素x,y,zについて、xがyと関係を持つとともにyがzと関係を持つ場合にxとzが関係を持つことが保証されるならば、Rは推移律を満たすと言います。推移律を満たす二項関係の例を挙げます。

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

関係