二項関係

同義語:binary relation

概要

二項関係(binary relation)とは、集合 $A,B$ の直積の部分集合 $R\subset A\times B$ のことであり、「どの組が関係にあるか」の一覧として関係を定式化したものである。反射性・対称性・推移性・反対称性の組合せから同値関係や順序が得られ、写像は各元にちょうど一つの元が対応する二項関係として特徴づけられる。逆関係と合成は結合律や $(S\circ R)^{-1}=R^{-1}\circ S^{-1}$ を満たし、各性質は対角集合・逆関係・合成の包含として言い換えられ、推移閉包は $R$ の冪の合併で与えられる。$n$ 元集合上の反射的・対称的・反対称的な関係の個数も数えられ、合成は可換でなく、推移閉包と対称閉包はとる順序で結果が変わる。

$$\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$ の元について「$a$ と $b$ は関係にある」という言い方を、関係にある組 $(a,b)$ の全体、すなわち直積 $A\times B$ の部分集合として表したものである。実数の大小 $\le$ や整数の整除、写像のグラフ、頂点集合上の有向グラフの辺の集合などが、この形で書ける。

定義

二項関係

集合 $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$ 上の二項関係という(Ham 定義 11.1、p. 202、定義 11.7、p. 221)。

「関係がある」という直観的な言い回しを、「関係にある組の一覧表」=部分集合そのものと同一視するのがこの定義の要点である。
$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$
    であるとは、それぞれ上の条件が成り立つことをいう(1〜3 は Ham 定義 11.2、p. 205)。

反射・対称・推移を満たすものが同値関係、反射・反対称・推移を満たすものが順序集合(半順序)である。この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つ存在する」ことである。写像をこの条件を満たす関係として定義する流儀もある(Ham 定義 12.1、p. 224)。

空関係と全関係

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

反例:3つ以上の対象の間の関係

「点 $q$ が点 $p$ と点 $r$ の間にある」(間性)のように3つの対象が絡む関係は、平面の点全体を $A$ とするとき、2つの対象の組の集合($A \times A$ の部分集合)ではないので、二項関係では表せない。これは直積 $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\} $$
が定まる。写像のグラフに対してはこれらは逆写像・合成写像と整合する。合成は結合的であり、集合を対象、二項関係を射とする圏が得られる。さらに次が成り立つ。

  1. $T\circ(S\circ R)=(T\circ S)\circ R$($T\subset C\times D$)。
  2. 対角集合 $\Delta_A=\{(a,a)\mid a\in A\}$ について $R\circ\Delta_A=R=\Delta_B\circ R$。
  3. $(S\circ R)^{-1}=R^{-1}\circ S^{-1}$、$(R^{-1})^{-1}=R$。
  4. 写像 $f\colon A\to B$、$g\colon B\to C$ のグラフについて $G_g\circ G_f=G_{g\circ f}$。
  1. $(a,d)\in T\circ(S\circ R)$ とは、ある $c$ で $(a,c)\in S\circ R$ かつ $cTd$、すなわち、ある $b,c$ で $aRb$、$bSc$、$cTd$ となることである。$(a,d)\in(T\circ S)\circ R$ も、ある $b$ で $aRb$ かつ $(b,d)\in T\circ S$、すなわち、ある $b,c$ で $aRb$、$bSc$、$cTd$ となることである。両者は同じ条件なので等しい。
  2. $(a,b)\in R\circ\Delta_A$ とは、ある $a'$ で $a=a'$ かつ $a'Rb$、すなわち $aRb$ のことである。右側も同様。
  3. $(c,a)\in(S\circ R)^{-1}$ $\iff$ $(a,c)\in S\circ R$ $\iff$ ある $b$ で $aRb$ かつ $bSc$ $\iff$ ある $b$ で $cS^{-1}b$ かつ $bR^{-1}a$ $\iff$ $(c,a)\in R^{-1}\circ S^{-1}$。逆の逆はもとに戻る。
  4. $(a,c)\in G_g\circ G_f$ とは、ある $b$ で $b=f(a)$ かつ $c=g(b)$ となること、すなわち $c=g(f(a))$ のことである。$\square$

3 の順序の入れ替わりは、靴下と靴の関係(履くときと脱ぐときで順が逆)と同じで、逆写像の公式 $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$ の関係版である。
関係の性質は、上の操作を使うと集合の包含として書ける。これは性質を機械的に確かめたり、閉包を作ったりするときに便利である。

性質の包含による言い換え

$A$ 上の二項関係 $R$ について、次が成り立つ。

  1. $R$ が反射的 $\iff$ $\Delta_A\subset R$。
  2. $R$ が対称的 $\iff$ $R^{-1}\subset R$ $\iff$ $R^{-1}=R$。
  3. $R$ が推移的 $\iff$ $R\circ R\subset R$。
  4. $R$ が反対称的 $\iff$ $R\cap R^{-1}\subset\Delta_A$。
  1. と 3. は定義をそのまま書き直したものである(3 は「ある $b$ で $aRb$ かつ $bRc$ なら $aRc$」)。2:対称的なら $(b,a)\in R^{-1}$ すなわち $aRb$ から $bRa$、つまり $(b,a)\in R$ なので $R^{-1}\subset R$。逆に $R^{-1}\subset R$ なら定義どおり対称的である。さらに $R^{-1}\subset R$ の両辺の逆をとると $R\subset R^{-1}$(逆をとる操作は包含を保ち、逆の逆はもとに戻る)なので $R^{-1}=R$。4:$(a,b)\in R\cap R^{-1}$ とは $aRb$ かつ $bRa$ のことなので、反対称律「$aRb$ かつ $bRa$ なら $a=b$」は $R\cap R^{-1}\subset\Delta_A$ と同じである。$\square$
推移閉包

$A$ 上の任意の二項関係 $R$ に対し、$R$ を含む最小の推移的関係(推移閉包)$R^{+}$ が存在し、
$$ R^{+}=\bigcup_{n\ge1}R^{n},\qquad R^{1}=R,\quad R^{n+1}=R\circ R^{n} $$
で与えられる。すなわち $aR^{+}b$ となるのは、有限列 $a=x_0,x_1,\dots,x_n=b$($n\ge1$)で各 $k$ について $x_{k-1}Rx_k$ となるものがあるとき、かつそのときに限る。同様に反射閉包 $R\cup\Delta_A$、対称閉包 $R\cup R^{-1}$ も存在する。関係を「望みの性質を持つ最小の関係」に拡げる操作は、同値関係の生成やグラフの到達可能性の解析で基本的である。

推移閉包についての主張は、推移閉包(二項関係) の定理「推移閉包の鎖による表示」の 1・2 である(証明はそちら)。反射閉包・対称閉包については、$R\cup\Delta_A$ が反射的、$R\cup R^{-1}$ が対称的($(R\cup R^{-1})^{-1}=R^{-1}\cup R$)である。$R$ を含む反射的関係 $T$ は命題「性質の包含による言い換え」の 1 により $\Delta_A\subset T$ なので $R\cup\Delta_A\subset T$ であり、$R$ を含む対称的関係 $T$ は同じ命題の 2 により $R^{-1}\subset T^{-1}=T$ なので $R\cup R^{-1}\subset T$ である。$\square$

閉包をとる順序には注意が要る。対称閉包の推移閉包 $(R\cup R^{-1})^{+}$ は対称的であるが、推移閉包の対称閉包 $R^{+}\cup(R^{+})^{-1}$ は推移的とは限らない。たとえば $A=\{1,2,3\}$ 上の $R=\{(1,2),(3,2)\}$ はすでに推移的で $R^{+}=R$ だが、その対称閉包は $(1,2)$ と $(2,3)$ を含み $(1,3)$ を含まない。反射閉包・対称閉包・推移閉包をこの順にとると、$R$ の生成する同値関係が得られる。これらの証明は 推移閉包(二項関係) の命題「閉包をとる順序」にある。

性質ごとの関係の個数

$A$ を $n$ 元集合とする。$A$ 上の二項関係は $2^{n^2}$ 個あり、そのうち

  • 反射的なものは $2^{n(n-1)}$ 個、
  • 対称的なものは $2^{n(n+1)/2}$ 個、
  • 反対称的なものは $2^{n}\,3^{n(n-1)/2}$ 個
    である。

二項関係は $A\times A$ の部分集合であり、$A\times A$ は $n^2$ 個の組からなるので、各組を入れるかどうかの選び方で $2^{n^2}$ 個ある。$A\times A$ を、対角の組 $(a,a)$($n$ 個)と、相異なる2元の集合 $\{a,b\}$ ごとの組の対 $\{(a,b),(b,a)\}$($\binom{n}{2}=n(n-1)/2$ 個)に分ける。どの性質も、この分け方の各部分ごとに独立な条件として書ける。

  • 反射的:対角の $n$ 組はすべて入れる(1通り)。残りの $n^2-n$ 組は自由なので $2^{n(n-1)}$ 通り。
  • 対称的:対角の各組は自由($2^n$ 通り)。各対 $\{(a,b),(b,a)\}$ は「両方入れる」か「両方入れない」の2通り。よって $2^n\cdot2^{n(n-1)/2}=2^{n(n+1)/2}$ 通り。
  • 反対称的:対角の各組は自由($2^n$ 通り)。各対は「どちらも入れない」「$(a,b)$ だけ」「$(b,a)$ だけ」の3通り(両方入れると $a\ne b$ で反対称律が破れる)。よって $2^n\cdot3^{n(n-1)/2}$ 通り。
    各部分の選び方は互いに独立で、選び方の組と関係は1対1に対応するので、個数は積になる。$\square$

例えば $n=3$ では、関係は $512$ 個、反射的なもの $64$ 個、対称的なもの $64$ 個、反対称的なもの $216$ 個である($n\le3$ ではすべての関係を数え上げても同じ値になる)。対称かつ反対称な関係は、対角の部分集合($2^n$ 個)だけである。

写像のグラフの特徴づけ

$R\subset A\times B$ が写像のグラフであるための必要十分条件は
$$ \Delta_A\subset R^{-1}\circ R\qquad\text{かつ}\qquad R\circ R^{-1}\subset\Delta_B $$
である。前者は「各 $a$ に少なくとも1つの $b$ が対応する」(全域性)、後者は「各 $a$ に対応する $b$ は高々1つ」(一意性)を表す。

$(a,a)\in R^{-1}\circ R$ とは、ある $b$ で $aRb$ かつ $bR^{-1}a$、すなわちある $b$ で $aRb$ となることである。よって前者はすべての $a$ に $aRb$ となる $b$ があることと同じである。$(b,b')\in R\circ R^{-1}$ とは、ある $a$ で $bR^{-1}a$ かつ $aRb'$、すなわち $aRb$ かつ $aRb'$ となる $a$ があることである。よって後者は「$aRb$ かつ $aRb'$ なら $b=b'$」と同じである。2条件を合わせると「各 $a$ に $aRb$ となる $b$ がちょうど1つある」となり、例「写像のグラフ」の条件に一致する。$\square$

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

反例

関係の性質や操作について、誤って信じられやすい主張を反例で退ける。

誤った主張反例($A=\{1,2,3\}$ など)何が破れるか
対称的でなければ反対称的$R=\{(1,2),(2,1),(2,3)\}$対称でも反対称でもない関係がある
反射的でなければ、どの $a$ でも $a\not\mathrel{R}a$$\{1,2\}$ 上の $R=\{(1,1)\}$反射的でも非反射的でもない関係がある
合成は可換$R=\{(1,2)\}$、$S=\{(2,3)\}$$S\circ R\ne R\circ S$
$(S\circ R)^{-1}=S^{-1}\circ R^{-1}$上と同じ $R,S$逆をとると合成の順が入れ替わる
推移閉包の対称閉包は推移的$R=\{(1,2),(3,2)\}$閉包をとる順で結果が変わる
$R^{-1}\circ R=\Delta$定値写像のグラフ写像のグラフでも逆関係は逆写像でない
反例:対称でも反対称でもない関係

$A=\{1,2,3\}$ 上の $R=\{(1,2),(2,1),(2,3)\}$ は、$(2,3)\in R$ かつ $(3,2)\notin R$ なので対称的でない。また $(1,2),(2,1)\in R$ かつ $1\ne2$ なので反対称的でない。「対称でない」は「ある組で逆向きが欠けている」ことであり、「反対称」は「相異なる2元のどの組でも両向きがそろわない」ことなので、互いの否定ではない。命題「性質の包含による言い換え」で見ると、対称は $R^{-1}\subset R$、反対称は $R\cap R^{-1}\subset\Delta_A$ で、両者は別の条件である。
同様に、「非反射的」(すべての $a$ で $a\not\mathrel{R}a$、すなわち $R\cap\Delta_A=\emptyset$)は「反射的でない」(ある $a$ で $a\not\mathrel{R}a$)よりずっと強い。$\{1,2\}$ 上の $R=\{(1,1)\}$ は反射的でも非反射的でもない。

反例:合成の非可換性と逆の順序

$A=\{1,2,3\}$ 上で $R=\{(1,2)\}$、$S=\{(2,3)\}$ とする。$S\circ R$ は「まず $R$、次に $S$」なので $\{(1,3)\}$ であるが、$R\circ S$ は「まず $S$ で $2\mapsto3$、次に $R$ で $3$ から出る組」を探すことになり、$3$ から出る $R$ の組はないので空である。よって $S\circ R\ne R\circ S$。
逆については $(S\circ R)^{-1}=\{(3,1)\}$ であり、命題「逆関係と合成」の 3 のとおり $R^{-1}\circ S^{-1}=\{(3,1)\}$ に等しい。一方 $S^{-1}\circ R^{-1}$ は、$R^{-1}=\{(2,1)\}$ で $2\mapsto1$ の後に $S^{-1}=\{(3,2)\}$ で $1$ から出る組を探すので空である。順序を入れ替えずに逆をとる誤りはここで破れる。

反例:逆関係は逆写像とは限らない

$A=\{1,2\}$、$B=\{0\}$ とし、定値写像 $f\colon A\to B$ のグラフ $G_f=\{(1,0),(2,0)\}$ をとる。逆関係 $G_f^{-1}=\{(0,1),(0,2)\}$ は、$0$ に $1$ と $2$ の2つを対応させるので写像のグラフでない(命題「写像のグラフの特徴づけ」の一意性の条件が破れる)。また $G_f^{-1}\circ G_f=A\times A\ne\Delta_A$ である。関係の世界では逆関係はいつでも作れるが、それが写像になるのは $f$ が全単射のときだけである。

関連項目

参考文献

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