関係と同値関係：「同じ」とは何か（同値類・商集合・well-defined）

0. この記事の要点

• 二項関係とは、直積集合 $X \times Y$ の部分集合のことです。「$x$ と $y$ が関係を持つ」という言明は、順序対 $(x, y)$ がその部分集合に属することとして定義されます。
• 反射律・対称律・推移律の 3 つを満たす関係を同値関係と呼びます。この 3 条件は「同じとみなしてよい」ための最小限の要求です。
• 同値関係は集合を同値類に分割し、逆に分割は同値関係を定めます。両者はちょうど 1 対 1 に対応します（Theorem 4.4）。
• 同値類を元とする集合が商集合 $X/\!\sim$ です。「異なるものを同じとみなす」という操作は、商集合を作ることとして厳密に定式化されます。
• 商集合の上で写像や演算を定義するときは、代表元の取り方によらないこと（well-defined であること）の確認が必須です。その一般形が商集合の普遍性（Theorem 5.1）です。
• 有理数も実数も、適当な集合を同値関係で割って作られます。「$1/2$ と $2/4$ は同じ数」という小学校の約束は、同値類が等しいという主張です。

1. 動機：「同じ」は文脈で決まる

小学校で、$\dfrac{1}{2}$ と $\dfrac{2}{4}$ は同じ数だと習います。しかし記号列としては明らかに違います。分数を「分子と分母の対 $(a, b)$」だと思えば、$(1, 2)$ と $(2, 4)$ は順序対として異なります。それでも同じ数だと言い切ってよいのはなぜでしょうか。

似た状況はいくらでもあります。時計の針は 15 時と 3 時を区別しません。合同な三角形は、置かれている場所が違っても「同じ三角形」として扱われます。地図の縮尺を変えても、相似な図形は「同じ形」です。プログラムを書くときも、内部表現が違う 2 つのオブジェクトを「等しい」とみなす基準を自分で決めます。

これらに共通するのは、本来は異なる対象を、ある観点のもとで同一視しているという構造です。そして観点が変われば「同じ」の意味も変わります。時計は「12 で割った余り」という観点、合同は「動かして重ねられる」という観点です。

数学は「同じ」という語をあいまいなまま使いません。かわりに次の二段構えを取ります。

1. どういう性質を満たす関係なら「同じ」と呼んでよいかを決める（同値関係）。
2. その関係で対象をまとめ上げ、新しい集合を作る（商集合）。

この記事では、この二段構えを最後まで実行します。そして最も間違いやすい箇所、すなわち商集合の上で何かを定義するときに何を確かめなければならないか（well-defined 性）を、証明つきで扱います。$\frac{1}{2} = \frac{2}{4}$ と書いてよい理由は §6 で回収します。

2. 準備：直積集合と二項関係

集合と論理の記法は 数学の国語 - 集合と論理 で扱ったものを使います。復習しておくと、集合 $X, Y$ に対して直積集合は

$$X \times Y = \{\, (x, y) \mid x \in X,\ y \in Y \,\}$$

であり、順序対の等号は $(x, y) = (x', y') \iff x = x' \text{ かつ } y = y'$ で定まります。

Definition 2.1（二項関係）

$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$ の関係にある」と読む。

Remark 2.2

「関係」を部分集合として定義するのは、一見まわりくどく見えます。しかしこの定義には 2 つの利点があります。

第一に、「$x$ は $y$ より大きい」のような日本語の述語を、集合論の中の対象として扱えます。関係そのものを動かしたり、関係全体の集合を考えたりできるのはこのおかげです。

第二に、関係が等しいとはどういうことかが自動的に決まります。2 つの関係が等しいとは、部分集合として等しいこと、すなわち $\forall x\, \forall y\, (x \mathrel{R} y \iff x \mathrel{S} y)$ です（外延性の原理（Axiom 3.2）［The Grammar of Mathematics］）。定義の言い換えに悩む必要がありません。

Example 2.3（身のまわりの二項関係）

いずれも $X$ 上の二項関係、すなわち $X \times X$ の部分集合です。

• $X = \mathbb{R}$、$R_{\le} = \{\, (x, y) \mid x \le y \,\}$。座標平面で描くと、直線 $y = x$ とその上側の閉半平面です。
• $X = \mathbb{N} = \{1, 2, \ldots\}$、整除関係 $R_{\mid} = \{\, (m, n) \mid \exists k \in \mathbb{N},\ n = mk \,\}$。たとえば $(2, 6) \in R_{\mid}$ です（$k = 3$ と取ればよい）。
• 任意の $X$ に対し、対角線集合 $\Delta_X = \{\, (x, x) \mid x \in X \,\}$。これは「等号そのもの」を関係として書いたものです。
• 空集合 $\emptyset$（何も関係しない）と $X \times X$（すべてが関係する）。極端ですが、これらも定義上れっきとした関係です。

Definition 2.4（関係の 3 法則）

$R$ を集合 $X$ 上の二項関係とする。

• $R$ が反射律を満たすとは、$\forall a \in X,\ a \mathrel{R} a$ が成り立つことをいう。
• $R$ が対称律を満たすとは、$\forall a, b \in X,\ (a \mathrel{R} b \implies b \mathrel{R} a)$ が成り立つことをいう。
• $R$ が推移律を満たすとは、$\forall a, b, c \in X,\ (a \mathrel{R} b \text{ かつ } b \mathrel{R} c \implies a \mathrel{R} c)$ が成り立つことをいう。

反射律は「どんな対象も自分自身とは同じ」、対称律は「同じという関係に向きはない」、推移律は「同じの連鎖はつながる」という要求です。この 3 つは、私たちが「同じ」という語に無意識に期待している性質を、過不足なく書き下したものだと考えてください。

3. 同値関係

Definition 3.1（同値関係）

集合 $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$	○	○	×	×
人の集合の「誕生日が同じ」	○	○	○	○

Example 3.2（推移律だけが破れる例）

$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$ です。

「だいたい同じ」を同値関係にできないのは、この例が示すとおりです。誤差の小ささは積み重なると無視できなくなります。

Remark 3.3（反射律は他の 2 つから出ない）

「$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$ は成り立たないので、反射律は破れています。

なお背理法（背理法の正当性（Proposition 6.2）［Techniques of Proof］）や帰納法（数学的帰納法の原理（Theorem 3.2）［Techniques of Proof］）など証明の型については 証明の技術 を参照してください。

3.1. 整数の合同

Proposition 3.4（法 n の合同は同値関係）

$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}$ 上の同値関係である。

Proof（Proposition 3.4）

Definition 3.1 の 3 条件を順に確かめます。

（E1）任意の $a \in \mathbb{Z}$ に対し $a - a = 0 = n \cdot 0$ であり、$0 \in \mathbb{Z}$ なので $n \mid a - a$。よって $a \equiv a$。

（E2）$a \equiv b$ とすると、ある $k \in \mathbb{Z}$ で $a - b = nk$。両辺に $-1$ を掛けて $b - a = n(-k)$。$-k \in \mathbb{Z}$ なので $n \mid b - a$、すなわち $b \equiv a$。

（E3）$a \equiv b$ かつ $b \equiv c$ とすると、ある $k, l \in \mathbb{Z}$ で $a - b = nk$、$b - c = nl$。辺々加えると

$$a - c = (a - b) + (b - c) = nk + nl = n(k + l)$$

であり $k + l \in \mathbb{Z}$ なので $n \mid a - c$、すなわち $a \equiv c$。

以上で 3 条件がすべて成り立ちました。

∎

Example 3.5（9 の倍数判定を最後まで計算する）

「各位の数の和が 9 の倍数なら、もとの数も 9 の倍数」という判定法は、合同の推移律と（後で示す）演算の整合性から出ます。

$10 - 1 = 9$ なので $10 \equiv 1 \pmod 9$ です。Theorem 5.4 の積の部分を繰り返し使うと、任意の $i \ge 0$ で $10^i \equiv 1^i = 1 \pmod 9$ です。したがって $N = \sum_{i=0}^{m} a_i 10^i$（$a_i$ は各位の数）に対し

$$N = \sum_{i=0}^{m} a_i 10^i \equiv \sum_{i=0}^{m} a_i \cdot 1 = \sum_{i=0}^{m} a_i \pmod 9 .$$

実際に $N = 12345$ で確かめます。各位の和は $1 + 2 + 3 + 4 + 5 = 15$、さらに $15$ の各位の和は $1 + 5 = 6$ なので $N \equiv 6 \pmod 9$ のはずです。割り算で検算すると $9 \times 1371 = 12339$、$12345 - 12339 = 6$。確かに余りは $6$ で、$12345$ は 9 の倍数ではありません。

3.2. 平行なベクトル

Proposition 3.6（零ベクトルを除いた平行関係）

$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}$ 上の同値関係である。

Proof（Proposition 3.6）

（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}$。

∎

Remark 3.7

定義域から $\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. 同値類・商集合・分割

同値関係を手に入れたので、次は「同じものをひとまとめにする」操作を定義します。

Definition 4.1（同値類・商集合・自然な射影）

$\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)$（べき集合の定義（Definition 3.5）［The Grammar of Mathematics］）の部分集合です。

Lemma 4.2（同値類の基本性質）

$\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 つの同値類は交わらない。

Proof（Lemma 4.2）

(1) 反射律（E1）より $a \sim a$ なので、Definition 4.1 の定義から $a \in [a]$。ゆえに $[a]$ は空でありません。

(2) （$\Rightarrow$）$a \sim b$ とします。$x \in [a]$ とすると $x \sim a$ で、これと $a \sim b$ に推移律（E3）を使って $x \sim b$、すなわち $x \in [b]$。よって $[a] \subseteq [b]$。逆に $x \in [b]$ とすると $x \sim b$ です。$a \sim b$ に対称律（E2）を使うと $b \sim a$ で、$x \sim b$ と合わせて推移律（E3）より $x \sim a$、すなわち $x \in [a]$。よって $[b] \subseteq [a]$。両方の包含から $[a] = [b]$。

（$\Leftarrow$）$[a] = [b]$ とします。(1) より $a \in [a] = [b]$ なので、$[b]$ の定義から $a \sim b$。

(3) $c \in [a] \cap [b]$ を取ります。$c \in [a]$ より $c \sim a$、対称律（E2）より $a \sim c$。$c \in [b]$ より $c \sim b$。推移律（E3）で $a \sim c$ と $c \sim b$ をつないで $a \sim b$。したがって (2) より $[a] = [b]$。

∎

Lemma 4.2 の (2) は、この記事でいちばん使う道具です。「代表元どうしが関係する」ことと「同値類が集合として等しい」ことが同じ意味だ、と述べています。以降、$[a] = [b]$ と $a \sim b$ を自由に行き来します。

Definition 4.3（集合の分割）

$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$（互いに交わらない）。

同値関係は集合を同値類に分割し、自然な射影 π が各同値類を商集合の 1 点に送る

Theorem 4.4（同値関係と分割の対応）

$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}$ が成り立つ。

Proof（Theorem 4.4）

$\Phi$ の行き先が分割であること。 Definition 4.3 の 3 条件を確かめます。(1) Lemma 4.2 の (1) より各 $[a]$ は $a$ を含むので空でありません。(2) 任意の $a \in X$ は $[a] \in X/\!\sim$ に属するので、和集合は $X$ を覆います（逆の包含は各 $[a] \subseteq X$ から明らかで、これは定義そのものです）。(3) $[a] \ne [b]$ とします。もし $[a] \cap [b] \ne \emptyset$ なら Lemma 4.2 の (3) より $[a] = [b]$ となって矛盾するので、$[a] \cap [b] = \emptyset$。

$\Psi$ の行き先が同値関係であること。 $\mathcal{P}$ を分割とし、$\approx$ を $\Psi(\mathcal{P})$ と書きます。(E1) Definition 4.3 の (2) より、任意の $a \in X$ に対し $a \in A$ なる $A \in \mathcal{P}$ が存在します。この $A$ が $a \approx a$ を保証します。(E2) 定義の条件「$a \in A$ かつ $b \in A$」は $a$ と $b$ について対称なので、そのまま $b \approx a$ が従います。(E3) $a \approx b$、$b \approx c$ とし、$a, b \in A$、$b, c \in B$（$A, B \in \mathcal{P}$）とします。$b \in A \cap B$ なので $A \cap B \ne \emptyset$、Definition 4.3 の (3) の対偶より $A = B$。よって $a, c \in A$ となり $a \approx c$。

$\Psi(\Phi(\sim)) = \sim$。 $\approx$ を左辺とします。$a \approx b$ とは、ある $c \in X$ で $a, b \in [c]$ となること、すなわち $a \sim c$ かつ $b \sim c$ となることです。このとき対称律で $c \sim b$、推移律で $a \sim b$ が出ます。逆に $a \sim b$ なら、$c = b$ と取れば $a \in [b]$（仮定より）かつ $b \in [b]$（Lemma 4.2 の (1)）なので $a \approx b$。よって 2 つの関係は $X \times X$ の部分集合として一致します。

$\Phi(\Psi(\mathcal{P})) = \mathcal{P}$。 $\approx = \Psi(\mathcal{P})$ とします。まず $a \in X$ を任意に取り、$a \in A$ なる $A \in \mathcal{P}$ を取ります（存在は分割の条件 (2)）。このとき $[a]_{\approx} = A$ を示します。$x \in [a]_{\approx}$ とすると、ある $B \in \mathcal{P}$ で $x, a \in B$。$a \in A \cap B$ より $A \cap B \ne \emptyset$ なので条件 (3) から $A = B$、よって $x \in A$。逆に $x \in A$ なら $x, a \in A$ なので $x \approx a$、すなわち $x \in [a]_{\approx}$。

これで $X/\!\approx \ \subseteq \mathcal{P}$ が言えました。逆に $A \in \mathcal{P}$ を取ると、条件 (1) より $A \ne \emptyset$ なので $a \in A$ が取れ、いま示したことから $A = [a]_{\approx} \in X/\!\approx$。よって $\mathcal{P} \subseteq X/\!\approx$ であり、両者は一致します。

∎

この定理（Theorem 4.4） は「同値関係を与えること」と「集合を重なりなく仕切ること」が完全に同じ情報だと述べています。同値関係を見たら仕切りの絵を思い浮かべ、仕切りを見たら同値関係を思い浮かべてください。

Example 4.5（Z/nZ の元はちょうど n 個）

$n$ を正の整数とし、Proposition 3.4 の同値関係による商集合を $\mathbb{Z}/n\mathbb{Z}$ と書きます。このとき

$$\mathbb{Z}/n\mathbb{Z} = \{\, [0], [1], \ldots, [n-1] \,\}$$

であり、しかもこれらはすべて相異なります。したがって元の個数はちょうど $n$ 個です。

覆っていること。 任意の $a \in \mathbb{Z}$ に対し、除法の定理より $a = qn + r$、$0 \le r < n$ なる $q, r \in \mathbb{Z}$ が取れます。すると $a - r = qn$ なので $a \equiv r \pmod n$、Lemma 4.2 の (2) より $[a] = [r]$ で、$r$ は $0, \ldots, n-1$ のいずれかです。

相異なること。 $0 \le r < s \le n-1$ とし、$[r] = [s]$ と仮定します。Lemma 4.2 の (2) より $n \mid s - r$ です。ところが $0 < s - r \le n - 1 < n$ なので、$s - r$ は $n$ の倍数のうち $0$ より大きく $n$ より小さいものになり、そのような整数は存在しません。矛盾です。

たとえば $n = 12$ なら $[15] = [3]$ です。時計が 15 時と 3 時を区別しないのは、この等式そのものです。

Example 4.6（R を Z で割ると円になる）

$X = \mathbb{R}$ に $x \sim y :\iff x - y \in \mathbb{Z}$ という関係を入れます。$0 \in \mathbb{Z}$、$\mathbb{Z}$ が符号反転と加法で閉じていることから、Proposition 3.4 とまったく同じ計算で同値関係だとわかります。

同値類 $[x] = \{\, x + k \mid k \in \mathbb{Z} \,\}$ は、実数直線上に間隔 $1$ で並ぶ点の列です。各同値類は区間 $[0, 1)$ の中にちょうど 1 つ代表元を持ちます（$x$ の小数部分を取ればよい）。商集合 $\mathbb{R}/\mathbb{Z}$ は、区間 $[0, 1]$ の両端をのり付けした円周だと思えます。実際、$f(x) = (\cos 2\pi x, \sin 2\pi x)$ とすると $f(x) = f(y) \iff x - y \in \mathbb{Z}$ なので、Theorem 5.1 と Corollary 5.3 により $\mathbb{R}/\mathbb{Z}$ から単位円周への全単射が得られます。

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 性の確認は省略できない義務です。

Caution

「well-defined か確かめよ」という問いは、「あなたの書いた対応は本当に写像になっているか」という問いです。写像とは各入力にただ一つの出力を与えるものですから、出力が代表元の選び方で変わるなら、それは写像ではありません。

一般論を先に立てておきます。次の定理が、あらゆる well-defined 性の議論の親玉です。

flowchart LR
X["X（もとの集合）"] -->|"π"| Q["X/∼（商集合）"]
X -->|"f"| Y["Y"]
Q -.->|"f̄（存在すれば一意）"| Y

商集合の普遍性：f が同値関係と整合するとき、f は π を経由して一意に分解する

Theorem 5.1（商集合の普遍性）

$\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}$ は存在すれば一意である。

Proof（Theorem 5.1）

2 $\Rightarrow$ 1。 $\bar{f}$ が存在するとし、$a \sim b$ とします。Lemma 4.2 の (2) より $[a] = [b]$ です。よって

$$f(a) = \bar{f}(\pi(a)) = \bar{f}([a]) = \bar{f}([b]) = \bar{f}(\pi(b)) = f(b).$$

1 $\Rightarrow$ 2。 条件 1 を仮定します。$\bar{f}$ を、そのグラフを直接指定することで定義します。

$$G = \{\, (C, y) \in (X/\!\sim) \times Y \mid \exists a \in C,\ f(a) = y \,\}.$$

これが写像のグラフであること、すなわち各 $C \in X/\!\sim$ に対して $(C, y) \in G$ なる $y$ がただ一つ存在することを示します。

（存在）$C \in X/\!\sim$ とすると、$C = [a]$ なる $a \in X$ があり、Lemma 4.2 の (1) より $a \in C$。よって $y = f(a)$ が条件を満たします。

（一意）$(C, y), (C, y') \in G$ とすると、ある $a, a' \in C$ で $y = f(a)$、$y' = f(a')$。$C$ は同値類なので $C = [c]$ と書け、$a, a' \in [c]$ から $a \sim c$ かつ $a' \sim c$。対称律で $c \sim a'$、推移律で $a \sim a'$。仮定 1 より $f(a) = f(a')$、すなわち $y = y'$。

そこでこの $G$ を持つ写像を $\bar{f}$ と書けば、任意の $a \in X$ に対し $a \in [a]$ より $\bar{f}([a]) = f(a)$、すなわち $\bar{f} \circ \pi = f$ です。

一意性。 $g : X/\!\sim \ \to Y$ が $g \circ \pi = f$ を満たすとします。任意の $C \in X/\!\sim$ は $C = \pi(a)$ の形（$\pi$ は定義から全射）なので、$g(C) = g(\pi(a)) = f(a) = \bar{f}(\pi(a)) = \bar{f}(C)$。よって $g = \bar{f}$。

∎

Remark 5.2

証明で「各同値類から代表元を 1 つずつ選ぶ」と言わずに、グラフ $G$ を直接書き下したのには理由があります。無限個の同値類から一斉に代表元を選ぶ操作は、素朴にやると選択公理を要求します。上の書き方なら選択公理は不要で、内包公理だけで $\bar{f}$ が作れます。定義が well-defined であることの証明は、実は「選ばずに済ませる」ことの証明でもあります。

Corollary 5.3（任意の写像は全射と単射に分解する）

$f : X \to Y$ を写像とし、$X$ 上の関係を $a \sim_f b :\iff f(a) = f(b)$ で定める。このとき $\sim_f$ は $X$ 上の同値関係であり、$\bar{f} : X/\!\sim_f \ \to Y$ は単射で、$f = \bar{f} \circ \pi$ は全射 $\pi$ と単射 $\bar{f}$ の合成である。とくに $X/\!\sim_f$ から像 $f(X)$ への全単射が存在する。

Proof（Corollary 5.3）

$\sim_f$ が同値関係であることは、等号の反射性 $f(a) = f(a)$、対称性、推移性からただちに従います（(E1)(E2)(E3) がそれぞれ等号の 3 性質に対応します）。

$a \sim_f b$ ならば定義から $f(a) = f(b)$ なので、Theorem 5.1 の条件 1 が成り立ち、$\bar{f} \circ \pi = f$ なる $\bar{f}$ が一意に存在します。

単射性を示します。$\bar{f}([a]) = \bar{f}([b])$ とすると、$\bar{f}([a]) = f(a)$、$\bar{f}([b]) = f(b)$ なので $f(a) = f(b)$、すなわち $a \sim_f b$。Lemma 4.2 の (2) より $[a] = [b]$。

$\pi$ は定義から全射です。最後に、$\bar{f}$ の像は $\{\bar{f}([a]) \mid a \in X\} = \{f(a) \mid a \in X\} = f(X)$ なので、終域を $f(X)$ に制限すれば全射かつ単射、すなわち全単射になります。

∎

5.1. Z/nZ の加法と乗法

Theorem 5.4（剰余類の加法と乗法は well-defined）

$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']$ が成り立つ。

Proof（Theorem 5.4）

$[a] = [a']$、$[b] = [b']$ とします。Lemma 4.2 の (2) と Proposition 3.4 より、これは $n \mid a - a'$ かつ $n \mid b - b'$ と同じことです。そこで $a - a' = nk$、$b - b' = nl$（$k, l \in \mathbb{Z}$）と書けます。

加法。

$$(a + b) - (a' + b') = (a - a') + (b - b') = nk + nl = n(k + l)$$

で $k + l \in \mathbb{Z}$ なので $n \mid (a+b) - (a'+b')$、よって Lemma 4.2 の (2) から $[a+b] = [a'+b']$。

乗法。 差を直接計算すると $ab - a'b'$ ですが、これは因数分解できません。そこで $a'b$ を足して引く定石を使います。

$$ab - a'b' = ab - a'b + a'b - a'b' = (a - a')b + a'(b - b') = nkb + a'nl = n(kb + a'l).$$

$kb + a'l \in \mathbb{Z}$ なので $n \mid ab - a'b'$、よって $[ab] = [a'b']$。

なお、より正確には Theorem 5.1 を 2 変数版として使っています。写像 $\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$、$(a, b) \mapsto [a + b]$ が $\mathbb{Z} \times \mathbb{Z}$ 上の同値関係「両成分がそれぞれ合同」と整合することを、いま確かめたわけです。

∎

Example 5.5（Z/6Z で方程式を解く）

$\mathbb{Z}/6\mathbb{Z}$ で $[4]x = [2]$ を解きます。Example 4.5 より $x$ の候補は $[0], [1], \ldots, [5]$ の 6 個だけなので、すべて代入すれば済みます。Theorem 5.4 のおかげで、代表元で計算して最後に類に戻す操作が正当化されています。

$$\begin{array}{c|cccccc} x & [0] & [1] & [2] & [3] & [4] & [5] \\ \hline [4]x & [0] & [4] & [8]=[2] & [12]=[0] & [16]=[4] & [20]=[2] \end{array}$$

$8 = 6 + 2$、$12 = 6 \cdot 2$、$16 = 12 + 4$、$20 = 18 + 2$ から各欄を計算しました。したがって解は $x = [2]$ と $x = [5]$ の 2 個です。

整数や実数の世界では 1 次方程式 $4x = 2$ の解はただ一つ $x = 1/2$ ですが、商集合の世界では解が 2 個になりました。$[4] \cdot [3] = [12] = [0]$ のように、$0$ でない元どうしの積が $0$ になる（零因子がある）ことがその原因です。商を取ると性質が変わることを、この例は具体的に示しています。

Example 5.6（well-defined でない「定義」）

確認を怠るとどうなるかを見ます。

(a) 冪。 $\mathbb{Z}/5\mathbb{Z}$ 上で $[a]^{[b]} := [a^b]$ と定めたくなります。$b = 1$ で計算すると $[2]^{[1]} = [2^1] = [2]$ です。ところが $6 - 1 = 5$ なので $[1] = [6]$ であり、代表元を $6$ に取り替えると $[2]^{[6]} = [2^6] = [64]$。$64 = 5 \cdot 12 + 4$ なので $[64] = [4]$ です。$[2] \ne [4]$（差 $2$ は $5$ の倍数でない）なので、この規則は 2 通りの値を返します。写像になっていません。

(b) 分数の分子と分母の和。 分数を対 $(a, b)$（$b \ne 0$）で表し、$(a,b) \sim (c,d) :\iff ad = bc$ とします（Proposition 6.1 で同値関係だと示します）。ここで $F([(a,b)]) := a + b$ と定めたくなります。しかし $1 \cdot 4 = 2 \cdot 2$ より $(1, 2) \sim (2, 4)$ なのに、$1 + 2 = 3$ と $2 + 4 = 6$ は異なります。やはり写像ではありません。

(c) 代表元そのものを返す規則。 $F([a]) := a$ は、各同値類がただ 1 つの元しか含まない場合（すなわち $\sim$ が等号そのものである場合）を除き、well-defined ではありません。$[a] = [b]$ でも $a \ne b$ があり得るからです。

これらはすべて、Theorem 5.1 の条件 1 が破れている例です。(a) では $f(b) = [2^b]$ という写像が $b \equiv b' \pmod 5$ を保たない、というのが正体です。

6. 同値関係で「新しい数」を作る

同値関係の最大の使い道は、既にある数の体系から新しい体系を作ることです。整数から有理数を作る手順を、最後まで書き下します。

Proposition 6.1（分数の同値関係）

$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$ 上の同値関係である。

Proof（Proposition 6.1）

（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)$。

∎

Remark 6.2

推移律の証明で $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)$、したがって Lemma 4.2 の (2) より $[(1,2)] = [(2,4)]$、すなわち

$$\frac{1}{2} = \frac{2}{4}$$

です。小学校で習った等式は、同値類が集合として等しいという主張だったのです。$\frac12$ と $\frac24$ は「同じものの別の書き方」ではなく、「同じ集合を指す 2 つの代表元」です。加法を $[(a,b)] + [(c,d)] := [(ad + bc, bd)]$ で定めるとき、それが well-defined であることの確認が必要になります（Exercise 7.4）。

Remark 6.3

同じ手口は繰り返し使われます。実数はコーシー列全体を「差が $0$ に収束する」という同値関係で割って作られ、$0.999\ldots = 1$ という等式（1 = 0.999… の証明（Theorem 6.3）［What Is a Number? From the Naturals to the Reals, and Why 1 = 0.999… Is True］）もこの商集合における同値類の一致として説明できます。詳しくは 数とは何か？ を参照してください。

集合の「濃度」も、全単射が存在するという関係（対等（Definition 3.1）［濃度と無限］。これは 同値関係の 3 条件（Proposition 3.2）［濃度と無限］ を満たします）で集合を分類したものです。ただしすべての集合を集めたものは集合ではないため、商集合を素朴に作れないという技術的な困難があります（濃度そのものを定義しようとすると（Remark 3.3）［濃度と無限］）。この点は 濃度と無限 で扱います。

7. 演習

Exercise 7.1標準

次の各関係について、反射律・対称律・推移律のそれぞれが成り立つかを判定し、成り立つ場合は証明、成り立たない場合は反例を挙げてください。

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$ からの距離が等しい。

Solution

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$。したがって対称律と推移律だけが成り立ち、同値関係ではありません。Remark 3.3 の状況の実例です。

2. 3 条件すべて成り立ち、同値関係です。(E1) $x - x = 0 \in \mathbb{Q}$。(E2) $x - y \in \mathbb{Q}$ ならば $y - x = -(x-y) \in \mathbb{Q}$（有理数は符号反転で閉じている）。(E3) $x - y \in \mathbb{Q}$、$y - z \in \mathbb{Q}$ ならば $x - z = (x-y) + (y-z) \in \mathbb{Q}$（有理数は加法で閉じている）。同値類は $[x] = x + \mathbb{Q}$ で、たとえば $[\sqrt2\,]$ と $[0] = \mathbb{Q}$ は異なります（平方根 2 の無理性（Theorem 7.5）［Techniques of Proof］ より $\sqrt2 \notin \mathbb{Q}$）。

3. 3 条件すべて成り立ちます。$d(P) = \lVert P \rVert$ と書けば $P \sim Q \iff d(P) = d(Q)$ であり、これは実数の等号を $d$ で引き戻したものなので、Corollary 5.3 の $\sim_f$ の形をしています。よって同値関係です。同値類は原点中心の円周（半径 $0$ のときは $\{O\}$）で、商集合は $[0, \infty)$ と全単射になります。

Exercise 7.2標準

$\mathbb{Z}/12\mathbb{Z}$ において次の方程式の解をすべて求めてください。

1. $[7]x = [3]$
2. $[8]x = [4]$

解の個数が異なる理由も説明してください。

Solution

1. $7 \cdot 7 = 49 = 48 + 1$ なので $[7][7] = [1]$、つまり $[7]$ は乗法逆元を持ちます。両辺に $[7]$ を掛けると $x = [7][3] = [21]$、$21 = 12 + 9$ なので $x = [9]$。検算すると $7 \cdot 9 = 63 = 60 + 3 = 12 \cdot 5 + 3$ なので $[7][9] = [3]$。逆元を持つ元を掛ける操作は可逆なので、解はこの 1 個だけです。

2. $8x$ を $x = [0], \ldots, [11]$ について計算します。$8x \bmod 12$ は順に $0, 8, 4, 0, 8, 4, 0, 8, 4, 0, 8, 4$ です（$8 \cdot 3 = 24 = 12 \cdot 2$ なので周期 $3$ で繰り返します）。値が $4$ になるのは $x = [2], [5], [8], [11]$ の 4 個です。

理由。 $7$ と $12$ は互いに素なので $[7]$ は逆元を持ち、掛け算が全単射になるため解は一意です。一方 $\gcd(8, 12) = 4 \ne 1$ で、$[8][3] = [24] = [0]$ のように $[8]$ は零因子です。掛け算が単射でなくなるぶん、解が複数現れます。Example 5.5 と同じ現象です。

Exercise 7.3標準

次の対応が well-defined かどうかを判定し、理由を述べてください。$n$ は正の整数、$[a]_m$ は法 $m$ の剰余類を表します。

1. $F : \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$、$F([a]_n) = [a^2]_n$。
2. $G : \mathbb{Z}/6\mathbb{Z} \to \mathbb{Z}/3\mathbb{Z}$、$G([a]_6) = [a]_3$。
3. $H : \mathbb{Z}/3\mathbb{Z} \to \mathbb{Z}/6\mathbb{Z}$、$H([a]_3) = [a]_6$。

Solution

1. well-defined です。 $[a]_n = [a']_n$ とすると Theorem 5.4 の乗法の部分を $b = a$、$b' = a'$ として適用でき、$[a^2]_n = [a \cdot a]_n = [a' \cdot a']_n = [a'^2]_n$。

2. well-defined です。 $[a]_6 = [a']_6$ とすると $6 \mid a - a'$、すなわち $a - a' = 6k$。このとき $a - a' = 3(2k)$ で $2k \in \mathbb{Z}$ なので $3 \mid a - a'$、よって $[a]_3 = [a']_3$。一般に $m \mid n$ ならば $\mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/m\mathbb{Z}$ が同じ理由で定まります。

3. well-defined ではありません。 $[0]_3 = [3]_3$ です（$3 - 0 = 3$ は $3$ の倍数）。しかし $H$ の右辺は $[0]_6$ と $[3]_6$ になり、$3 - 0 = 3$ は $6$ の倍数でないのでこれらは異なります。粗い分割から細かい分割へは、一般には降りられません。

Exercise 7.4難

Proposition 6.1 の記号のもとで、$\mathbb{Q} = S/\!\sim$ 上の加法を

$$[(a,b)] + [(c,d)] := [(ad + bc,\ bd)]$$

で定めます。これが well-defined であること、すなわち (i) 右辺が $S$ の元であること、(ii) $[(a,b)] = [(a',b')]$ かつ $[(c,d)] = [(c',d')]$ ならば $[(ad+bc, bd)] = [(a'd'+b'c', b'd')]$ であることを示してください。

Solution

(i) $b \ne 0$ かつ $d \ne 0$ なので、整数環に零因子がないことから $bd \ne 0$。よって $(ad + bc, bd) \in S$ です。この確認を飛ばすと、そもそも右辺が定義域の外に出てしまいます。

(ii) 仮定は Lemma 4.2 の (2) より $ab' = a'b$ と $cd' = c'd$ です。示すべきは

$$(ad + bc)(b'd') = (bd)(a'd' + b'c')$$

です。左辺を展開して、仮定を使って書き換えます。

$$\begin{aligned} (ad + bc)(b'd') &= ab'dd' + bb'cd' \\ &= (a'b)dd' + bb'(c'd) \qquad (ab' = a'b,\ cd' = c'd \text{ を代入}) \\ &= bd(a'd') + bd(b'c') \\ &= (bd)(a'd' + b'c'). \end{aligned}$$

3 行目では $a'b\,dd' = bd \cdot a'd'$ と $bb'c'd = bd \cdot b'c'$ を、整数の乗法の可換性と結合性で並べ替えました。よって両辺は等しく、加法は well-defined です。

同様に乗法 $[(a,b)] \cdot [(c,d)] := [(ac, bd)]$ も well-defined です。実際 $ab' = a'b$、$cd' = c'd$ の辺々を掛けると $(ac)(b'd') = ab' \cdot cd' = a'b \cdot c'd = (bd)(a'c')$ が得られます。

参考文献

• 松坂和夫『集合・位相入門』岩波書店、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$ で結ばれた点をたどって行き来できる」という関係が、生成される同値関係の正体です。