2. 良序原理

非负整数集 $N$ 的每一个非空子集都有一个最小元素，这被称作 良序原理（Well Order Principle）。良序原理与选择公理等价，是皮亚诺算术公理体系中的一条基本公理。

良序原理能被应用的前提是集合是良序集。例如，整数集 $Z$ 与正实数集 $R^{+}$ 都没有最小元素，因此不能应用良序原理。其等价判定方法是集合不存在一个无限的递减序列。

良序原理可以借助反证法用于证明一系列形如“对 $\forall n \in N$ ， $P (n)$ 成立”的命题。其基本过程如下：

定义 $C$ 为使 $P (n)$ 为假的反例集合，即：

C \equiv {n \in N ∣ \neg P (n)}

假设反例存在，则集合 $C$ 非空。
由于 $C \subseteq N$ ，根据良序原理， $C$ 有一个最小元素 $n_{0}$ 。
依照 $P (n)$ 的具体形式导出矛盾结论，有两种可能：
- 存在元素 $m < n$ ，且 $m \in C$
- $P (n_{0})$ 为真， $n_{0} \notin C$ 。
导出了矛盾结论，证明 $C$ 一定为空集，不存在反例，原命题得证。

我们下面尝试应用良序原理证明一些过去认为理所应当正确的命题：

例一

证明所有有理数都可以写成最简分数 $\frac{m}{n}$ 的形式，其中 $gcd (| m |, | n |) = 1$ 。

解答

假设命题不成立，则存在有理数不能写成最简分数。定义集合

C \equiv {| m | \in N | \exists n \in N^{+} 使得 \frac{m}{n} 无法化简至最简形式} .

由假设， $C$ 非空。根据良序原理， $C$ 有最小元素 $m_{0}$ 。则存在 $n_{0} > 0$ 使得 $\frac{m_{0}}{n_{0}}$ 不能写成最简形式，即 $gcd (m_{0}, n_{0}) > 1$ 。显然 $0 \notin C$ ，即 $m_{0} > 0$ 。

设 $p > 1$ 是 $m_{0}$ 和 $n_{0}$ 的一个公共质因数。考虑分数 $\frac{m_{0} / p}{n_{0} / p}$ ，显然 $\frac{m_{0} / p}{n_{0} / p} = \frac{m_{0}}{n_{0}} .$

若 $\frac{m_{0} / p}{n_{0} / p}$ 可写成最简形式，则 $\frac{m_{0}}{n_{0}}$ 也可写成最简形式，该最简形式即为 $\frac{m_{0} / p}{n_{0} / p}$ ，矛盾。

因此 $\frac{m_{0} / p}{n_{0} / p}$ 不能写成最简形式，从而 $m_{0} / p \in C$ 。但 $m_{0} / p < m_{0}$ ，与 $m_{0}$ 是 $C$ 的最小元矛盾。

故假设错误， $C$ 必为空集。所有有理数均可写成最简分数。

例二

证明

\sum_{i = 1}^{n} = \frac{n (n + 1)}{2}

解答

假设命题不成立，设反例集合

C \equiv {n \in N^{+} | \sum_{i = 1}^{n} i \neq \frac{n (n + 1)}{2}} .

由假设， $C \neq \emptyset$ 。由良序原理， $C$ 有最小元 $m$ 。

由于当 $n = 1$ 时：

\sum_{i = 1}^{1} i = 1, \frac{1 \cdot 2}{2} = 1.

等式成立，故 $m > 1$ 。

因 $m$ 是 $S$ 的最小元，则 $m - 1 \notin C$ ，即等式对 $n = m - 1$ 成立：

\sum_{i = 1}^{m - 1} i = \frac{(m - 1) m}{2} .

对该式两边同时加 $m$ 有

\sum_{i = 1}^{m} i = \sum_{i = 1}^{m - 1} i + m = \frac{(m - 1) m}{2} + m = \frac{m^{2} - m + 2 m}{2} = \frac{m (m + 1)}{2} .

这表明等式对 $n = m$ 成立，与 $m \in C$ 矛盾。则 $C = \emptyset$ ，故原等式对所有正整数 $n$ 成立。

并非只在非负整数集 $N$ 上有良序原理成立。如果一个集合的所有非空子集均有一个最小元素，我们就称这个集合是 良序的^[1]。例如所有的有限集合都是良序集；大于任意数字 $x$ 的整数构成的集合也是良序的。然而，有最小元素的集合并不一定是良序的，其所有非空子集也得有最小元素才行，例如非负有理数集合。

我们定义一个集合 $S$ 的下界 $b$ 满足对 $\forall s \in S$ ，有 $b \leq s$ 。^[2]上界的定义与之类似。显然任何有下界的非空整数集合都是良序的，而任何有上界的非空整数集合都有一个最大元素。

我们定义这样一个集合

F \equiv {\frac{n}{n + 1} | n \in N}

显然集合 $F$ 是一个良序集。我们向该集合任意添加一个非负整数 $n$ ，称该集合为 $N + F$ ，该集合同样是良序的。

此处对于良序集的定义并不严谨。严谨的定义请见Wikipedia。 ↩︎
此处定义同样不严谨。 ↩︎