二項関係

同義語：binary relation

概要

二項関係（binary relation）とは、「2つの対象の間に関係があるか否か」を、直積集合の部分集合として定式化した概念である。等号・大小関係・整除・合同など数学に現れるあらゆる「関係」の共通の土台であり、写像・同値関係・順序集合はいずれも特別な性質を持つ二項関係として定義される。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 集合, 直積集合, 部分集合

定義

二項関係

集合 $A, B$ に対し、直積集合の部分集合 $R \subset A \times B$ を $A$ から $B$ への二項関係 (binary relation) という。$(a,b) \in R$ のとき「$a$ と $b$ は関係 $R$ にある」といい、$a \mathrel{R} b$ と書く。特に $A = B$ のとき、$R \subset A \times A$ を $A$ 上の二項関係という。

「関係がある」という直観的な言い回しを、「関係にある組の一覧表」＝部分集合そのものと同一視するのがこの定義の要点である。
$A$ 上の二項関係 $R$ について、よく使われる性質に名前がついている。

関係の基本的な性質

$A$ 上の二項関係 $R$ が

  1. 反射的 (reflexive): すべての $a \in A$ で $a \mathrel{R} a$
  2. 対称的 (symmetric): $a \mathrel{R} b$ ならば $b \mathrel{R} a$
  3. 推移的 (transitive): $a \mathrel{R} b$ かつ $b \mathrel{R} c$ ならば $a \mathrel{R} c$
  4. 反対称的 (antisymmetric): $a \mathrel{R} b$ かつ $b \mathrel{R} a$ ならば $a = b$
    であるとは、それぞれ上の条件が成り立つことをいう。

反射・対称・推移を満たすものが同値関係、反射・反対称・推移を満たすものが順序集合（半順序）である。この2系統が二項関係の最重要の特殊化である。

直感

二項関係が認識しているのは、「数学的構造とは、集合の上の関係の指定である」という事実そのものである。集合それ自体はただの砂の山であり、順序・同値・隣接・対応といった一見バラバラな「構造」は、すべて「どの組が関係にあるかの一覧」という同一の形式に還元される。数理論理学が構造（モデル）を「集合＋関係の解釈」と定義するのは、この認識の徹底に他ならない。二項関係は、構造という言葉に最初の厳密な意味を与える概念である。
具体的には、二項関係とは「◯と◯は関係がある」と宣言された組の一覧表である。$A, B$ が有限なら、行を $A$、列を $B$ とする表に◯×を書き込んだもの（隣接行列）や、$A$ の元から $B$ の元へ矢印を引いた図（有向グラフ）と同じ情報になる。実際、離散数学の有向グラフは「頂点集合上の二項関係」そのものである。
初学者が誤解しやすい点を挙げる。

  • 写像は二項関係の特別な場合である。$f \colon A \to B$ のグラフ $\{(a, f(a)) \mid a \in A\}$ は $A$ から $B$ への二項関係であり、逆に「どの $a \in A$ にもちょうど1つの $b$ が対応する」関係が写像に他ならない。「関係の方が写像より広い」という包含の向きを押さえておくと、逆写像や部分写像の議論が整理される。
  • 性質1〜4は独立に成り立ったり成り立たなかったりする。対称かつ反対称な関係も存在し（等号がそう）、どちらでもない関係も普通にある。「対称でなければ反対称」ではない。
  • 反射性は台集合 $A$ に依存する。同じ組の一覧でも、$A$ を広げれば反射的でなくなり得る。関係は常に「どの集合の上か」とセットで考える。

例

等号と大小関係

$\mathbb{R}$ 上の等号 $=$ は反射・対称・推移・反対称をすべて満たす。大小関係 $\le$ は反射・推移・反対称だが対称でない（順序集合の原型）。狭義の $<$ は推移的だが反射的でない。

整除と合同

$\mathbb{Z}$ 上で「$a$ は $b$ を割り切る」（整除関係）は反射・推移的だが、対称でも（$\mathbb{Z}$ 上では）反対称でもない（$2 \mid {-2}$ かつ $-2 \mid 2$ だが $2 \neq -2$）。一方、法 $n$ の合同式 $a \equiv b \pmod n$ は反射・対称・推移を満たす同値関係である。

写像のグラフ

写像 $f \colon A \to B$ のグラフ $G_f = \{(a, f(a)) \mid a \in A\} \subset A \times B$ は二項関係である。二項関係 $R \subset A \times B$ が写像のグラフであるための条件は「各 $a \in A$ に対し $a \mathrel{R} b$ なる $b \in B$ がちょうど1つ存在する」ことである。

空関係と全関係

$R = \emptyset$（どの組も関係にない）と $R = A \times A$（すべての組が関係にある）も二項関係である。空関係は $A \neq \emptyset$ のとき反射的でないが、対称・推移・反対称はすべて（空虚に）満たす。「条件が空虚に成立する」ことの練習台として重要な例である。

非例：3つ以上の対象の間の関係

「点 $B$ が点 $A$ と点 $C$ の間にある」（間性）のように3つの対象が絡む関係は、二項関係では表せない。これは直積 $A \times A \times A$ の部分集合、すなわち3項関係として定式化される。一般に $n$ 項関係が同様に定義され、数理論理学の構造（モデル）では任意の項数の関係を扱う。

性質

逆関係と合成

$R \subset A \times B$ に対し、逆関係 $R^{-1} = \{(b,a) \mid (a,b) \in R\} \subset B \times A$ が定まる。また $R \subset A \times B$、$S \subset B \times C$ に対し、合成
$$ S \circ R = \{(a,c) \in A \times C \mid \text{ある } b \in B \text{ が存在して } a \mathrel{R} b \text{ かつ } b \mathrel{S} c\} $$
が定まる。写像のグラフに対してはこれらは逆写像・合成写像と整合する。合成は結合的であり、集合を対象、二項関係を射とする圏（関係の圏 Rel）が得られる。

推移閉包

$A$ 上の任意の二項関係 $R$ に対し、$R$ を含む最小の推移的関係（推移閉包）が存在する。同様に反射閉包・対称閉包も存在する（推移閉包（関係））。関係を「望みの性質を持つ最小の関係」に拡げる操作は、同値関係の生成やグラフの到達可能性の解析で基本的である。

なお、代数・論理・離散数学のそれぞれで二項関係は別の顔を持つ。代数では同値関係を経由して合同・商構造の土台となり、離散数学では有向グラフ・隣接行列と同一視されてアルゴリズムの対象になり、数理論理学では構造の解釈として意味論の基本単位になる。関係そのものを射とみなす関係の圏 Relの視点は圏論に属する。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する

Mathpediaを支援する
二項関係