同値関係

同義語:equivalence relation

概要

同値関係(equivalence relation)とは、集合上の二項関係で、反射律・対称律・推移律の三条件を満たすものであり、「この違いは無視する」という同一視を数学的に表す。同値関係を与えることは集合を同値類に分割することと同じ情報であり、どの同値関係も写像の行き先が等しいという関係(同値核)として得られる。同値関係の共通部分は同値関係で、任意の関係はそれを含む最小の同値関係を生成し、$n$ 元集合上の同値関係の個数は Bell 数の漸化式で数えられる。三条件は互いに独立であり、合同式・有理数の構成・商群・商位相・$L^p$ 空間など、商集合を作るあらゆる場面の基礎となる。

$$\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}} $$

前提知識: 集合, 二項関係, 直積集合

同値関係は、集合の元どうしを「同じものとみなす」ための規則を、反射・対称・推移という三つの性質で定めたものである。たとえば整数を 7 で割った余りだけに注目して $3$ と $10$ を同一視する、有理数 $\frac12$ と $\frac24$ を同じ数とみなす、といった場面で使われる。同値関係を与えると、集合は互いに交わらない同値類に分かれる。

定義

同値関係

集合 $A$ 上の二項関係 $\sim$ が同値関係 (equivalence relation) であるとは、次の3条件が成り立つことをいう。

  1. 反射律: すべての $a \in A$ で $a \sim a$
  2. 対称律: $a \sim b$ ならば $b \sim a$
  3. 推移律: $a \sim b$ かつ $b \sim c$ ならば $a \sim c$
    3条件の名前と定義はHam 第 11 章(定義 11.2、p. 205、§11.3、p. 210)による。
同値類と商集合

$\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つの公理は、「無視の仕方」が破綻しないための最小条件になっている: 自分自身と区別しない(反射)、無視は双方向(対称)、無視のつながりを辿っても矛盾しない(推移)。
そして核心は次の一点にある: 同値関係を与えることと、集合を互いに素な部分に分割することは、完全に同じ情報である(下の性質)。「関係」という動的な見方と「分割」という静的な見方を自由に行き来できることが、この概念の威力の源である。
初学者が誤解しやすい点を挙げる。

  • 推移律は「見た目が近い」関係では簡単に破れる。「差が1以下」という $\mathbb{R}$ 上の関係は反射・対称だが推移的でない($0 \sim 1$, $1 \sim 2$ だが $0 \not\sim 2$)。「似ている」を同値関係にできないことは、分類がしばしば難しいことの原因そのものである。
  • 同値類は元ではなく集合である。$\mathbb{Z}/7\mathbb{Z}$ の元 $[3]$ は「3」ではなく $\{\ldots, -4, 3, 10, \ldots\}$ という無限集合であり、それを1つの対象として扱う、という頭の切り替えが商構成のすべてである。
  • 代表元の取り方によらないこと(well-defined性)の確認が常に必要。商集合上で演算や写像を定義するときは、$[a]=[a']$ なら結果が同じになることを検証しなければならない(well-definedness)。この検証を怠るのが商構成の最も典型的な誤りである。

例

整数の合同

$n \ge 1$ を固定し、$\mathbb{Z}$ 上で $a \sim b \iff n \mid (a - b)$ と定めると同値関係になる(合同式)。商集合 $\mathbb{Z}/n\mathbb{Z}$ は $n$ 個の同値類からなり、代表元によらずに加法・乗法が定まって剰余群・剰余環になる。同値関係→商→代数構造という流れの原型である。

有理数の構成

整数の組 $(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$ の部分集合 $A, B$ の間に全単射があるとき $A \sim B$(対等)と定めると、これは $X$ の冪集合上の同値関係であり(すべての集合の集まりは集合でないので、全体の上では「同値関係の3条件を満たす関係」として扱う)、その「同値類」の代表として濃度の概念が生まれる。

道で結べること

位相空間の点 $x, y$ に対し「$x$ から $y$ への連続な道が存在する」は同値関係であり、その同値類が弧状連結成分である(弧状連結空間)。推移律の証明には道の連結(貼り合わせ)を使う。幾何における「つながり方の分類」も同値関係の言葉で書かれる。

性質

3条件を集合の言葉で書く

二項関係は直積の部分集合 $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)にある。

  1. 類の族が分割であること。反射律から $a\in[a]$ なので、各類は空でなく、類の和集合は $A$ を覆う。$[a]\cap[b]\ne\emptyset$ とし、$c\in[a]\cap[b]$ をとると $c\sim a$、$c\sim b$ である。対称律から $a\sim c$、推移律から $a\sim b$。このとき $x\in[a]$ なら $x\sim a$ と $a\sim b$ から $x\sim b$、すなわち $[a]\subset[b]$ であり、対称律から $b\sim a$ なので同様に $[b]\subset[a]$。よって交わる類は一致する。
  2. 分割から同値関係を作ること。分割 $\mathcal P$ に対し、$a\approx b$ を「$a,b$ が同じブロックに属する」と定める。各元はちょうど1つのブロックに属するので、$a$ の属するブロックを $P(a)$ と書けば $a\approx b\iff P(a)=P(b)$ であり、これは写像 $a\mapsto P(a)$ の同値核なので同値関係である(下の命題「写像から定まる同値関係」の前半と同じ論法)。
  3. 2つの対応が互いに逆であること。同値関係 $\sim$ から類の分割を作り、そこから (2) で関係を作ると、$a\approx b\iff[a]=[b]\iff a\sim b$(最後の同値は (1) の論法そのもの)なので元の $\sim$ に戻る。分割 $\mathcal P$ から $\approx$ を作ると、$\approx$ による $a$ の類は $\{x\mid P(x)=P(a)\}=P(a)$ なので、類の族は $\mathcal P$ に戻る。$\square$

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$

3元集合上の同値関係

$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条件がいかに強い制約かが分かる。

反例: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$ ならば $aRa$ である。
  2. $R\subset D\times D$ であり、$R$ は $D$ 上の同値関係である。
  3. $R$ が $A$ 上の同値関係であることと $D=A$ は同値である。

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$ を介して繋がってしまい、すべてが一つの類に潰れる(命題「同値関係の生成」の後の例:生成される同値関係は全関係になる)。「似ている」による分類が本質的に難しい理由がここにある。

分野ごとの使われ方

同値関係は全分野に現れるが、何を同一視するかが分野の個性そのものである。

  • 代数学: 部分構造による合同(正規部分群・イデアル)が同値関係を定め、剰余群・剰余環が生まれる。「準同型定理」とは、同値核(上の命題「写像から定まる同値関係」)と商構成の対応を構造つきで述べたものであり、代数の商構成はすべてこの一つの型に載っている。
  • 幾何学: 点の同一視による商位相(貼り合わせ・軌道空間)と、写像や空間そのものを同一視するホモトピーの2階建てで使われる。「トーラスとは正方形の辺の同一視」のように、対象の構成法としての同値関係が主役。
  • 解析学: 「ほとんど至る所等しい」(測度)が基本の同値関係で、$L^p$ 空間の元は関数ではなく関数の同値類である。これを意識しないと「$L^2$ の元の1点での値」のような無意味な問いに陥る。
  • 数論: 合同式がそのまま主役。さらにイデアル類群(イデアル類群)のように「どれだけ単項イデアルから離れているか」を測る同値類が深い不変量になる。
  • 数理論理学・基礎論: 商構成そのものが道具になる(Lindenbaum代数、超積のためのフィルターによる同一視、Cantorの対角線論法と並ぶ構成技法)。
  • 圏論の視点: 同値関係で割る操作はコイコライザの特別な場合であり、「同型な対象を区別しない」という圏論の作法(骨格・圏同値)は同値関係の思想の圏レベルへの持ち上げである。
    進む分野を問わず、「商を取ったらwell-definedを確認する」という一手だけは共通の必須動作である(well-definedness)。

関連項目

参考文献

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