第二章：良序原理 — 動畫敘事
第三集 · Ch.2 良序原理
最小的那個
你有沒有想過：如果一件事情是錯的，
那一定有「第一個錯的地方」。
這個直覺，就是良序原理的核心。
它看起來理所當然，卻能證明非常深刻的定理。
那一定有「第一個錯的地方」。
這個直覺，就是良序原理的核心。
它看起來理所當然，卻能證明非常深刻的定理。
良序原理
Well-Ordering Principle（WOP）
每一個非空的非負整數集合，都有一個最小元素。
例：集合 {7, 3, 9, 1, 15} → 最小元素是 1
例：所有質數的集合 → 最小元素是 2
例：所有大於 100 的整數 → 最小元素是 101
例：集合 {7, 3, 9, 1, 15} → 最小元素是 1
例：所有質數的集合 → 最小元素是 2
例：所有大於 100 的整數 → 最小元素是 101
聽起來很「顯然」？但它是一條公理——
數學家把它當作出發點，用它證明許多看似不明顯的事情。
數學家把它當作出發點，用它證明許多看似不明顯的事情。
哪些集合有良序？
不是所有集合都有最小元素。
ℕ
非負整數
0, 1, 2, 3 …
最小元素 = 0 ✓
最小元素 = 0 ✓
✓
任何有限集合
{5, 2, 8, 1}
最小元素 = 1 ✓
最小元素 = 1 ✓
ℤ
所有整數
… -3, -2, -1, 0, 1 …
沒有最小元素 ✗
沒有最小元素 ✗
ℝ
實數 (0,1)
0.1, 0.01, 0.001 …
趨近 0 但不到達 ✗
趨近 0 但不到達 ✗
應用：質因數分解定理
定理：每個大於 1 的整數都可以分解為質數的乘積。
用良序原理來證明：
用良序原理來證明：
1
假設存在「不能被質數分解的整數」，令 C 為所有這類整數的集合。
WOP
若 C 非空，由良序原理，C 有一個最小元素
m。3
m 不可能是質數（質數本身就是質數乘積）。
所以 m 是合數：
所以 m 是合數：
m = a × b，其中 1 < a, b < m。4
a 和 b 都比 m 小，且 m 是 C 的最小元素，
所以 a, b ∉ C——它們都能被質數分解。
所以 a, b ∉ C——它們都能被質數分解。
!
但
m = a × b，a 和 b 都能分解，所以 m 也能分解——矛盾！C 必定是空集合。∴ 定理成立。
良序原理的證明模板
用良序原理證明「P(n) 對所有非負整數成立」，有標準結構：
1
定義反例集合：
C = { n ∈ ℕ | P(n) 為假 }2
假設 C 非空（即：假設存在反例）。
WOP
由良序原理，C 有最小元素
m（最小的反例）。4
利用 m 是「最小反例」這個性質，推導出矛盾。
✓
矛盾 → C 是空集合 → P(n) 對所有 n 成立。
互動：排列證明步驟
把下列步驟拖曳排成正確的良序原理證明順序：
小結
1 / 7
本頁為動畫敘事版。看完後可前往
完整第二章
進行互動練習（拖曳排序步驟）。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)