2 良序原理
每一个非空的非负整数集都有一个最小元素。
这个声明被称为良序原理（WOP, Well Ordering Principle）。这看起来似乎很明显，对吧？但是注意它的前提条件：它要求是一个非空集合——对空集是不成立的，因为空集没有元素。它要求是非负整数集——对负整数集合以及某些非负有理数集也是不成立的，例如，正有理数集。因此，良序原理捕捉了非负整数的某些特殊性质。
虽然良序原理看起来很显而易见，但它的实用性并不是一眼就能看出的。事实上，它提供了离散数学中最重要的证明方法之一。在本章中，我们将通过一些简单的例子来展示这种证明方法的力量。
2.1 良序证明
事实上，在证明\(\sqrt{2}\)是无理数时，我们已经默认使用了良序原理。那个证明假设了对于任何正整数\(m\)和\(n\)，分数\(m/n\)都可以写成最简形式，即形式为\(m_0/n_0\)，其中\(m_0\)和\(n_0\)是没有共同质因数的正整数。我们怎么知道这总是可能的呢？
考虑反证法, 假设存在正整数\(m\)和\(n\)，使得分数\(m/n\)不能写成最简形式。现在令\(C\)是所有这样的分数的分子构成的正整数集合。那么\(m\)属于\(C\)，所以\(C\)是非空的。根据WOP，一定存在最小的整数\(m_0\)属于\(C\)。这样，根据\(C\)的定义，存在一个整数\(n_0>0\)，使得
这意味着\(m_0\)和\(n_0\)必须有一个共同的质因数\(p>1\)。但是
所以如果左边的分数是最简形式, 那么右边也是. 既然右边的不是最简形式, 那么分数\(\frac{m_0/p}{n_0/p}\)也不是最简的. 因此，根据\(C\)的定义，分子\(m_0/p\)属于\(C\)。但是\(m_0/p < m_0\)，这与\(m0\)是\(C\)中最小的元素相矛盾。
由于假设C是非空的导致了矛盾，因此必须是C为空。也就是说，不存在不能被写成最简形式的分数。
原来从一开始, 我们已经在不知不觉中就使用了良序原理！
2.2 良序证明的模板
更一般地，有一种标准的方法可以使用良序原理证明某个性质\(P(n)\)对每个非负整数\(n\)都成立。我们可以使用这个模板:
要使用良序原理证明 “对所有\(n\in N\)，\(P(n)\)都是真的”：
- 定义反例集\(C\)为\(P\)不成立的情况。具体来说，定义\(C \equiv {n \in N | \lnot P(n) \text{为真}}\)
- 假设反证法中\(C\)是非空的。
- 根据WOP，\(C\)中会有一个最小元素\(n\)。
- 以某种方式得到矛盾——通常是通过显示\(P(n)\)实际上是真的，或者显示\(C\)中有比\(n\)更小的另一个元素。这是证明任务中困难的部分。
- 得出结论\(C\)必须为空，即不存在反例。
我们用此来证明下面的定理
定理2.2.1
对于非负整数\(n\), 有\(1+2+3+\cdots+n=n(n+1) / 2\).
采用反证法。假设上述定理是假的。那么，一些非负整数作为它的反例。我们把它们收集到一个集合中：
假设存在反例，那么 \(C\) 是一个非空的非负整数集。因此，根据 WOP，\(C\) 存在一个最小元素，我们称之为 \(c\)。即，在非负整数中，\(c\) 是方程式 (2.1) 的最小反例。
由于 \(c\) 是最小的反例，我们知道 (2.1) 对 \(n = c\) 是假的，但对所有 \(n < c\) 的非负整数是成立的。然而，(2.1) 对 \(n = 0\) 是成立的，因此 \(c > 0\)。这意味着 \(c - 1\) 是一个非负整数，并且由于它小于 \(c\)，方程 (2.1) 对 \(c - 1\) 成立。即，
但是，然后将 \(c\) 加到两边，我们得到
这意味着方程 (2.1) 对 \(c\) 也成立！这就是一个矛盾，因此证明完成。
2.3 质因数分解
我们之前已经默认了素因数分解定理（Prime Factorization Theorem），也被称为唯一分解定理（Unique Factorization Theorem）和算术基本定理（Fundamental Theorem of Arithmetic），它指出每一个大于一的整数都有一个唯一的表达式作为质数的乘积。这是另一个被认为理所当然但在仔细观察时并不显然的数学事实。我们将在后面的章节中证明质因数分解的唯一性，但良序原理提供了一个简单的证明，证明每个大于一的整数都可以表达为某些质数的乘积。
定理2.3.1
每个大于1的正整数都可以分解为质数的乘积。
证明采用良序原理（WOP）。
设 \(C\) 为所有大于一且不能分解为质数乘积的整数的集合。我们假设 \(C\) 是非空的并得出一个矛盾。
如果 \(C\) 是非空的，根据良序原理（WOP），\(C\) 中存在一个最小的元素 \(n\)。这个 \(n\) 不可能是质数，因为质数本身被认为是（长度为一的）质数乘积，而这样的乘积不在 \(C\) 中。
所以 \(n\) 必须是两个整数 \(a\) 和 \(b\) 的乘积，其中 \(1 < a, b < n\)。由于 \(a\) 和 \(b\) 都小于 \(C\) 中的最小元素 \(n\)，我们知道 \(a, b \notin C\)。换句话说，\(a\) 可以表示为质数 \(p_1p_2 \cdots p_k\) 的乘积，\(b\) 可以表示为质数 \(q_1 \cdots q_l\) 的乘积。因此，\(n = p_1 \cdots p_k q_1 \cdots q_l\) 可以表示为质数的乘积，这与 \(n \in C\) 的声明相矛盾。我们的假设 \(C\) 是非空的，因此必须是错误的。
2.4 良序集合
当一个实数集的每个非空子集都有最小元素时，该集合被称为良序的。良序原理表明，非负整数集是良序的，但实际上还有许多其他的实数集按照这种更一般形式的良序原理也是良序的。一个简单的例子是集合 \(r\mathbb{N}\)，其中 \(r\) 是一个正实数，\(n \in \mathbb{N}\)（为什么这是可行的？）。
良序在计算机科学中常被用作证明计算不会无限运行的方法。这种方法的核心是为计算的每一步骤分配一个值，使得这些值在每一步都变小。如果这些值都来自一个良序集，那么计算就不可能无限运行，因为如果真的无限运行，就会定义出一个没有最小元素的子集。你将在第6章看到多个使用这种技术的例子，证明各种状态机最终会终止。
请注意，一个集合可能有最小元素但不是良序的。非负有理数集就是一个例子：它有最小元素零，但它也有非空子集没有最小元素——正有理数就是一个例子。
以下定理是良序原理的一个小小的推广。
定理2.4.1
对于任何非负整数 \(n\)，整数集大于或等于 \(-n\) 是良序的。
这个定理就像良序原理一样显而易见，接受它作为另一个公理也无伤大雅。但不断引入公理会在一段时间后变得令人担忧，当一个潜在的公理实际上可以被证明时，注意到这一点是值得的。这一次，我们可以轻松地使用良序原理来证明它：
设 \(S\) 为任何非空的整数集，其中的元素都 \(\geq -n\)。现在对 \(S\) 中的每个元素加上 \(n\)；我们将这个新集合称为 \(S + n\)。现在 \(S + n\) 是一个非空的非负整数集，因此根据良序原理，它有一个最小元素 \(m\)。但随后很容易看出，\(m - n\) 是 \(S\) 的最小元素。
良序的定义表明，一个良序集的每个子集都是良序的，这产生了上述定理 的两个方便的直接推论：
一个集合 \(S\) 的实数集的下界（或上界）是一个数 \(b\)，使得对每个 \(s \in S\)，都有 \(b \leq s\)（或 \(b \geq s\)）。
注意，集合 \(S\) 的下界或上界不要求在集合中。
任何具有下界的整数集都是良序的。
具有下界 \(b \in \mathbb{R}\) 的整数集也会有整数 \(n = \lfloor b \rfloor\) 作为下界，其中 \(\lfloor b \rfloor\) 称为 \(b\) 的下取整，通过将 \(b\) 向下舍入到最接近的整数得到。因此，定理 2.4.1 表明该集合是良序的。
上面的推论揭示了我们认为理所当然的另一个事实：
任何具有上界的非空整数集都有一个最大元素。
假设一个整数集 \(S\) 具有上界 \(b \in \mathbb{R}\)。现在将 \(S\) 中的每个元素乘以 -1；我们将这个新集合称为 \(-S\)。当然，\(-b\) 是 \(-S\) 的下界。因此，\(-S\) 由推论 2.4.3 有一个最小元素 \(-m\)。但很容易看出，\(m\) 是 \(S\) 的最大元素。
有限集是良序集的又一个常见例子。
每个非空的有限实数集都是良序的。
由于有限集的子集也是有限的，证明每个有限集都有一个最小元素就足够了。
我们使用良序原理来证明有限集的大小。
设 \(C\) 为正整数 \(n\) 的集合，使得某个大小为 \(n\) 的集合没有最小元素。假设为了反证 \(C\) 是非空的。根据良序原理，\(C\) 中存在一个最小整数 \(m\)。
每个大小为1的集合显然有一个最小元素，所以 \(m \geq 2\)。
现在令 \(F\) 为一个包含 \(m\) 个实数的集合。我们将通过证明 \(F\) 有一个最小元素来得出矛盾。
令 \(r_0\) 为 \(F\) 的一个元素。由于 \(m \geq 2\)，从 \(F\) 中移除 \(r_0\) 会留下一个比 \(m\) 小的非空集合 \(F^{\prime}\)。由于 \(m\) 是 \(C\) 中的最小元素，我们知道 \(F^{\prime}\) 有一个最小元素 \(r_1\)。但这意味着 \(r_0\) 和 \(r_1\) 中较小的一个是 \(F\) 的最小元素。
2.4.1 不太一样的良序集*
实际上由分数形式 \(n/(n + 1)\) 表示的分数的集合 \(\mathbb{F}\) 是良序的。任何 \(\mathbb{F}\) 的非空子集的最小元素就是当以 \(n/(n + 1)\) 形式表示时分子最小的那个。
现在我们可以通过将非负整数加到 \(\mathbb{F}\) 中的数来定义一个非常不同的良序集。即，我们取所有形式为 \(n + f\) 的数，其中 \(n\) 是非负整数，\(f\) 是 \(\mathbb{F}\) 中的一个数。让我们将这个数集称为——你猜对了——\(\mathbb{N} + \mathbb{F}\)。找到 \(\mathbb{N} + \mathbb{F}\) 的任何非空子集中的最小数有一个简单的配方，这解释了为什么这个集合是良序的：
引理 2.4.2
\(\mathbb{N} + \mathbb{F}\) 是良序的。
给定 \(\mathbb{N} + \mathbb{F}\) 的任何非空子集 \(S\)，查看所有非负整数 \(n\)，使得 \(n + f\) 在 \(S\) 中，对于某个 \(f \in \mathbb{F}\)。这是一个非空的非负整数集，所以根据良序原理（WOP），存在一个最小的整数；称之为 \(n_S\)。
根据 \(n_S\) 的定义，存在某个 \(f \in \mathbb{F}\)，使得 \(n_S + f\) 在 \(S\) 中。因此，所有分数 \(f\) 使得 \(n_S + f \in S\) 的集合是 \(\mathbb{F}\) 的一个非空子集，由于 \(\mathbb{F}\) 是良序的，这个非空子集包含一个最小元素；称之为 \(f_S\)。现在很容易验证 \(n_S + f_S\) 是 \(S\) 的最小元素。
集合 \(\mathbb{N} + \mathbb{F}\) 与上述例子显著不同，它提供了丰富的良序集的线索。在之前的所有例子中，每个元素只比有限数量的其他元素大。在 \(\mathbb{N} + \mathbb{F}\) 中，每个大于或等于 1 的元素都可以是任意有限长度的严格递减序列中的第一个元素。例如，以下在 \(\mathbb{N} + \mathbb{F}\) 中的递减序列都以 1 开头：
然而，由于 \(\mathbb{N} + \mathbb{F}\) 是良序的，在 \(\mathbb{N} + \mathbb{F}\) 中不可能找到一个无限递减序列，因为这样的序列中的元素集将没有最小元素。