5.2 强归纳法与良序性
强归纳法¶
强归纳法，也称 数学归纳法第二原理，或称为完全归纳法。
要证明对所有的正整数 \(n\) 而言，都有 \(P(n)\) 为真，其中 \(P(n)\) 为命题函数，我们需要完成以下两个步骤：
-
基础步骤：
证明 \(P(1)\) 为真。
-
归纳步骤：
要证明对所有正整数 \(k\) 来说，蕴含式
$$ [P(1) \land P(2) \land \cdots \land P(k)] \to P(k+1) $$ 也为真。
例——爬楼梯¶
假设我们能到达无限高梯子的第1个和第2个阶梯，且知道如果能到达某个阶梯，那么就能到达高出两阶的那个阶梯。我们能否用数学归纳法或强归纳法证明“我们能到达每一个阶梯”？
数学归纳法证明¶
基础步骤：
该证明的基础步骤是成立的，只需验证我们能到达第1个阶梯。
归纳步骤：
归纳假设是命题“我们能到达第 \(k\) 个阶梯”。为了完成归纳步骤，需要证明：如果假定归纳假设是对正整数 \(k\) 而言的，即我们能到达第 \(k\) 个阶梯，那么就能到达第 \(k+1\) 个阶梯。然而，这里无法完成归纳步骤，因为从给定信息来看，我们不知道是否能从第 \(k\) 个阶梯到达第 \(k+1\) 个阶梯。我们只知道“如果我们能到达一个阶梯，那么就能到达高出两阶的那个阶梯”。
强归纳法证明¶
基础步骤：
基础步骤与数学归纳法相同，只需验证我们能到达第1个阶梯。
归纳步骤：
归纳假设是命题“我们能到达前 \(k\) 个阶梯中的每个阶梯”。为了完成归纳步骤，需要证明：在归纳假设为真的情况下，即如果我们能到达前 \(k\) 个阶梯中的每个阶梯，那么就能到达第 \(k+1\) 个阶梯。已经证明了我们能到达第2个阶梯。这里只需注意：只要 \(k > 2\)，那么就可以从第 \(k-1\) 个阶梯到达第 \(k+1\) 个阶梯，因为知道我们可以从某个阶梯到达高出两阶的那个阶梯。这样就由强归纳法完成了归纳步骤。
结论：
我们已经证明了：如果我们能到达无限高梯子的前两个阶梯，且对每个整数 \(k\)，如果我们能到达所有前 \(k\) 个阶梯，那么我们就能到达第 \(k+1\) 个阶梯，于是就能到达所有的阶梯。
计算几何中的强归纳法¶
- 多边形 是一个封闭的图形，由一系列叫做 边 的线段所构成。
- 每一对相邻的边都相交于一个公共的端点，称其为 顶点。
- 简单 多边形：任意两条不相邻的边没有交点。简单多边形把整个平面划分为 内部区域和外部区域
- 凸：连接多边形内部任意两点的线段都整个包含在该多边形内
- 三角化：通过加入不相交的对角线把一个简单多边形划分为多个三角形
定理1：具有 \(n\) 条边的简单多边形能够被三角形化为 \(n-2\) 个三角形，其中 \(n \geq 3\) 的整数
引理1：每个简单的至少四边的多边形都存在一条内部对角线
定理1证明¶
命题 \(T(n):\) 具有 \(n\) 条边的简单多边形能够被三角化为 \(n-2\) 个三角形
基础步骤：
\(T(3)\) 为真
归纳步骤：
需要证明：当归纳假设为真时，\(T(k+1)\) 也为真，即具有 \(k+1\) 条边的任意简单多边形都能被三角形化为 \((k+1)-2 = k-1\) 个三角形。
-
假设多边形 \(P\) 有 \(k+1\) 条边：
-
由于 \(k+1 \geq 4\)，根据引理1，\(P\) 中存在一条内部对角线 \(ab\)。
- 对角线 \(ab\) 将 \(P\) 分成两个简单多边形 \(Q\) 和 \(R\)，其中 \(Q\) 有 \(s\) 条边，\(R\) 有 \(t\) 条边。
-
\(Q\) 和 \(R\) 的边包括 \(P\) 的边和对角线 \(ab\)（公共边）。
-
边数关系：
-
\(Q\) 和 \(R\) 的边数满足 \(3 \leq s \leq k\) 和 \(3 \leq t \leq k\)。
-
多边形 \(P\) 的边数比 \(Q\) 和 \(R\) 的边数之和少2条：
$$ k+1 = s + t - 2 $$
-
归纳假设的应用：
-
根据归纳假设，\(Q\) 可以被三角形化为 \(s-2\) 个三角形，\(R\) 可以被三角形化为 \(t-2\) 个三角形。
-
合并三角形化：
-
\(Q\) 和 \(R\) 的三角形化合并后构成了 \(P\) 的三角形化。
-
总三角形数为：
$$ (s-2) + (t-2) = s + t - 4 = (k+1) - 2 $$
通过以上步骤，完成了强归纳法的证明，即证明了：具有 \(n\) 条边的简单多边形可以被三角形化为 \(n-2\) 个三角形，其中 \(n \geq 3\)。
引理1证明¶
略
良序性¶
数学归纳法原理和强归纳法的有效性源于整数集合的基本公理——良序性公理。
该公理断言：任意一个非空的非负整数集合都有最小元素。即，自然数集合中不包含任何无限严格递减的序列。
可以证明，良序性公理、数学归纳法以及强归纳法之间是等价的。
例¶
命题：前n个奇正整数的和等于n的平方。
设命题 \(P(n)\) 为题目中所述的性质。考虑集合 \(S = \{n \geq 1 \mid P(n) \text{ 不成立}\}\)。我们声称 \(S = \varnothing\)。
为了导出矛盾，假设 \(S \neq \varnothing\)。
根据良序性（WO），集合 \(S\) 包含一个最小元素，记为 \(n_0\)。
由于 \(1^2 = 1\) 且 \(P(1)\) 成立，因此 \(n_0 > 1\)。
因此，\(n_0 - 1 \geq 1\)。根据 \(n_0\) 的最小性，\(n_0 - 1 \notin S\)。
因此，\(P(n_0 - 1)\) 成立，即：
接下来考虑：
因此，\(P(n_0)\) 成立，这与 \(n_0 \in S\) 矛盾。
综上所述，\(S = \varnothing\)，即 \(P(n)\) 对所有 \(n \geq 1\) 都成立。
\(WO \equiv MI \equiv SI\)¶
- Well-ordering property
- Mathematical induction
- Strong induction
\(WO \Rightarrow MI\)¶
假设 \(P(0)\) 成立，并且对于每个 \(n \geq 0\)，若 \(P(n)\) 成立，则 \(P(n+1)\) 也成立。
为了导出矛盾，假设存在某个 \(n \geq 0\) 使得 \(P(n)\) 不成立。
设集合 \(S\) 是所有使得 \(P(n)\) 不成立的 \(n \geq 0\) 的集合。显然，\(S\) 非空。
根据良序性原理，\(S\) 包含一个最小元素，记为 \(n_0\)。
显然，\(n_0 > 0\)，因为 \(P(0)\) 成立。
由于 \(n_0\) 是 \(S\) 的最小元素，因此 \(n_0 - 1\) 不在 \(S\) 中。因此，\(P(n_0 - 1)\) 成立。
根据假设，若 \(P(n_0 - 1)\) 成立，则 \(P(n_0)\) 也成立，这与 \(n_0 \in S\) 矛盾。
综上所述，\(P(n)\) 对所有 \(n \geq 0\) 都成立。
\(MI \Rightarrow SI\)¶
假设 \(P(0)\) 成立，并且对于每个 \(n \geq 0\)，若 \(P(0), \ldots, P(n)\) 都成立，则 \(P(n+1)\) 也成立。
定义 \(Q(n)\) 表示对于所有 \(0 \leq n' \leq n\)，\(P(n')\) 成立。
- 基础步骤：
由于 \(P(0)\) 成立，因此 \(Q(0)\) 也成立。
- 归纳步骤：
假设对于某个 \(n \geq 0\)，\(Q(n)\) 成立，即 \(P(0), \ldots, P(n)\) 都成立。根据题设条件，这意味 \(P(n+1)\) 也成立。因此，\(P(0), \ldots, P(n), P(n+1)\) 都成立，即 \(Q(n+1)\) 成立。
根据数学归纳法（MI），我们得出对于所有 \(n \geq 0\)，\(Q(n)\) 成立。
- 结论：
由于对于每个 \(n \geq 0\)，\(Q(n)\) 成立意味着 \(P(n)\) 成立，因此我们得出对于所有 \(n \geq 0\)，\(P(n)\) 成立。
\(SI \Rightarrow WO\)¶
假设 \(S \subseteq \mathbb{N}\) 是一个非空集合。
为了导出矛盾，假设 \(S\) 没有最小元素。
定义 \(P(n)\) 表示 \(n \notin S\)。
- 基础步骤：
首先，\(0 \notin S\)。否则，如果 \(0 \in S\)，则 \(0\) 是 \(S\) 的最小元素，导致矛盾。因此，\(P(0)\) 成立。
- 归纳步骤：
假设对于某个 \(n \geq 0\)，\(P(0), \ldots, P(n)\) 都成立，即 \(0, 1, \ldots, n \notin S\)。
为了导出矛盾，假设 \(n+1 \in S\)。
则 \(n+1\) 是 \(S\) 的最小元素，导致矛盾。
因此，\(n+1 \notin S\)，即 \(P(n+1)\) 成立。
根据数学归纳法（SI），对于所有 \(n \geq 0\)，\(P(n)\) 成立，即 \(n \notin S\)。
因此，\(S = \varnothing\)，这与 \(S\) 非空的假设矛盾。
综上所述，\(S\) 必须包含一个最小元素。