二項関係
一般に、複数の物事が互いに関わり合っている状態を関係（relation）と呼びますが、これを数学的にどのように定式化できるでしょうか。いくつか具体例を挙げた上で、後に話を一般化します。
\end{equation*}を作ります。男性\(m\)と女性\(w\)は夫婦であるか否かのどちらか一方です。そこで、夫婦であるような男女を成分とする順序対\(\left(m,w\right) \)からなる集合を、\begin{equation*}R=\left\{ \left( m,w\right) \in M\times W\ |\ m\text{と}w\text{は夫婦である}\right\}
\end{equation*}と表記します。これは直積\(M\times W\)の部分集合です。このとき、任意の男女\(m,w\)について、以下の関係\begin{eqnarray*}\left( m,w\right) &\in &R\Leftrightarrow m\text{と}w\text{は夫婦である} \\
\left( m,w\right) &\not\in &R\Leftrightarrow m\text{と}w\text{は夫婦ではない}
\end{eqnarray*}が成り立ちます。このような\(M\times W\)の部分集合\(R\)が与えられれば、任意の男女\(m,w\)について、彼らが夫婦であるか判定できます。したがって、この集合\(R\)は婚姻関係を総体的に記述することに成功しています。
\end{equation*}を作ります。\(e<o\)は成立するか否かのどちらか一方です。例えば、\begin{equation*}\left( e,o\right) =\left( 2,3\right)
\end{equation*}については\(2<3\)が成立する一方で、\begin{equation*}\left( e,o\right) =\left( 2,1\right)
\end{equation*}については\(2<1\)は成立しません。そこで、\(e<o\)が成立するような順序対\(\left( e,o\right) \)からなる集合を、\begin{equation*}R=\left\{ \left( e,o\right) \in E\times O\ |\ e<o\right\}
\end{equation*}と表記します。これは直積\(E\times O\)の部分集合です。このとき、任意の偶数\(e\)と奇数\(o\)について、以下の関係\begin{eqnarray*}\left( e,o\right) &\in &R\Leftrightarrow e<o \\
\left( e,o\right) &\not\in &R\Leftrightarrow \lnot \left( e<o\right)
\end{eqnarray*}が成り立ちます。このような\(E\times O\)の部分集合\(R\)が与えられれば、任意の偶数\(e\)と奇数\(o\)について\(e<o\)が成立するか否かを判定できます。したがって、この集合\(R\)は偶数と奇数の間の大小関係を記述することに成功しています。
以上の2つの例が示唆するように、2つの集合\(A,B\)が与えられたとき、それらの要素の間の関係は直積\(A\times B\)の部分集合\begin{equation*}R\subset A\times B
\end{equation*}として総体的に記述できます。このような事情を念頭においた上で、一般に、問題としている2つの集合\(A,B\)が与えられたとき、\(A\)から\(B\)への関係（relation from \(A\) to \(B\)）という概念を直積\(A\times B\)の部分集合\(R\)として定義します。
集合\(A\)の要素\(a\)と集合\(B\)の要素\(b\)をそれぞれ任意に選んだとき、順序対\(\left( a,b\right) \)が関係\(R\)の要素である場合、すなわち、\begin{equation*}\left( a,b\right) \in R
\end{equation*}が成り立つ場合、\(R\)のもとで\(a\)と\(b\)は関係を持つ（\(a\) is related to \(b\) by \(R\)）や、\(a\)と\(b\)は関係\(R\)にあるなどと言い、そのことを、\begin{equation*}R\left( a,b\right) ,\quad aRb
\end{equation*}などで表記します。つまり、\begin{equation*}
R\left( a,b\right) \Leftrightarrow aRb\Leftrightarrow \left( a,b\right) \in R
\end{equation*}です。したがって、\begin{eqnarray*}
R &=&\left\{ \left( a,b\right) \in A\times B\ |\ R\left( a,b\right) \right\}
\\
&=&\left\{ \left( a,b\right) \in A\times B\ |\ aRb\right\}
\end{eqnarray*}という関係が成り立ちます。
逆に、順序対\(\left( a,b\right) \)が関係\(R\)の要素でない場合、すなわち、\begin{equation*}\left( a,b\right) \not\in R
\end{equation*}が成り立つ場合、\(R\)のもとで\(a\)と\(b\)は関係を持たない（not related）と言い、そのことを\(\lnot R\left( a,b\right) \)や\(\lnot \left( aRb\right) \)などで表記します。つまり、\begin{equation*}\lnot R\left( a,b\right) \Leftrightarrow \lnot \left( aRb\right)
\Leftrightarrow \left( a,b\right) \not\in R
\end{equation*}です。したがって、\begin{eqnarray*}
R^{c} &=&\left\{ \left( a,b\right) \in A\times B\ |\ \lnot R\left(
a,b\right) \right\} \\
&=&\left\{ \left( a,b\right) \in A\times B\ |\ \lnot \left( aRb\right)
\right\}
\end{eqnarray*}という関係が成り立ちます。ただし、\(R^{c}\)は\(R\)の補集合です。
集合\(A\)から集合\(B\)への関係\(R\subset A\times B\)が与えられたとき、\(A\)を\(R\)の始集合（initial set）と呼び、\(B\)を\(R\)の終集合（final set）と呼びます。正式には、始集合が\(A\)で終集合が\(B\)であるような関係を、\begin{equation*}\left( R,A,B\right)
\end{equation*}と表記しますが、始集合\(A\)と終集合\(B\)が文脈から明らかである場合、関係をシンプルに、\begin{equation*}R
\end{equation*}と表記できます。
R=\left\{ \left( 1,2\right) \right\}
\end{equation*}を、\begin{equation*}
R\subset \left\{ 1\right\} \times \left\{ 2\right\}
\end{equation*}とみなす場合、\(R\)の始集合は\(\left\{ 1\right\} \)であり終集合は\(\left\{ 2\right\} \)です。一方、\begin{equation*}R\subset \left\{ 1,3\right\} \times \left\{ 2,4\right\}
\end{equation*}とみなす場合、\(R\)の始集合は\(\left\{ 1,3\right\} \)であり終集合は\(\left\{ 2,4\right\} \)です。つまり、同一の順序対集合\(R\)に対して異なる始集合および終集合が設定可能であるため、関係\(R\)を定義する際には始集合と終集合を明示する必要があります。このような事情もあり、厳密には関係は単なる集合\(R\)だけでなく、\begin{equation*}\left( R,A,B\right)
\end{equation*}として捉える必要があります。ただし、\(A,B\)が文脈から明らかである場合には、これをシンプルに、\begin{equation*}R
\end{equation*}と表記できるということです。
集合\(A\)から集合\(B\)への関係\(R\)は2つの集合の要素どうしの関係を規定する概念であるため、これを二項関係（binary relation）と呼ぶ場合もあります。3つ以上の集合の要素どうしを規定する関係概念を定義することもできますが、それについては場を改めて解説します。以降において「関係」と言う場合、特に断りのない場合、それは二項関係を表します。
関係\(R\)の始集合\(A\)と終集合\(B\)は異なる集合である必要はありません。始集合\(A\)と終集合\(B\)が一致する場合、そのような関係を自己関係（endorelation）と呼ぶ場合もあります。自己関係については場を改めて解説します。
W &=&\left\{ w_{1},w_{2},w_{3}\right\}
\end{eqnarray*}で与えられているものとします。さらにこの関係\(R\)は、それぞれの\(\left( m,w\right) \in M\times W\)について、\begin{equation*}R\left( m,w\right) \Leftrightarrow m\text{と}w\text{は夫婦である}
\end{equation*}を満たすものとして定義されているものとします。つまり、\(m\)と\(w\)が夫婦であるとき、そしてその場合にのみ\(R\)のもとで\(m\)と\(w\)は関係を持つということです。仮に\(m_{1}\)と\(w_{2}\)、\(m_{2}\)と\(w_{3}\)がそれぞれ夫婦であり、他の全員が独身であるならば、\begin{eqnarray*}R &=&\left\{ \left( m,w\right) \in M\times W\ |\ m\text{と}w\text{は夫婦である}\right\} \\
&=&\left\{ \left( m_{1},w_{2}\right) ,\left( m_{2},w_{3}\right) \right\}
\end{eqnarray*}となります。その一方で、例えば、\begin{eqnarray*}
\left( m_{1},w_{1}\right) &\not\in &R \\
\left( m_{2},w_{2}\right) &\not\in &R \\
\left( m_{3},w_{3}\right) &\not\in &R
\end{eqnarray*}などが成り立ちます。
B &=&\left\{ 2,4,6\right\}
\end{eqnarray*}で与えられているものとします。さらにこの関係\(R\)は、それぞれの\(\left( a,b\right) \in A\times B\)について、\begin{equation*}R\left( a,b\right) \Leftrightarrow a<b
\end{equation*}を満たすものとして定義されているものとします。つまり、\(a\)が\(b\)よりも小さいとき、そしてその場合にのみ\(R\)のもとで\(a\)と\(b\)は関係を持つということです。このとき、\begin{eqnarray*}R &=&\left\{ \left( a,b\right) \in A\times B\ |\ a<b\right\} \\
&=&\left\{ \left( 1,2\right) ,\left( 1,4\right) ,\left( 1,6\right) ,\left(
3,4\right) ,\left( 3,6\right) ,\left( 5,6\right) \right\}
\end{eqnarray*}となります。その一方で、例えば、\begin{eqnarray*}
\left( 3,2\right) &\not\in &R \\
\left( 5,2\right) &\not\in &R \\
\left( 5,4\right) &\not\in &R
\end{eqnarray*}などが成り立ちます。
以上の例では「婚姻関係」「大小関係」など、私たちが慣れ親しんでいる具体的な関係を数学的な関係として定式化しましたが、数学においては2つの集合の直積の部分集合であれば、それはいかなるものでも関係とみなされる点に注意してください。
A &=&\left\{ 1,2,3,4,5\right\} \\
B &=&\left\{ a,b,c,e,d\right\}
\end{eqnarray*}が与えられたとき、\begin{equation*}
R=\left\{ \left( 1,b\right) ,\left( 1,c\right) ,\left( 3,d\right) ,\left(
4,c\right) ,\left( 5,a\right) \right\}
\end{equation*}は直積\(A\times B\)の部分集合であるため、これは\(A\)から\(B\)への関係です。また、空集合は任意の集合の部分集合であることから、\begin{equation*}\phi \subset A\times B
\end{equation*}が成り立ちますが、これは\(\phi \)が\(A\)から\(B\)への関係であることを意味します。さらに、\begin{equation*}A\times B\subset A\times B
\end{equation*}が成り立ちますが、これは\(A\times B\)が\(A\)から\(B\)への関係であることを意味します。直積\(A\times B\)の任意の部分集合は\(A\)から\(B\)への関係です。その一方で、\begin{equation*}S=\left\{ \left( 1,a\right) ,\left( 2,b\right) ,\left( c,3\right) \right\}
\end{equation*}は\(A\)から\(B\)への関係ではありません。なぜなら、\begin{equation*}\left( c,3\right) \not\in A\times B
\end{equation*}であり、したがって\(S\)は\(A\times B\)の部分集合ではないからです。
関係の定義域
集合\(A\)から集合\(B\)への関係\(R\)が与えられたとき、\(R\)のもとで何らかの\(B\)の要素と関係を持つ\(A\)の要素からなる集合を、\begin{eqnarray*}D\left( R\right) &=&\left\{ a\in A\ |\ \exists b\in B:\left( a,b\right) \in
R\right\} \\
&=&\left\{ a\in A\ |\ \exists b\in B:R\left( a,b\right) \right\}
\end{eqnarray*}で表記し、これを\(R\)の定義域（domain）と呼びます。関係\(R\)の定義域を表す記号としては、\begin{equation*}D\left( R\right) ,\quad \mathrm{dom}\left( R\right) ,\quad D_{R}
\end{equation*}などが使われます。定義より、任意の\(a\in A\)について、\begin{eqnarray*}a\in D\left( R\right) &\Leftrightarrow &\exists b\in B:\left( a,b\right)
\in R \\
&\Leftrightarrow &\exists b\in B:R\left( a,b\right)
\end{eqnarray*}という関係が成り立ちます。つまり、\(R\)の定義域とは、\(R\)の要素である順序対の第1成分からなる集合です。
W &=&\left\{ w_{1},w_{2},w_{3}\right\}
\end{eqnarray*}で与えられているものとします。さらにこの関係\(R\)は、それぞれの\(\left( m,w\right) \in M\times W\)について、\begin{equation*}R\left( m,w\right) \Leftrightarrow m\text{と}w\text{は夫婦である}
\end{equation*}を満たすものとして定義されているものとします。仮に\(m_{1}\)と\(w_{2} \)、\(m_{2}\)と\(w_{3}\)がそれぞれ夫婦であり、他の全員が独身であるならば、\begin{equation*}R=\left\{ \left( m_{1},w_{2}\right) ,\left( m_{2},w_{3}\right) \right\}
\end{equation*}となるため、\(R\)の定義域は、\begin{equation*}D\left( R\right) =\left\{ m_{1},m_{2}\right\}
\end{equation*}です。これは結婚している男性からなる集合です。
B &=&\left\{ 2,4,6\right\}
\end{eqnarray*}で与えられているものとします。さらにこの関係\(R\)は、それぞれの\(\left( a,b\right) \in A\times B\)について、\begin{equation*}R\left( a,b\right) \Leftrightarrow a<b
\end{equation*}を満たすものとして定義されているものとします。このとき、\begin{equation*}
R=\left\{ \left( 1,2\right) ,\left( 1,4\right) ,\left( 1,6\right) ,\left(
3,4\right) ,\left( 3,6\right) ,\left( 5,6\right) \right\}
\end{equation*}となるため、\(R\)の定義域は、\begin{equation*}D\left( R\right) =\left\{ 1,3,5\right\}
\end{equation*}です。
関係の値域
集合\(A\)から集合\(B\)への関係\(R\)が与えられたとき、\(R\)のもとで何らかの\(A\)の要素と関係を持つ\(B\)の要素からなる集合を、\begin{eqnarray*}R\left( R\right) &=&\left\{ b\in B\ |\ \exists a\in A:\left( a,b\right) \in
R\right\} \\
&=&\left\{ b\in B\ |\ \exists a\in A:R\left( a,b\right) \right\}
\end{eqnarray*}で表し、これを\(R\)の値域（range）と呼びます。関係\(R\)の値域を表す記号としては、\begin{equation*}R\left( R\right) ,\quad \mathrm{ran}\left( R\right) ,\quad R_{R}
\end{equation*}などが使われます。定義より、任意の\(b\in B\)について、\begin{eqnarray*}b\in R\left( R\right) &\Leftrightarrow &\exists a\in A:\left( a,b\right)
\in R \\
&\Leftrightarrow &\exists a\in A:R\left( a,b\right)
\end{eqnarray*}という関係が成り立ちます。つまり、\(R\)の値域とは、\(R\)の要素であるそれぞれの順序対の第2成分からなる集合です。
W &=&\left\{ w_{1},w_{2},w_{3}\right\}
\end{eqnarray*}で与えられているものとします。さらにこの関係\(R\)は、それぞれの\(\left( m,w\right) \in M\times W\)について、\begin{equation*}R\left( m,w\right) \Leftrightarrow m\text{と}w\text{は夫婦である}
\end{equation*}を満たすものとして定義されているものとします。仮に\(m_{1}\)と\(w_{2} \)、\(m_{2}\)と\(w_{3}\)がそれぞれ夫婦であり、他の全員が独身であるならば、\begin{equation*}R=\left\{ \left( m_{1},w_{2}\right) ,\left( m_{2},w_{3}\right) \right\}
\end{equation*}となるため、\(R\)の値域は、\begin{equation*}R\left( R\right) =\left\{ w_{2},w_{3}\right\}
\end{equation*}です。これは結婚している女性からなる集合です。
B &=&\left\{ 2,4,6\right\}
\end{eqnarray*}で与えられているものとします。さらにこの関係\(R\)は、それぞれの\(\left( a,b\right) \in A\times B\)について、\begin{equation*}R\left( a,b\right) \Leftrightarrow a<b
\end{equation*}を満たすものとして定義されているものとします。このとき、\begin{equation*}
R=\left\{ \left( 1,2\right) ,\left( 1,4\right) ,\left( 1,6\right) ,\left(
3,4\right) ,\left( 3,6\right) ,\left( 5,6\right) \right\}
\end{equation*}となるため、\(R\)の値域は、\begin{equation*}R\left( R\right) =\left\{ 2,4,6\right\}
\end{equation*}です。
演習問題
A &=&\left\{ 1,2,3\right\} \\
B &=&\left\{ a,b\right\}
\end{eqnarray*}を考えます。次の集合が\(A\)から\(B\)への関係であるか判定してください。
- \(R=\left\{ \left( 1,a\right) ,\left( 2,b\right) ,\left( 3,a\right)\right\} \)
- \(S=\left\{ \left( 1,a\right) ,\left( a,2\right) \right\} \)
- \(T=\phi \)
A &=&\left\{ 1,2,3,4,5\right\} \\
B &=&\left\{ 2,3,4,5,6\right\}
\end{eqnarray*}を考えます。\(A\)から\(B\)への関係を、\begin{equation*}aRb\Leftrightarrow b=2a
\end{equation*}により定義します。\(R\)を求めた上で、さらに\(R\)の定義域と値域を特定してください。
S=\left\{ s_{1},s_{2},s_{3}\right\}
\end{equation*}とし、授業科目の集合を、\begin{equation*}
C=\left\{ c_{1},c_{2},c_{3},c_{4}\right\}
\end{equation*}とします。学生\(s\in S\)が科目\(c\in C\)を履修しているという関係\(R\)を、\begin{equation*}sRc\Leftrightarrow s\text{は}c\text{を履修している}
\end{equation*}により定義します。さらに、\begin{equation*}
R=\left\{ \left( s_{1},c_{1}\right) ,\left( s_{1},c_{3}\right) ,\left(
s_{2},c_{1}\right) ,\left( s_{3},c_{2}\right) \right\}
\end{equation*}であるものとします。\(R\)の定義域と値域を求めた上で、それらの意味を説明してください。
B &=&\left\{ 3,4,5,6\right\}
\end{eqnarray*}で与えられているものとします。さらにこの関係\(R\)は、それぞれの\(\left( a,b\right) \in A\times B\)について、\begin{equation*}R\left( a,b\right) \Leftrightarrow a+b\leq 6
\end{equation*}を満たすものとして定義されているものとします。\(R\)の要素を明らかにするとともに、\(R\)の定義域と値域を明らかにしてください。
B &=&\left\{ 2,4,6\right\}
\end{eqnarray*}で与えられているものとします。さらにこの関係\(R\)は、それぞれの\(\left( a,b\right) \in A\times B\)について、\begin{equation*}R\left( a,b\right) \Leftrightarrow a=b
\end{equation*}を満たすものとして定義されているものとします。\(R\)の要素を明らかにするとともに、\(R\)の定義域と値域を明らかにしてください。
\end{equation*}を満たすものとして定義します。企業\(A\)の社長と企業\(B\)の社長はお互いに知り合いですが、それ以外に企業間での知り合いは存在しません。\(R\)の要素を明らかにするとともに、\(R\)の定義域と値域を明らかにしてください。
\end{equation*}が成り立つことを証明してください。
