## 2. 準備：直積集合と二項関係
集合と論理の記法は [数学の国語 - 集合と論理](/mathematics/foundations/sets-and-logic) で扱ったものを使います。復習しておくと、集合 $X, Y$ に対して直積集合は
$$
X \times Y = \{\, (x, y) \mid x \in X,\ y \in Y \,\}
$$
であり、順序対の等号は $(x, y) = (x', y') \iff x = x' \text{ かつ } y = y'$ で定まります。
$X, Y$ を集合とする。直積集合の部分集合 $R \subseteq X \times Y$ を、$X$ から $Y$ への**二項関係**という。とくに $Y = X$ のとき、$R \subseteq X \times X$ を $X$ 上の二項関係という。
$(x, y) \in R$ であることを $x \mathrel{R} y$ とも書き、「$x$ は $y$ と $R$ の関係にある」と読む。
「関係」を部分集合として定義するのは、一見まわりくどく見えます。しかしこの定義には 2 つの利点があります。
第一に、「$x$ は $y$ より大きい」のような日本語の述語を、集合論の中の**対象**として扱えます。関係そのものを動かしたり、関係全体の集合を考えたりできるのはこのおかげです。
第二に、関係が等しいとはどういうことかが自動的に決まります。2 つの関係が等しいとは、部分集合として等しいこと、すなわち $\forall x\, \forall y\, (x \mathrel{R} y \iff x \mathrel{S} y)$ です（
反射律は「どんな対象も自分自身とは同じ」、対称律は「同じという関係に向きはない」、推移律は「同じの連鎖はつながる」という要求です。この 3 つは、私たちが「同じ」という語に無意識に期待している性質を、過不足なく書き下したものだと考えてください。
## 3. 同値関係
集合 $X$ 上の二項関係 $\sim$ が反射律・対称律・推移律のすべてを満たすとき、$\sim$ を $X$ 上の**同値関係**という。すなわち、次の 3 つがすべて成り立つときをいう。
$$
\begin{aligned}
&\text{(E1)} && \forall a \in X, && a \sim a \\
&\text{(E2)} && \forall a, b \in X, && a \sim b \implies b \sim a \\
&\text{(E3)} && \forall a, b, c \in X, && (a \sim b \ \text{かつ}\ b \sim c) \implies a \sim c
\end{aligned}
$$
3 条件はどれも独立で、2 つだけでは「同じ」として使い物になりません。次の表で確認してください。
| $X$ と関係 | 反射律 | 対称律 | 推移律 | 同値関係 |
|---|:--:|:--:|:--:|:--:|
| $\mathbb{R}$ 上の $x = y$ | ○ | ○ | ○ | ○ |
| $\mathbb{R}$ 上の $x \le y$ | ○ | × | ○ | × |
| $\mathbb{N}$ 上の整除 $m \mathrel{\mid} n$ | ○ | × | ○ | × |
| 平面の直線の直交 $\ell \perp m$ | × | ○ | × | × |
| $\mathbb{R}$ 上の $\lvert x - y \rvert < 1$ | ○ | ○ | × | × |
| 人の集合の「誕生日が同じ」 | ○ | ○ | ○ | ○ |
$X = \mathbb{R}$ で $x \sim y :\iff \lvert x - y \rvert < 1$ と定めます。$\lvert x - x \rvert = 0 < 1$ なので反射律が成り立ち、$\lvert x - y \rvert = \lvert y - x \rvert$ なので対称律も成り立ちます。
しかし推移律は破れます。$x = 0,\ y = 0.6,\ z = 1.2$ とすると $\lvert 0 - 0.6 \rvert = 0.6 < 1$、$\lvert 0.6 - 1.2 \rvert = 0.6 < 1$ ですが、$\lvert 0 - 1.2 \rvert = 1.2 \ge 1$ です。
「だいたい同じ」を同値関係にできないのは、この例が示すとおりです。誤差の小ささは積み重なると無視できなくなります。
「$a \sim b$ ならば対称律で $b \sim a$、推移律で $a \sim a$。だから反射律は要らない」という議論を見かけることがあります。これは誤りです。この議論は「各 $a$ に対して $a \sim b$ となる $b$ が存在する」ことを黙って使っています。
反例を挙げます。$X = \{1, 2\}$、$R = \{(1, 1)\}$ とします。対称律は、前提 $x \mathrel{R} y$ を満たすのが $(1,1)$ だけで、$(1,1)$ の左右を入れ替えても $(1,1) \in R$ なので成り立ちます。推移律も同様に $(1,1)$ と $(1,1)$ の組しか前提を満たさず、結論 $(1,1) \in R$ が成り立ちます。しかし $2 \mathrel{R} 2$ は成り立たないので、反射律は破れています。
なお背理法（
### 3.1. 整数の合同
$n$ を正の整数とする。整数 $a, b$ に対して
$$
a \equiv b \pmod{n} \quad :\iff \quad n \mid a - b \quad (\text{すなわち } \exists k \in \mathbb{Z},\ a - b = nk)
$$
と定める。このとき $\equiv \pmod n$ は $\mathbb{Z}$ 上の同値関係である。
### 3.2. 平行なベクトル
$V$ を実ベクトル空間とし、$V^{\times} = V \setminus \{\boldsymbol{0}\}$ とおく。$\boldsymbol{u}, \boldsymbol{v} \in V^{\times}$ に対して
$$
\boldsymbol{u} \parallel \boldsymbol{v} \quad :\iff \quad \exists \lambda \in \mathbb{R} \setminus \{0\},\ \boldsymbol{u} = \lambda \boldsymbol{v}
$$
と定めると、$\parallel$ は $V^{\times}$ 上の同値関係である。
（E1）$\boldsymbol{u} = 1 \cdot \boldsymbol{u}$ で $1 \ne 0$ なので $\boldsymbol{u} \parallel \boldsymbol{u}$。
（E2）$\boldsymbol{u} = \lambda \boldsymbol{v}$（$\lambda \ne 0$）とすると、$\lambda$ が $0$ でないので逆数 $\lambda^{-1}$ が取れて $\boldsymbol{v} = \lambda^{-1} \boldsymbol{u}$。$\lambda^{-1} \ne 0$ なので $\boldsymbol{v} \parallel \boldsymbol{u}$。ここで $\lambda \ne 0$ という仮定が本質的に効いています。
（E3）$\boldsymbol{u} = \lambda \boldsymbol{v}$、$\boldsymbol{v} = \mu \boldsymbol{w}$（$\lambda, \mu \ne 0$）とすると $\boldsymbol{u} = \lambda(\mu \boldsymbol{w}) = (\lambda\mu)\boldsymbol{w}$。実数の積で $\lambda \ne 0$ かつ $\mu \ne 0$ ならば $\lambda\mu \ne 0$ なので、$\boldsymbol{u} \parallel \boldsymbol{w}$。
定義域から $\boldsymbol{0}$ を除いたのは飾りではありません。平行を「1 次従属である」と言い換えて $V$ 全体に広げると、推移律が壊れます。
実際 $V = \mathbb{R}^2$ で $\boldsymbol{u} = (1, 0)$、$\boldsymbol{w} = (0, 1)$ とすると、$\boldsymbol{u}$ と $\boldsymbol{0}$ は 1 次従属、$\boldsymbol{0}$ と $\boldsymbol{w}$ も 1 次従属です。しかし $\boldsymbol{u}$ と $\boldsymbol{w}$ は 1 次独立です。零ベクトルが「すべてと平行」なせいで、無関係な 2 本が連結されてしまうのです。
仮定を落とすと何が壊れるかを確かめる癖をつけてください。定義の細部は、たいてい反例を防ぐために置かれています。
## 4. 同値類・商集合・分割
同値関係を手に入れたので、次は「同じものをひとまとめにする」操作を定義します。
$\sim$ を集合 $X$ 上の同値関係とする。$a \in X$ に対し
$$
[a] = [a]_{\sim} = \{\, x \in X \mid x \sim a \,\} \subseteq X
$$
を $a$ の**同値類**といい、$a$ をこの同値類の**代表元**という。同値類全体の集合
$$
X/\!\sim \ = \{\, [a] \mid a \in X \,\}
$$
を $\sim$ による**商集合**という。写像 $\pi : X \to X/\!\sim,\ \pi(a) = [a]$ を**自然な射影**という。
商集合の元は $X$ の元ではなく、$X$ の**部分集合**であることに注意してください。$X/\!\sim$ は $X$ の冪集合 $\mathcal{P}(X)$（
）の部分集合です。
$\sim$ を集合 $X$ 上の同値関係とする。任意の $a, b \in X$ に対して次が成り立つ。
1. $a \in [a]$。とくに $[a] \ne \emptyset$。
2. $a \sim b \iff [a] = [b]$。
3. $[a] \cap [b] \ne \emptyset \implies [a] = [b]$。言い換えると、異なる 2 つの同値類は交わらない。
**(1)** 反射律（E1）より $a \sim a$ なので、 の (2) は、この記事でいちばん使う道具です。「代表元どうしが関係する」ことと「同値類が集合として等しい」ことが同じ意味だ、と述べています。以降、$[a] = [b]$ と $a \sim b$ を自由に行き来します。
$X$ を集合とする。$X$ の部分集合の族 $\mathcal{P} \subseteq \mathcal{P}(X)$ が $X$ の**分割**であるとは、次の 3 条件を満たすことをいう。
1. $\emptyset \notin \mathcal{P}$（各成分は空でない）。
2. $\bigcup_{A \in \mathcal{P}} A = X$（全体を覆う）。
3. $A, B \in \mathcal{P}$ かつ $A \ne B$ ならば $A \cap B = \emptyset$（互いに交わらない）。
$X$ を集合とする。$X$ 上の同値関係全体の集合を $\mathrm{Eq}(X)$、$X$ の分割全体の集合を $\mathrm{Part}(X)$ と書く。写像
$$
\begin{aligned}
\Phi &: \mathrm{Eq}(X) \to \mathrm{Part}(X), &&\quad \Phi(\sim) = X/\!\sim \\[2pt]
\Psi &: \mathrm{Part}(X) \to \mathrm{Eq}(X), &&\quad a \mathrel{\Psi(\mathcal{P})} b :\iff \exists A \in \mathcal{P},\ (a \in A \ \text{かつ}\ b \in A)
\end{aligned}
$$
はいずれも well-defined であり、互いに逆写像である。すなわち $\Psi \circ \Phi = \mathrm{id}$ かつ $\Phi \circ \Psi = \mathrm{id}$ が成り立つ。
**$\Phi$ の行き先が分割であること。** は「同値関係を与えること」と「集合を重なりなく仕切ること」が完全に同じ情報だと述べています。同値関係を見たら仕切りの絵を思い浮かべ、仕切りを見たら同値関係を思い浮かべてください。
$n$ を正の整数とし、
## 5. well-defined：代表元によらないこと
商集合を作ったら、次はその上で計算をしたくなります。たとえば $\mathbb{Z}/12\mathbb{Z}$ で「3 時の 4 時間後は 7 時」と言いたい。素直に書けば
$$
[a] + [b] := [a + b]
$$
です。しかしこの式には落とし穴があります。左辺は同値類（集合）だけで決まる式ですが、右辺は**代表元 $a, b$ を使って**書かれています。$[3] = [15]$ なので、左辺が同じでも代表元は違い得ます。もし $[3 + 4] \ne [15 + 4]$ だったら、$[3] + [4]$ の値が 2 通りになってしまい、そもそも演算として成立しません。
このように、代表元を使って定義された規則が、代表元の取り方によらず一つの値を定めることを **well-defined である**（定義がきちんとしている）といいます。商集合の上で何かを定義したら、well-defined 性の確認は省略できない義務です。
一般論を先に立てておきます。次の定理が、あらゆる well-defined 性の議論の親玉です。
|"π"| Q["X/∼（商集合）"]
X -->|"f"| Y["Y"]
Q -.->|"f̄（存在すれば一意）"| Y`} />
$\sim$ を集合 $X$ 上の同値関係、$\pi : X \to X/\!\sim$ を自然な射影、$Y$ を集合、$f : X \to Y$ を写像とする。このとき次は同値である。
1. $\forall a, b \in X,\ (a \sim b \implies f(a) = f(b))$。
2. $\bar{f} \circ \pi = f$ を満たす写像 $\bar{f} : X/\!\sim \ \to Y$ が存在する。
さらに、条件 2 の $\bar{f}$ は存在すれば一意である。
**2 $\Rightarrow$ 1。** $\bar{f}$ が存在するとし、$a \sim b$ とします。
### 5.1. Z/nZ の加法と乗法
$n$ を正の整数とする。$\mathbb{Z}/n\mathbb{Z}$ 上の二項演算を
$$
[a] + [b] := [a + b], \qquad [a] \cdot [b] := [ab]
$$
で定めると、これらは well-defined である。すなわち、$[a] = [a']$ かつ $[b] = [b']$ ならば $[a+b] = [a'+b']$ かつ $[ab] = [a'b']$ が成り立つ。
$[a] = [a']$、$[b] = [b']$ とします。
## 6. 同値関係で「新しい数」を作る
同値関係の最大の使い道は、既にある数の体系から新しい体系を作ることです。整数から有理数を作る手順を、最後まで書き下します。
$S = \mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$ とし、$(a, b), (c, d) \in S$ に対して
$$
(a, b) \sim (c, d) \quad :\iff \quad ad = bc
$$
と定める。このとき $\sim$ は $S$ 上の同値関係である。
（E1）$ab = ba$（整数の乗法の可換性）より $(a, b) \sim (a, b)$。
（E2）$(a,b) \sim (c,d)$、すなわち $ad = bc$ とすると、可換性より $cb = da$、すなわち $(c,d) \sim (a,b)$。
（E3）$(a,b) \sim (c,d)$ かつ $(c,d) \sim (e,f)$ とします。仮定は $ad = bc$ と $cf = de$ です。目標は $af = be$ です。第 1 式の両辺に $f$ を掛けると
$$
adf = bcf = b(cf) = b(de) = bde .
$$
（2 番目の等号で結合法則、3 番目で第 2 式 $cf = de$ を使いました。）よって $adf - bde = 0$、すなわち $d(af - be) = 0$ です。
ここで $S$ の定義から $d \ne 0$ であり、整数環に零因子がない（$xy = 0$ かつ $x \ne 0$ ならば $y = 0$）ことから $af - be = 0$、すなわち $af = be$。ゆえに $(a,b) \sim (e,f)$。
推移律の証明で $d \ne 0$ を使ったことに注目してください。もし第 2 成分に $0$ を許すと推移律は壊れます。実際 $(1, 0) \sim (0, 0)$（$1 \cdot 0 = 0 \cdot 0$）かつ $(0, 0) \sim (0, 1)$（$0 \cdot 1 = 0 \cdot 0$）ですが、$(1, 0) \sim (0, 1)$ は $1 \cdot 1 = 0 \cdot 0$、つまり $1 = 0$ を要求するので成り立ちません。
「分母は $0$ にしてはいけない」という規則が、ここでは推移律を守るための条件として現れています。ゼロ除算を禁止する理由の一つがこれです。
そこで $\mathbb{Q} := S/\!\sim$ と定義し、$[(a, b)]$ を $\dfrac{a}{b}$ と書きます。$1 \cdot 4 = 2 \cdot 2$ なので $(1,2) \sim (2,4)$、したがって
の (2) より $[(1,2)] = [(2,4)]$、すなわち
$$
\frac{1}{2} = \frac{2}{4}
$$
です。小学校で習った等式は、**同値類が集合として等しい**という主張だったのです。$\frac12$ と $\frac24$ は「同じものの別の書き方」ではなく、「同じ集合を指す 2 つの代表元」です。加法を $[(a,b)] + [(c,d)] := [(ad + bc, bd)]$ で定めるとき、それが well-defined であることの確認が必要になります（
）。
同じ手口は繰り返し使われます。実数はコーシー列全体を「差が $0$ に収束する」という同値関係で割って作られ、$0.999\ldots = 1$ という等式（
## 7. 演習
次の各関係について、反射律・対称律・推移律のそれぞれが成り立つかを判定し、成り立つ場合は証明、成り立たない場合は反例を挙げてください。
1. $X = \mathbb{Z}$、$a \sim b :\iff ab > 0$。
2. $X = \mathbb{R}$、$x \sim y :\iff x - y \in \mathbb{Q}$。
3. $X = \mathbb{R}^2$、$P \sim Q :\iff$ 原点 $O$ からの距離が等しい。
**1.** 反射律は成り立ちません。$a = 0$ のとき $0 \cdot 0 = 0 > 0$ は偽です。対称律は成り立ちます（$ab = ba$ なので $ab > 0 \iff ba > 0$）。推移律も成り立ちます。$ab > 0$ かつ $bc > 0$ とすると、まず $ab > 0$ より $b \ne 0$、したがって $b^2 > 0$ です。$(ab)(bc) = ac \cdot b^2 > 0$ で $b^2 > 0$ なので $ac > 0$。したがって対称律と推移律だけが成り立ち、同値関係ではありません。
## 参考文献
- 松坂和夫『集合・位相入門』岩波書店、1968 — 第 1 章（集合と写像）。同値関係と類別、商集合の扱いが丁寧です。
- 斎藤毅『集合と位相』東京大学出版会、2009 — 第 1 章。同値関係と商集合、well-defined 性の確認が現代的な書き方で整理されています。
- P. R. Halmos, *Naive Set Theory*, Van Nostrand, 1960 — 関係（Relations）を扱う節。関係を直積の部分集合として定義する立場の古典です。
- 高木貞治『初等整数論講義』第 2 版、共立出版、1971 — 第 1 章。合同式と剰余類の理論を基礎から扱っています。
- 雪江明彦『代数学 1 群論入門』日本評論社、2010 — 第 1 章。同値関係と商集合が、その後の商群・準同型定理へどうつながるかが見えます。
## Appendix: 関係から同値関係を作る
同値関係でない関係 $R$ が与えられたとき、$R$ を含む最小の同値関係を作れます。図形を「この辺とこの辺を貼り合わせる」と指定して新しい図形を作るときなど、応用は広い操作です。
まず、$X$ 上の同値関係の族 $\{\sim_i\}_{i \in I}$（$I \ne \emptyset$）に対し、その共通部分 $\bigcap_{i \in I} \sim_i$（$X \times X$ の部分集合としての共通部分）も同値関係です。実際、(E1) 各 $i$ で $(a,a) \in \sim_i$ なので共通部分にも属します。(E2) $(a,b)$ が共通部分に属せば各 $i$ で $(b,a) \in \sim_i$ なので共通部分に属します。(E3) も各 $i$ ごとに推移律を使えば同様です。
さて $R \subseteq X \times X$ を任意の関係とします。$R$ を含む同値関係は少なくとも 1 つ存在します（$X \times X$ 全体がそうです）。そこで $R$ を含むすべての同値関係の共通部分を取れば、それは同値関係であり、$R$ を含む最小のものです。これを $R$ が**生成する同値関係**と呼びます。
具体的な記述も与えられます。$a \approx b$ を「$a = b$ であるか、または有限列 $a = x_0, x_1, \ldots, x_m = b$（$m \ge 1$）が存在して各 $i$ について $x_i \mathrel{R} x_{i+1}$ または $x_{i+1} \mathrel{R} x_i$ が成り立つ」と定めると、$\approx$ は同値関係になります。反射律は $a = b$ の場合から、対称律は列を逆順に並べ替えることから、推移律は 2 本の列をつなぐことから従います。そして $\approx$ は $R$ を含み（長さ $1$ の列を取る）、$R$ を含む任意の同値関係は列の各段を推移律でつないで $\approx$ を含むので、$\approx$ が最小です。
つまり「$R$ で結ばれた点をたどって行き来できる」という関係が、生成される同値関係の正体です。