02.2 關係與等價類：劃分如何產生商集合#

1. 為什麼需要「關係」#

集合只回答「哪些東西在場」（02.1 節）；數學更關心對象之間的聯繫：「 \(3 < 5\) 」「 \(7 \equiv 2 \pmod 5\) 」「兩三角形相似」。Frege（1879）指出：關係不是命題的裝飾，而是量詞邏輯的基本成分。Cayley（1857）研究化學分子結構時更把「元素間的鍵結」畫成圖——關係的可視化就是圖論（第 05 章的歷史起點）。本節聚焦一種最重要的關係：等價關係，它教會我們數學的核心操作——把不重要的差異除掉。

2. 二元關係#

定義 2.1（笛卡兒積）： \(A \times B = \{(a, b) : a \in A, b \in B\}\) 。

定義 2.2（二元關係）：從 \(A\) 到 \(B\) 的二元關係是 \(A \times B\) 的子集 \(R\) 。記 \((a,b) \in R\) 為 \(a \, R \, b\) 。若 \(B = A\) 稱為 \(A\) 上的關係。

範例 2.3： \(A = \{1,2,3,4\}\) ， \(R = \{(a,b) : a < b\} = \{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}\) 。

定義 2.4（關係的基本性質， \(R \subseteq A \times A\) ）：

• 自反： \(\forall a\, (a R a)\) 。
• 對稱： \(\forall a \forall b\, (a R b \to b R a)\) 。
• 反對稱： \(\forall a \forall b\, (a R b \land b R a \to a = b)\) 。
• 傳遞： \(\forall a \forall b \forall c\, (a R b \land b R c \to a R c)\) 。

兩大陣營：

同樣三條性質，加上「對稱」或「反對稱」就分岔出兩個世界：一個把對象黏合，一個把對象排隊。本節走前者，偏序見第 05 章。

3. 等價關係與等價類#

定義 3.1（等價類）：給定 \(A\) 上的等價關係 \(\sim\) 與 \(a \in A\) ，等價類

引理 3.2（等價類的基本引理）：對任意 \(a, b \in A\) ： \(a \sim b \iff [a] = [b]\) ，且 \(a \not\sim b \iff [a] \cap [b] = \varnothing\) 。

證明： （ \(\Rightarrow\) ）設 \(a \sim b\) 。對任意 \(x \in [a]\) ，即 \(x \sim a\) ；由傳遞性 \(x \sim b\) ，故 \(x \in [b]\) ，得 \([a] \subseteq [b]\) 。由對稱性 \(b \sim a\) ，同理得 \([b] \subseteq [a]\) 。 （ \(\Leftarrow\) ）設 \([a] = [b]\) 。由自反性 \(a \in [a] = [b]\) ，故 \(a \sim b\) 。 第二式：若 \([a] \cap [b] \ne \varnothing\) ，取 \(x\) 屬於兩者，則 \(x \sim a, x \sim b\) ，由對稱與傳遞得 \(a \sim b\) 。逆否即得。 \(\blacksquare\)

定義 3.3（劃分與商集合）： \(A\) 的劃分是一族非空子集 \(\{A_i\}\) ，兩兩互斥且聯集為 \(A\) 。等價關係的全體等價類構成劃分，此劃分稱為商集合 \(A / \sim\) 。

定理 3.4（劃分 \(\leftrightarrow\) 等價關係）： \(A\) 上的等價關係與 \(A\) 的劃分一一對應。

證明：（ \(\to\) ）引理 3.2 說明等價類兩兩互斥或相等，且每個 \(a\) 屬於 \([a]\) ，故等價類族是劃分。 （ \(\leftarrow\) ）給定劃分 \(\{A_i\}\) ，定義 \(a \sim b \iff a, b\) 同屬某個 \(A_i\) 。自反： \(a\) 屬於某塊。對稱、傳遞顯然（同塊關係可拼接）。故 \(\sim\) 是等價關係，且其等價類恰為各 \(A_i\) 。兩個方向互逆，故一一對應。 \(\blacksquare\)

這條定理是本節的靈魂：等價關係（語法層）與劃分（物件層）是同一件事的兩種講法。數學家常說「模掉某等價關係」——其實就是在宣告：這個劃分以後就是我的新宇宙。

4. 商集合如何誕生新數學對象#

範例 4.1（同餘與 \(\mathbb{Z}_n\) ，Gauss 1801《算術研究》）： \(\mathbb{Z}\) 上定義 \(a \equiv b \pmod n \iff n \mid (a-b)\) 。這是等價關係（自反： \(n \mid 0\) ；對稱、傳遞由整除性質立得）。等價類：

在商集合上繼承運算： \([a] + [b] = [a+b]\) 。這是良定義（well-defined）嗎？必須檢查：換代表元結果不變。若 \(a \equiv a'\) 、 \(b \equiv b'\) ，則 \(a+b \equiv a'+b'\) ，故 \([a+b] = [a'+b']\) 。 \(\checkmark\)

# 同餘類的加法表：商集合上繼承的運算
n = 5
def add(x, y): return (x + y) % n

table = [[add(i, j) for j in range(n)] for i in range(n)]
for row in table:
    print(row)
# [0, 1, 2, 3, 4]
# [1, 2, 3, 4, 0]
# [2, 3, 4, 0, 1]
# [3, 4, 0, 1, 2]
# [4, 0, 1, 2, 3]

# 良定義性的程式驗證：換代表元，結果不變
assert add(2, 3) == add(7, 13)   # 2≡7, 3≡13 (mod 5)
assert (2 + 3) % 5 == (7 + 13) % 5

範例 4.2（有理數的定義）： \(\mathbb{Q}\) 不是「分數」，而是

「 \(1/2 = 2/4\) 」不是巧合而是定義——它們在同一等價類。驗證良定義（ \(ad=bc \wedge a'd'=b'c' \Rightarrow (a+b)d' = (a'+b')c'\) 型計算）是每個代數課的標準習題。商構造是數學創造新對象的萬用模板： \(\mathbb{Z}_n\) 、 \(\mathbb{Q}\) 、 \(\mathbb{R}/\mathbb{Q}\) 、幾何中的商空間，乃至電腦科學的 hash 表（雜湊值即等價類）。

範例 4.3（Python 中的等價類計算）：

from collections import defaultdict

def classes(A, eq):
    d = defaultdict(list)
    for a in A:
        d[eq(a)].append(a)     # 以「規範代表元」為鍵分組
    return dict(d)

# mod 4 的等價類
print(classes(range(12), lambda a: a % 4))
# {0: [0,4,8], 1: [1,5,9], 2: [2,6,10], 3: [3,7,11]}

# 有理數等價類（最簡分數為規範代表元）
from math import gcd
def rat_key(pair):
    a, b = pair
    g = gcd(abs(a), b);  g = g if g else 1
    return (a // g, b // g)
print(classes([(1,2),(2,4),(-1,-2),(3,5),(6,10)], rat_key))

hash、正規化、canonical form——工程界的每一天都在做「選等價類代表元」。

範例 4.4（日期星期——等價關係的日常應用）：「 \(a\) 與 \(b\) 是同一天」在「第幾個星期幾」的意義下就是 \(\mathbb{Z}\) 上的 mod 7 同餘。行事曆軟體把無窮的日期序列壓成 7 個等價類，正是商構造：

import datetime
# 2026-10-19 是星期幾？—— mod 7 的等價類
d = datetime.date(2026, 10, 19)
print(d.weekday())          # 0=星期一
# 任何 7k 天後落在同一等價類
assert (d + datetime.timedelta(days=35)).weekday() == d.weekday()

5. 深入：為什麼良定義檢查不可省略#

在商集合上定義 \(f([a]) =\) 依 \(a\) 算出的值時，若 \(f\) 的輸出依賴代表元，就不是函數。經典反例：在 \(\mathbb{Z}_5\) 上試圖定義 \(f([a]) = a \bmod 10\) 。 \([2]\) 的代表元 \(2\) 與 \(7\) 給出 \(f = 2\) 與 \(f = 7\) ，矛盾——這個「定義」非法。

定理 5.1（商的泛性質，預告）：設 \(\pi : A \to A/{\sim}\) 為自然投影 \(\pi(a) = [a]\) 。則函數 \(g : A \to B\) 滿足 \(g(a) = g(a')\) （當 \(a \sim a'\) ）時，存在唯一函數 \(\bar g : A/{\sim} \to B\) 使 \(g = \bar g \circ \pi\) 。也就是：可降級到商集合的函數，恰是「尊重等價關係」的函數。

這條泛性質是範疇論「商對象」的雛形，也精確刻畫了「良定義」一詞。有趣的是它與 01.2 節的連結：泛性質是 \(\forall \exists\) （存在唯一 \(\bar g\) ）型敘述，其證明結構正是 01.3 節的「存在性 + 唯一性」兩段式。

歷史一瞥：Gauss 在 1801 年引入同餘記號時，實際上就是在 \(\mathbb{Z}\) 上宣告等價關係並使用商結構——比 Cantor 的集合論早了七十年。這再次說明：好結構常先於形式基礎被使用，集合論（02.1）是事後的統一地基。

6. 習題#

1. 證明「整除」關係在 \(\mathbb{N}\) 上自反、傳遞，但不對稱；在 \(\mathbb{Z} \setminus \{0\}\) 上甚至不反對稱（ \(2 \mid -2\) 且 \(-2 \mid 2\) ）。
2. \(\mathbb{Z}\) 上定義 \(a \sim b \iff a - b\) 為偶數。證明為等價關係，列出所有等價類，並證明恰有兩類。（這就是 02.1 習題提到的 \(\mathbb{Z}_2\) 的前世。）
3. 在 \(\mathbb{Z}_6\) 上驗證乘法 \([a][b] = [ab]\) 良定義，並找出所有滿足 \([a][b] = [0]\) 但 \([a],[b] \ne [0]\) 的情形（零因子——通往環論）。
4. 定義 \(\mathbb{R}^2\) 上 \((x,y) \sim (x',y') \iff y - x = y' - x'\) 。描述等價類（提示：直線），並說明商集合幾何上是什麼。
5. 用 Python 對 \(n = 6\) 生成 \(\mathbb{Z}_6\) 的加法與乘法表，找出「有乘法反元素」的等價類集合。對 \(n = 7\) 重做，比較結果並猜想什麼性質決定了反元素的存在。（這是 Euler–Fermat 定理的門口。）
6. 良定義反例：證明 \(\mathbb{Q}\) 上（以最簡分數為代表）規則 \(f\big(\tfrac{a}{b}\big) = a + b\) 不是良定義的。

7. 歷史備忘：Gauss 同餘記號的深遠影響#

Gauss 1801 年引進 \(a \equiv b \pmod n\) 的記號時，可能沒想到這個「等號的近似品」會成為現代代數的起點：同餘類的加減乘運算孕育了環的概念（每個 \(\mathbb{Z}_n\) 都是最小的有限環範例），而「哪些同餘類有乘法反元素」的問題（範例 4.3 習題的線索）孕育了域與 Euler–Fermat 定理（07.2 節），最終支撐起 RSA 密碼系統（07.3 節）。一個好的等價關係，值得一座新的數學分支。

8. 小結與下一步#

• 關係 = 笛卡兒積的子集；自反/對稱/傳遞的組合決定關係的性格。
• 等價關係 \(\leftrightarrow\) 劃分一一對應（定理 3.4）：語法與物件的兩面。
• 商集合是把「視為相同」形式化的工具；新對象上的運算必須通過良定義檢查。
• \(\mathbb{Z}_n\) 、 \(\mathbb{Q}\) 皆由商構造誕生；hash 與規範化是它的工程化身。

下一步：等價類告訴我們如何「合併」，但「多與少」呢？02.3 節用函數（單射、滿射、雙射）為集合稱重，定義基數，並用 01.3 節的對角線法劃出可數與不可數無限的分界——Cantor 定理： \(|A| < |\mathcal{P}(A)|\) ，無限之上還有無限。