良序

$\mathbb{N}$ 上的數學歸納法之所以有效，是因為不存在無限向下的鏈 $\cdots < n_2 < n_1 < n_0$：每個非空的自然數集合都有一個最小元素。這個性質——稱為良序性（well-ordering）——嚴格強於全序，且事實上等價於歸納法本身。

定義

全序 $(S, \leq)$ 是良序（well-order），若 $S$ 的每個非空子集都有最小元素：

$$\forall A \subseteq S,\quad A \neq \emptyset \;\Longrightarrow\; \exists\, m \in A \;\text{ such that }\; \forall a \in A,\; m \leq a$$

此時數對 $(S, \leq)$ 稱為良序集（well-ordered set）。

一個等價刻畫是用沒有無限嚴格遞降鏈的條件來替代「最小元素」條件：

$(S, \leq)$ 是良序，若且唯若 $S$ 中不存在無限序列 $a_0 > a_1 > a_2 > \cdots$。

這兩種表述是等價的，各自在不同的情境下很有用。「最小元素」的形式便於存在性論證；「無遞降鏈」的形式便於矛盾論證。

範例

$\leq$ 下的自然數

$(\mathbb{N}, \leq)$ 是典型的良序。給定任意非空的 $A \subseteq \mathbb{N}$，取任意 $a_0 \in A$。若 $a_0$ 不是 $A$ 的最小元素，則 $A$ 中存在嚴格更小的元素 $a_1$；若 $a_1$ 不是最小元素，則存在更小的 $a_2$；如此繼續。由於所有元素都是非負整數，這個嚴格遞降序列 $a_0 > a_1 > a_2 > \cdots$ 不能無限持續——你不能從一個自然數無限地減去 $1$。序列必然終止於 $A$ 的最小元素。

這個良序性是數學歸納法所依賴的基礎。

有限全序集

每個非空有限全序集都是良序的：有限集合的任何非空子集也是有限的，所以你可以掃描所有元素並記錄目前最小的，來找到其最小值。

$\mathbb{N}$ 的前段

對任意 $n \in \mathbb{N}$，集合 $\{0, 1, 2, \ldots, n\}$ 在通常的 $\leq$ 下是良序的，作為有限全序集。

反例

$\leq$ 下的整數

$(\mathbb{Z}, \leq)$ 是全序，但不是良序。子集 $\mathbb{Z}$ 本身沒有最小元素：對任意 $n \in \mathbb{Z}$，元素 $n - 1$ 嚴格更小。更明確地，子集 $\{\ldots, -3, -2, -1, 0\}$ 沒有最小值。

$\leq$ 下的有理數與實數

$(\mathbb{Q}, \leq)$ 和 $(\mathbb{R}, \leq)$ 都是全序，但都不是良序。開區間 $(0, 1)$ 是兩者的非空子集，且沒有最小元素：對任意 $q \in (0, 1)$，元素 $q/2$ 嚴格更小且仍在 $(0, 1)$ 中。

良序性與數學歸納法

對 $\mathbb{N}$ 而言，良序原理與數學歸納原理在邏輯上是等價的——各自蘊含另一個。

良序性蘊含歸納法。 設 $P$ 是自然數的一個性質。假設 $P(0)$ 成立，且對每個 $k \in \mathbb{N}$，$P(k) \Rightarrow P(k+1)$。定義失敗集：

$$F \;\coloneqq\; \{n \in \mathbb{N} \mid \neg P(n)\}$$

假設 $F$ 非空以得矛盾。由良序性，$F$ 有最小元素 $m$。由於 $P(0)$ 成立，$m \neq 0$，所以 $m \geq 1$ 且 $m - 1 \in \mathbb{N}$。由於 $m$ 是 $F$ 的最小元素，自然數 $m - 1$ 不在 $F$ 中，所以 $P(m - 1)$ 成立。套用歸納步驟得 $P(m)$，與 $m \in F$ 矛盾。因此 $F = \emptyset$，$P$ 普遍成立。

歸納法蘊含良序性。 利用強歸納法可以證明：對每個 $n \in \mathbb{N}$，$\{0, 1, \ldots, n\}$ 的每個非空子集都有最小值。將這些情形組合起來覆蓋整個 $\mathbb{N}$，建立了良序性。

這個等價性表明，$\mathbb{N}$ 的良序性並不是一個獨立的假設——它是從不同角度看到的同一個事實，即歸納法。

良序定理

一個自然的問題是：每個集合——即使是像 $\mathbb{R}$ 這樣的不可數集合——是否都能被良序？

值得注意的是，答案是肯定的——但證明需要選擇公理（Axiom of Choice, AC），它斷言對任意非空集合的群體，你可以同時從每個集合中選取一個元素。由 AC 可以推出以下定理：

良序定理。 每個集合都能被良序。

良序定理在集合論的標準 Zermelo–Fraenkel 公理（ZF）框架內等價於 AC：各自蘊含另一個。這意味著儘管 $\mathbb{R}$ 原則上可以被良序，但這個良序卻無法被明確寫下來——其存在性是非構造性的。沒有任何公式能告訴你哪個實數排在第一個。

摘要

• 良序是每個非空子集都有最小元素的全序；等價地，不存在無限嚴格遞降序列。
• $(\mathbb{N}, \leq)$ 是原型良序；每個有限全序集也是良序的。
• $(\mathbb{Z}, \leq)$、$(\mathbb{Q}, \leq)$ 和 $(\mathbb{R}, \leq)$ 是全序但不是良序。
• $\mathbb{N}$ 上的良序原理與數學歸納法在邏輯上等價。
• 良序定理指出每個集合都能被良序，但這需要——且實際上等價於——選擇公理。