同値関係(equivalence relation)とは、集合上の二項関係で、反射律・対称律・推移律の三条件を満たすものであり、「この違いは無視する」という同一視を数学的に表す。同値関係を与えることは集合を同値類に分割することと同じ情報であり、どの同値関係も写像の行き先が等しいという関係(同値核)として得られる。同値関係の共通部分は同値関係で、任意の関係はそれを含む最小の同値関係を生成し、$n$ 元集合上の同値関係の個数は Bell 数の漸化式で数えられる。三条件は互いに独立であり、合同式・有理数の構成・商群・商位相・$L^p$ 空間など、商集合を作るあらゆる場面の基礎となる。
同値関係は、集合の元どうしを「同じものとみなす」ための規則を、反射・対称・推移という三つの性質で定めたものである。たとえば整数を 7 で割った余りだけに注目して $3$ と $10$ を同一視する、有理数 $\frac12$ と $\frac24$ を同じ数とみなす、といった場面で使われる。同値関係を与えると、集合は互いに交わらない同値類に分かれる。
$\sim$ を $A$ 上の同値関係とする。$a \in A$ に対し
$$
[a] = \{x \in A \mid x \sim a\}
$$
を $a$ の同値類 (equivalence class)、$a$ を $[a]$ の代表元という。同値類全体の集合
$$
A/{\sim} = \{[a] \mid a \in A\}
$$
を $A$ の $\sim$ による商集合という(商集合)。
同値関係とは「この違いは無視する」という宣言の数学的な形である。整数を7で割った余りだけに注目するとき、$3$ と $10$ の違いは無視すると決める——これが合同 $3 \equiv 10 \pmod 7$ である。3つの公理は、「無視の仕方」が破綻しないための最小条件になっている: 自分自身と区別しない(反射)、無視は双方向(対称)、無視のつながりを辿っても矛盾しない(推移)。
そして核心は次の一点にある: 同値関係を与えることと、集合を互いに素な部分に分割することは、完全に同じ情報である(下の性質)。「関係」という動的な見方と「分割」という静的な見方を自由に行き来できることが、この概念の威力の源である。
初学者が誤解しやすい点を挙げる。
整数の組 $(a,b)$($b \neq 0$)の集合上で $(a,b) \sim (c,d) \iff ad = bc$ と定めると同値関係になり、商集合が有理数 $\mathbb{Q}$ の構成を与える。$\frac{1}{2} = \frac{2}{4}$ とは「$(1,2)$ と $(2,4)$ が同じ同値類に属する」ことの略記である。数の体系そのものが商集合として作られる例。
位相空間の点 $x, y$ に対し「$x$ から $y$ への連続な道が存在する」は同値関係であり、その同値類が弧状連結成分である(弧状連結空間)。推移律の証明には道の連結(貼り合わせ)を使う。幾何における「つながり方の分類」も同値関係の言葉で書かれる。
二項関係は直積の部分集合 $R\subset A\times A$ であった($a\sim b\iff(a,b)\in R$)。対角集合 $\Delta_A=\{(a,a)\mid a\in A\}$、逆関係 $R^{-1}=\{(b,a)\mid(a,b)\in R\}$、合成 $R\circ R=\{(a,c)\mid\text{ある }b\text{ で }(a,b)\in R,\ (b,c)\in R\}$ を使うと、3条件は
$$
\Delta_A\subset R,\qquad R^{-1}\subset R,\qquad R\circ R\subset R
$$
と書ける。対称律は $R^{-1}=R$ と同じである($R^{-1}\subset R$ の両辺の逆をとると $R\subset R^{-1}$)。この形は、同値関係の共通部分や生成を扱うときに便利である。
推移律の包含 $R\circ R\subset R$ は、同値関係では等号になる。
$R$ が $A$ 上の同値関係ならば $R\circ R=R$ である。
$R\circ R\subset R$ は推移律の言い換えである。実際 $(a,c)\in R\circ R$ なら、ある $b$ で $(a,b)\in R$ かつ $(b,c)\in R$ であり、推移律から $(a,c)\in R$ となる。逆に $(a,c)\in R$ とする。反射律から $(c,c)\in R$ なので、$b=c$ とおけば $(a,b)\in R$ かつ $(b,c)\in R$ が成り立ち、$(a,c)\in R\circ R$ である。よって $R\subset R\circ R$ であり、両方の包含から $R\circ R=R$ を得る。$\square$
逆向きの主張「$R\circ R=R$ なら同値関係」は成り立たない。上の証明は対称律を使っておらず、反射律と推移律だけから $R\circ R=R$ が出る。したがって、$\mathbb{R}$ 上の $\le$ は反射律と推移律を満たすので、同じ証明により ${\le}\circ{\le}={\le}$ となるが、対称律を満たさない(節「反例:3条件は互いに独立である」)。
集合 $A$ 上の同値関係 $\sim$ に対し、その同値類の全体 $A/{\sim}$ は $A$ の分割(互いに素な空でない部分集合の族で、和が $A$ になるもの)である。逆に、$A$ の任意の分割 $\mathcal{P}$ に対し「同じブロックに属する」という関係は同値関係であり、この2つの対応は互いに逆である。すなわち、$A$ 上の同値関係と $A$ の分割は一対一に対応する。前半(類の族が分割になること)は Ham 定理 11.1・11.2(pp. 215–217)にある。
3条件のどれもが (1) のどこかで使われていることに注意する。どれか1つを外すと分割にならない(節「反例:3条件は互いに独立である」)。同じ定理は商集合でも命題「同値関係と分割」として扱っている。
任意の写像 $f \colon A \to B$ に対し、$a \sim a' \iff f(a) = f(a')$ は $A$ 上の同値関係である($f$ の同値核)。逆に、任意の同値関係は標準射影 $A \to A/{\sim}$ の同値核として得られる。つまり同値関係とは「何かの写像で行き先が同じになること」に他ならない。
前半:$f(a)=f(a)$ だから反射律、$f(a)=f(a')$ なら $f(a')=f(a)$ だから対称律、$f(a)=f(a')$ かつ $f(a')=f(a'')$ なら $f(a)=f(a'')$ だから推移律が成り立つ。3条件はどれも等号 $=$ の性質をそのまま写したものである。
後半:$\sim$ を同値関係とし、$\pi\colon A\to A/{\sim}$、$\pi(a)=[a]$ を標準射影とする。$\pi(a)=\pi(a')$、すなわち $[a]=[a']$ となるのは、$a\sim a'$ のときであり、かつそのときに限る(商集合の命題「同値類の一致判定」)。念のため確かめると、$[a]=[a']$ なら反射律から $a\in[a]=[a']$ なので $a\sim a'$。逆に $a\sim a'$ とし $x\in[a]$ をとると $x\sim a$ と推移律から $x\sim a'$、すなわち $x\in[a']$ である。対称律から $a'\sim a$ でもあるので同様に $[a']\subset[a]$ となり、$[a]=[a']$ である。よって $\sim$ は $\pi$ の同値核に一致する。$\square$
この命題から、$A$ 上の同値関係は「$A$ から出る全射を、行き先の集合の付け替え(全単射)を除いて考えたもの」と同じ情報をもつ。分割・同値関係・全射という3つの見方が同じものを表している。
$A$ 上の同値関係の族 $(R_\lambda)_{\lambda\in\Lambda}$($\Lambda\ne\emptyset$)に対し、共通部分 $\bigcap_\lambda R_\lambda\subset A\times A$ は同値関係である。$\Lambda=\emptyset$ のときは共通部分を $A\times A$ と約束すれば、これも同値関係である。
$R=\bigcap_\lambda R_\lambda$ とおく。各 $\lambda$ で $\Delta_A\subset R_\lambda$ だから $\Delta_A\subset R$。$(a,b)\in R$ なら各 $\lambda$ で $(a,b)\in R_\lambda$、したがって $(b,a)\in R_\lambda$ なので $(b,a)\in R$。$(a,b),(b,c)\in R$ なら各 $\lambda$ で $(a,c)\in R_\lambda$ なので $(a,c)\in R$。$A\times A$ が同値関係であることは明らかである。$\square$
和集合については同じことが成り立たない。$A=\{1,2,3\}$ 上で、$1$ と $2$ だけを同一視する同値関係 $R_1$ と、$2$ と $3$ だけを同一視する同値関係 $R_2$ をとると、$R_1\cup R_2$ は $(1,2)$ と $(2,3)$ を含むが $(1,3)$ を含まないので推移的でない。この反例は「同値関係の和集合は反射的・対称的である」ことを保ちながら推移律を破る。
$A$ 上の任意の二項関係 $R$ に対し、$R$ を含む最小の同値関係 $\langle R\rangle$ が存在する。具体的には、$a\mathrel{\langle R\rangle}b$ となるのは、$a=b$ であるか、または有限列 $a=x_0,x_1,\dots,x_n=b$($n\ge1$)で、各 $k$ について $x_{k-1}Rx_k$ または $x_kRx_{k-1}$ となるものがあるとき、かつそのときに限る。貼り合わせによる空間の構成(商位相)や群の表示など、「これとこれを同一視せよ」という指定から出発する構成の基礎である。
存在:$R$ を含む同値関係の全体は空でない($A\times A$ を含む)ので、その共通部分をとれば、命題「同値関係の共通部分」により $R$ を含む同値関係であり、作り方から最小である。これを $\langle R\rangle$ とする。
具体形:$a\approx b$ を「$a=b$ であるか、上のような列(「$R$ の鎖」と呼ぶ)で $a$ と $b$ が結べる」と定める。
(1) $\approx$ は同値関係である。反射律は $a=b$ の場合として含まれる。対称律:$a$ から $b$ への鎖を逆順にたどれば $b$ から $a$ への鎖になる(各段の条件「$x_{k-1}Rx_k$ または $x_kRx_{k-1}$」は向きについて対称である)。推移律:$a$ から $b$ への鎖と $b$ から $c$ への鎖をつなげれば $a$ から $c$ への鎖になる(どちらかが $a=b$ や $b=c$ の場合は明らか)。
(2) $R\subset{\approx}$ である。$aRb$ なら長さ $1$ の鎖 $x_0=a$、$x_1=b$ がある。
(3) $R$ を含む任意の同値関係 $E$ について ${\approx}\subset E$ である。$a=b$ なら反射律から $aEb$。鎖 $a=x_0,\dots,x_n=b$ があれば、各段で $x_{k-1}Rx_k$ なら $x_{k-1}Ex_k$、$x_kRx_{k-1}$ なら $x_kEx_{k-1}$ と対称律から $x_{k-1}Ex_k$ である。推移律を $n-1$ 回使って $aEb$ を得る。
(1)〜(3) から $\approx$ は $R$ を含む最小の同値関係であり、$\langle R\rangle$ に一致する。$\square$
例えば $\mathbb{R}$ 上の関係 $|x-y|\le1$ が生成する同値関係は $\mathbb{R}\times\mathbb{R}$ 全体である:$x< y$ なら、$x$ から $y$ まで幅 $1$ 以下の刻みで進む鎖がとれる。「似ている」を推移的に閉じると、すべてが1つの類に潰れてしまうのはこのためである。
$n$ 元集合上の同値関係の個数を $B_n$(Bell数)とし、$B_0=1$ とおく。このとき
$$
B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_k\qquad(n\ge0)
$$
が成り立つ。特に $B_0,B_1,\dots,B_6=1,1,2,5,15,52,203$ である。
定理「同値関係と分割の対応」により、$B_n$ は $n$ 元集合の分割の個数に等しい($B_0=1$ は空集合の唯一の分割、すなわち空の族に対応する)。$A=\{1,\dots,n+1\}$ の分割を、元 $n+1$ を含むブロック $P$ で分類する。$P$ は $n+1$ と、$\{1,\dots,n\}$ から選んだ $j$ 個の元からなる($0\le j\le n$)。その選び方は $\binom{n}{j}$ 通りで、残りの $n-j$ 個の元の分割の仕方は $B_{n-j}$ 通りであり、$P$ と残りの分割を組にすれば $A$ の分割が1つずつ得られる(逆に $A$ の分割から $P$ と残りの分割が一意に復元できる)。よって
$$
B_{n+1}=\sum_{j=0}^{n}\binom{n}{j}B_{n-j}=\sum_{k=0}^{n}\binom{n}{n-k}B_k=\sum_{k=0}^{n}\binom{n}{k}B_k
$$
である($k=n-j$ とおき、$\binom{n}{n-k}=\binom{n}{k}$ を使った)。数値は漸化式から順に $B_2=1+1=2$、$B_3=1+2+2=5$、$B_4=1+3+6+5=15$、$B_5=1+4+12+20+15=52$、$B_6=1+5+20+50+75+52=203$ と計算される。$\square$
$A=\{1,2,3\}$ 上の同値関係は $B_3=5$ 個ある。分割で書くと、$\{\{1\},\{2\},\{3\}\}$(等号)、$\{\{1,2\},\{3\}\}$、$\{\{1,3\},\{2\}\}$、$\{\{2,3\},\{1\}\}$、$\{\{1,2,3\}\}$(全関係 $A\times A$)である。一方、$A\times A$ の部分集合は $2^9=512$ 個あり、そのうち同値関係はこの $5$ 個だけである。3条件がいかに強い制約かが分かる。
反射律・対称律・推移律のどれも、残りの2つからは導けない。1つだけを破る関係を並べ、そのとき定理「同値関係と分割の対応」のどこが崩れるかを示す。
| 外す条件 | 反例(残り2条件は成り立つ) | 成り立たなくなること |
|---|---|---|
| 反射律 | $A=\{a,b\}$ 上の $R=\{(a,a)\}$ | $[b]=\emptyset$ となり、類の族が $A$ を覆わない |
| 対称律 | $\mathbb{R}$ 上の $\le$ | 「類」$\{x\mid x\le a\}$ どうしが交わるのに一致しない |
| 推移律 | $\mathbb{R}$ 上の $\lvert x-y\rvert\le1$ | 「類」どうしが交わるのに一致しない |
$A=\{a,b\}$ 上の $R=\{(a,a)\}$ は対称的($(a,a)$ の逆は自分自身)かつ推移的($(a,a),(a,a)$ から $(a,a)$)であるが、$(b,b)\notin R$ なので反射的でない。空集合でない集合上の空関係 $R=\emptyset$ も同じ型の反例である。
よく見かける誤った「証明」がある:「$a\sim b$ なら対称律で $b\sim a$、推移律で $a\sim a$。よって反射律は不要」。この論法が使えるのは、$a$ と関係する元 $b$ が少なくとも1つあるときだけである。上の $R$ の $b$ にはそのような相手がない。実際に成り立つのは、下の命題「対称律と推移律から分かること」の弱い主張である。
この反例は「対称律と推移律」を満たしながら「反射律」を満たさず、その結果 $b$ の類 $[b]=\{x\mid xRb\}$ が空になって、類の族が $A$ の分割にならない。
$A$ 上の関係 $R$ が対称律と推移律を満たすとし、$D:=\{a\in A\mid\text{ある }b\in A\text{ で }aRb\}$ とおく。このとき次が成り立つ。
1:$a\in D$ とし、$aRb$ となる $b$ をとる。対称律から $bRa$ である。$aRb$ と $bRa$ に推移律を当てると $aRa$ を得る。
2:$aRb$ とする。定義から $a\in D$ である。対称律から $bRa$ なので $b\in D$ でもある。よって $(a,b)\in D\times D$ であり、$R\subset D\times D$ となる。したがって $R$ は $D$ 上の関係とみなせる。1 から $D$ 上で反射律が成り立ち、対称律と推移律は $A$ 上で成り立つので $D$ 上でもそのまま成り立つ。よって $R$ は $D$ 上の同値関係である。
3:$D=A$ なら 2 から $R$ は $A$ 上の同値関係である。逆に $R$ が $A$ 上の反射律を満たすなら、各 $a\in A$ で $aRa$ なので、$b=a$ として $a\in D$ となり、$D=A$ である。$\square$
上の反例 $R=\{(a,a)\}$ では $D=\{a\}\ne A$ であり、$R$ は $D$ 上では同値関係である。このように、ある部分集合の上で同値関係になっている対称かつ推移的な関係を部分同値関係と呼ぶことがある。
$\mathbb{R}$ 上の大小関係 $\le$ は反射的・推移的であるが、$0\le1$ かつ $1\not\le0$ なので対称的でない。定義どおり $[a]=\{x\mid x\le a\}$ とおくと、$[0]=(-\infty,0]$ と $[1]=(-\infty,1]$ は交わる($0$ を共有する)が等しくない。つまり「交わる類は一致する」という分割の性質が破れる。反射的かつ推移的な関係は前順序と呼ばれ、同値関係とは別の重要な概念である(前順序 $\preceq$ から「$a\preceq b$ かつ $b\preceq a$」として同値関係を取り出せる)。
$\mathbb{R}$ 上の関係 $x \sim y \iff |x - y| \le 1$ は反射的・対称的だが推移的でないため、同値関係ではない($0\sim1$、$1\sim2$ だが $0\not\sim2$)。$[0]=[-1,1]$ と $[1]=[0,2]$ は交わるが等しくなく、分割にならない。これを無理に「分類」に使おうとすると、$0$ と $2$ は直接は似ていないのに $1$ を介して繋がってしまい、すべてが一つの類に潰れる(命題「同値関係の生成」の後の例:生成される同値関係は全関係になる)。「似ている」による分類が本質的に難しい理由がここにある。
同値関係は全分野に現れるが、何を同一視するかが分野の個性そのものである。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する