4.4 二項関係

二項関係 (binary relation) は二つのモノに関する関係を定義する。例えば実数に関する「未満」という二項関係は実数 \(a\), \(b\) が \(a < b\) を満たすのはどんなときかを定義する。同様に、「部分集合」という二項関係は集合 \(A\), \(B\) が \(A \subseteq B\) を満たすのがどんなときかを定義する。関数 \(f \colon A \to B \) も二項関係の一種であり、\(a \in A\) と \(b \in B\) は \(b = f(a)\) を満たすときに限って二項関係 \(f\) を持つと解釈できる。

本節では二項関係に関する語彙と性質を見ていく。

始域 \(A\) と終域 \(B\) を持つ関係は「\(A\) と \(B\) の関係」や「\(A\) から \(B\) への関係」と呼ばれる。関数と同様に、\(R\colon A \to B\) は \(R\) が \(A\) から \(B\) への関係であることを意味する。始域と終域が同じ集合 \(A\) である関係を「\(A\) 上の関係」と呼ぶ。関係 \(R\) のグラフに組 \((a, b)\) が含まれることは \(a \mathrel{R} b\) と表記される¹。

定義 4.4.1 は第 4.3.1 項で示した関数の定義とよく似ており、関数では始域の任意の要素に関係付けられる終域の要素が \(1\) 個以下である点だけが異なる。先述の通り、関数は二項関係の一種である。

手頃な例として、「2010 年夏学期に MIT で講義を担当する」を表す関係 \(Chrg\) を考えよう。この関係の始域は MIT の教授と講師の名前全体の集合 \(\text{Fac}\) で、終域は 2009 年冬学期と 2010 年夏学期に開講される講義の講義番号全体の集合 \(\text{SubNums}\) だとする。このとき \(Chrg\) のグラフは次の形をした組だけを含む:

この組は \(\langle \text{担当者の名前} \rangle\) が \(\langle \text{講義番号} \rangle\) を担当することを意味する。例えば次のような組が含まれる:

終域 \(\text{SubNums}\) に含まれる講義番号の中には、リスト \(\text{(4.4)}\) に示した組の第 \(2\) 要素として使われていないものが存在する ── 2009 年冬学期にだけ開講される講義の講義番号である。同様に、始域 \(\text{Fac}\) に含まれる名前の中にはリスト \(\text{(4.4)}\) に示した組の第 \(1\) 要素に含まれないものが存在する ── 彼らは 2010 年夏学期に講義を一つも担当しない。

4.4.1 二項関係の図示

二項関係を表す図を描くと、その基礎的な性質が分かりやすくなる。二項関係 \(R\) を表す図では、\(R\) の始域の要素を表す点を左側に一列に書き、\(R\) の終域の要素を表す点を右側に一列に書き、グラフに属する組 \((a, b)\) ごとに \(a\) に対応する点から \(b\) に対応する点に向かう矢印を書いた図が使われることが多い。二つの関数を表す図を示す:

「関数である」は二項関係に関する重要な特徴の一つである。これは図において、左側に並んだ任意の点から右に向かう矢印が \(1\) 本以下であることを意味する。この条件を省略して「外向き矢印が \(1\) 本以下」と表記する。二項関係に関する頻出の特徴が他に四つあり、どれも図示したときの矢印の本数を使って定義できる:

ここからは「外向き矢印が \(1\) 本以下」や「内向き矢印が \(1\) 本以上」をさらに省略して「外 \(\leq 1\)」や「内 \(\geq 1\)」などと書く。

上図左の関係は「外 \(= 1\)」と「内 \(\geq 1\)」を満たすので、全射かつ全域な関数である。一方で \(3\) に向かう矢印が \(2\) 本あるので「内 \(\leq 1\)」は満たされない。つまり、この関係は単射でない。

上図右の関係は「外 \(= 1\)」と「内 \(\leq 1\)」を満たすので、単射かつ全域な関数である。一方で \(4\) に向かう矢印が存在しないので「内 \(\geq 1\)」は満たされない。つまり、この関係は全射でない。

二項関係 \(R\) の図に含まれる矢印は当然それぞれが異なる \(R\) のグラフの要素に対応する。しかし、矢印だけに関する情報だけでは「外 \(\geq 1\)」といった条件を判定できないことに注意してほしい。始域と終域の各要素がどれだけ矢印を持つかは矢印に関する情報だけからは分からない。言い換えれば、\(R\) の全単射性などの特徴は \(\text{graph(R)}\) を知っただけでは決定しない: \(\operatorname{domain}(R)\) や \(\operatorname{codomain}(R)\) も知る必要がある。

4.4.2 二項関係の像

関数による集合の像という概念は二項関係にもそのまま拡張できる。

例えば、2010 年夏学期に MIT で Meyer が担当する講義の番号全体の集合は、関係 \(Chrg\) による集合 \(\left\{ \texttt{A.\;R.\;Meyer} \right\}\) の像 \(Chrg(\left\{ \texttt{A.\;R.\;Meyer} \right\})\) である。この集合の要素を実際に見つけるには、二項関係 \(Chrg\) を図示して \(\texttt{A.\;R.\;Meyer}\) に対応する点から出る矢印の終点に注目すればよい。\(\operatorname{graph}(Chrg)\) を示したリスト \(\text{(4.4)}\) からは、\(Chrg(\left\{ \texttt{A.\;R.\;Meyer} \right\})\) が \(\left\{6.042,\ 18.062,\ 6.844\right\}\) を部分集合に持つと分かる (関係 \(Chrg\) のグラフがリスト \(\text{(4.4)}\) に全て示されているわけではないので、ここでは部分集合関係しか言えない)。同様に、Freeman または Eng が担当する講義を見つけるには、\(\texttt{G.\;Freeman}\) または \(\texttt{T.\;Eng}\) に対応する点から出る矢印の終点になっている講義番号を収集すればよい。この集合は \(Chrg(\left\{\texttt{G.\;Freeman},\ \texttt{T.\;Eng}\right\})\) であり、リスト \(\text{(4.4)}\) からは次が分かる:

最後に、\(\text{Fac}\) は講義を担当できる教授・講師全体の集合なので、\(Chrg(\text{Fac})\) は 2010 年夏学期に MIT で開講される講義の番号全体の集合となる。

逆関係と逆像

別の言い方をすれば、\(R\) を表す図で矢印の方向を反転させることで得られる二項関係が \(R^{-1}\) である。

講義の担当者の例を続けると、2010 年夏学期に MIT で 6.UAT を担当する人物全体の集合は \(Chrg\) における \(\left\{\text{6.UAT}\right\}\) の逆像に等しい。リスト \(\text{(4.4)}\) によると、Eng と Freeman は 6.UAT の担当者である。つまり次の関係が成り立つ:

MIT では入門講義が \(\text{6.0}\) で始まる番号を持つ。\(\text{Intro}\) を入門講義全体の集合とすれば、2010 年夏学期の入門講義の担当者全体の集合は \(Chrg^{-1}(\text{Intro})\) に等しい。リスト \(\text{(4.4)}\) からは、Meyer, Leighton, Freeman, Guttag が 2010 年夏学期の入門講義を担当すると分かる。つまり次の関係が成り立つ:

最後に、\(Chrg^{-1}(\text{SubNums})\) は 2010 年夏学期に MIT で何らかの講義を担当する教授・講師全体の集合に等しい。