第二章：良序原理
良序原理是數學證明中一個強大且基礎的工具，它與數學歸納法有著密切的關聯。
2.1 什麼是良序原理？
良序原理：
每一個非空的非負整數集合都有一個最小元素。
每一個非空的非負整數集合都有一個最小元素。
這聽起來似乎顯而易見，但這在數學上是一個非常重要的假設（公理）。例如：
- 集合 { 1, 2, 3 } 的最小元素是 1。
- 集合 { n ∈ N | n > 5 } 的最小元素是 6。
- 即使對於無限集合，如所有質數的集合，它也有最小元素 2。
非空集合 C
{7, 3, 9, 1, 15}
{7, 3, 9, 1, 15}
➡️
最小元素 m
1
1
2.2 證明模板互動練習
良序原理常用於證明某些特定性質對所有非負整數成立。其證明通常遵循一個標準的結構。
請將下列步驟拖曳或排序，組成正確的良序原理證明結構：
2.3 應用：質因數分解
良序原理的一個經典應用是證明每一個大於 1 的整數都可以分解為質數的乘積（算術基本定理的一部分）。
定理：每個整數 n > 1 都可以寫成質數的乘積。
證明思路：
假設存在反例（即存在不能分解為質數乘積的整數）。
令 C 為所有這些反例的集合。根據良序原理，C 有一個最小元素 m。
這個 m 不可能是質數（因為質數本身就是質數乘積）。所以 m 必須是合數，即 m = a * b。
因為 a 和 b 都比 m 小，且 m 是最小的反例，所以 a 和 b 都可以分解為質數乘積。
因此 m = a * b 也可以分解，這與 m 是反例矛盾。
2.4 良序集
我們可以將良序原理推廣到其他集合。
如果一個集合的每一個非空子集都有最小元素，則稱該集合為良序集。
- 非負整數集 (N) 是良序集。
- 整數集 (Z) 不是良序集，因為整數沒有下界（例如負整數集合 { -1, -2, -3, ... } 沒有最小元素）。
- 實數集 (R) 不是良序集，例如區間 (0, 1) 沒有最小元素。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)