自然数与归纳

• 1. Peano 公理
  • 1.1 对公理的直觉解释
• 2. 自然数的集合论构造
  • 2.1 Von Neumann 构造
  • 2.2 无穷公理的作用
• 3. 数学归纳法
  • 3.1 第一归纳法
  • 3.2 强归纳法
  • 3.3 良序原理
• 4. 递归定义
• 5. 自然数上的算术
  • 5.1 加法
  • 5.2 乘法
  • 5.3 序关系
• 6. 数系的扩张

1. Peano 公理

在数学的早期发展中，自然数被视为是不言而喻的存在。然而，随着 19 世纪数学严谨化运动的兴起，数学家们开始意识到，如果我们要建立一个坚实的数学大厦，就必须为最基础的自然数提供一套严格的公理化定义。

1889 年，意大利数学家朱塞佩·皮亚诺（Giuseppe Peano）在前人工作的基础上，提出了一组刻画自然数本质属性的公理系统。这套公理不再依赖于我们的直觉计数，而是通过后继运算将自然数串联成一个无限的序列。

定义 Peano 公理系统（Peano Axioms）是一个包含一个集合 $\mathbb{N}$（其元素称为自然数）、一个特定的元素 $0 \in \mathbb{N}$ 以及一个后继函数 $S: \mathbb{N} \to \mathbb{N}$ 的系统，满足以下五条公理：

1. $0 \in \mathbb{N}$。这确立了序列的起点。
2. 若 $n \in \mathbb{N}$，则 $S(n) \in \mathbb{N}$。这保证了自然数集合对后继运算是封闭的，即自然数序列可以无限向后延伸。
3. $\forall n \in \mathbb{N},\, S(n) \neq 0$。这意味着 $0$ 不是任何自然数的后继，即 $0$ 是序列中真正的第一个数。
4. $\forall m,\, n \in \mathbb{N},\, S(m) = S(n) \Rightarrow m = n$。这表明后继函数是一个单射函数，保证了序列不会在中间“分叉”或“重合”。
5. 归纳公理（Induction Axiom）：若 $M \subseteq \mathbb{N}$ 满足：
   • $0 \in M$；
   • 对任意 $n \in M$，都有 $S(n) \in M$； 那么 $M = \mathbb{N}$。

1.1 对公理的直觉解释

我们可以将自然数想象成一列无穷无尽的台阶。公理 1 说这里有第一级台阶（标记为 $0$）；公理 2 说每一级台阶后面紧跟着下一级台阶；公理 3 说没有任何一级台阶能走到 $0$ 的前面去；公理 4 保证了每一级台阶都只有一个唯一的“前辈”，这样我们就不会看到两级不同的台阶通向同一级台阶。

最关键的是公理 5。它告诉我们，自然数集合 $\mathbb{N}$ 恰好是由 $0$ 及其所有的后继构成的，没有“多余”的东西。如果没有公理 5，我们可能会在 $\mathbb{N}$ 中混入一些奇怪的元素，它们虽然满足前四条公理，但却无法通过从 $0$ 开始不停地取后继来达到。

2. 自然数的集合论构造

虽然 Peano 公理完美地描述了自然数的性质，但它并没有告诉我们自然数到底“是什么”。在纯粹的集合论框架内，我们希望用集合本身来构造出满足这些公理的对象。

2.1 Von Neumann 构造

约翰·冯·诺依曼（John von Neumann）提出了一种极具美感的构造方式：用集合的嵌套深度来表示数值。

定义 Von Neumann 序数（Von Neumann Ordinals）构造法将自然数定义为：

• $0 = \emptyset$
• $1 = \{0\} = \{\emptyset\}$
• $2 = \{0,\, 1\} = \{\emptyset,\, \{\emptyset\}\}$
• $3 = \{0,\, 1,\, 2\} = \{\emptyset,\, \{\emptyset\},\, \{\emptyset,\, \{\emptyset\}\}\}$
• 一般地，$n = \{0,\, 1,\, 2,\, \dots,\, n-1\}$

在这种构造下，每一个自然数 $n$ 都是一个包含了所有比它小的自然数的集合。

定义 后继（Successor）运算在集合论中定义为：

$$S(n) = n \cup \{n\}$$

例 2.1 计算 $S(1)$： 根据定义，$S(1) = 1 \cup \{1\}$。因为 $1 = \{0\}$，所以 $S(1) = \{0\} \cup \{1\} = \{0,\, 1\} = 2$。

这种构造的优美之处在于，它将算术大小关系转化为了集合包含关系：

• $n \in m$ 等价于 $n < m$。
• $n \subseteq m$ 等价于 $n \leqslant m$。
• 自然数 $n$ 作为集合，其基数刚好等于 $n$，即 $|n| = n$。

2.2 无穷公理的作用

我们虽然知道了如何构造每一个单独的自然数，但如何保证所有这些自然数可以放在一起组成一个集合呢？

在 ZFC 集合论中，我们专门引入了无穷公理（Axiom of Infinity）来解决这个问题。该公理断言存在一个包含 $\emptyset$ 且对后继运算封闭的集合。

定义 归纳集（Inductive Set）是一个集合 $A$，满足：

• $\emptyset \in A$；
• $\forall x \in A,\, S(x) \in A$。

显然，如果我们想要一个包含所有自然数的集合，它必须是一个归纳集。然而，归纳集可能很大，包含了除了自然数以外的其他元素。因此，我们将自然数集合 $\mathbb{N}$ 定义为所有归纳集的交集。由于所有归纳集的交集仍然是归纳集（请读者尝试证明），且它是最小的归纳集，它完美地符合了 Peano 第五公理的要求。

3. 数学归纳法

数学归纳法是我们证明关于自然数命题的最强力武器。

3.1 第一归纳法

@theorem-1 数学归纳法原理（Principle of Mathematical Induction）：设 $P(n)$ 是关于自然数 $n$ 的命题。若满足：

1. 奠基步：$P(0)$ 成立；
2. 归纳步：对任意 $n \in \mathbb{N}$，$P(n) \Rightarrow P(n+1)$ 成立； 那么对所有 $n \in \mathbb{N}$，$P(n)$ 都成立。

证明：定义集合 $M = \{n \in \mathbb{N} \mid P(n) \text{ 成立}\}$。 根据前提 1，$0 \in M$。 根据前提 2，若 $n \in M$，则 $n+1 \in M$（即 $S(n) \in M$）。 由 Peano 第五公理（归纳公理），$M = \mathbb{N}$。 这意味着对所有 $n \in \mathbb{N}$，$P(n)$ 均成立。

TIP

归纳法就像推骨牌：第一块倒下（奠基），且如果第 $n$ 块倒下能带动第 $n+1$ 块（归纳），那么整排骨牌都会倒下。

例 3.1 证明对所有 $n \geqslant 1$，有 $\sum_{k=1}^n k = \frac{n(n+1)}{2}$。 证明：

1. 奠基：当 $n = 1$ 时，左边为 $1$，右边为 $\frac{1 \cdot (1+1)}{2} = 1$，成立。
2. 归纳：假设 $n=k$ 时成立，即 $\sum_{j=1}^k j = \frac{k(k+1)}{2}$。 那么当 $n = k+1$ 时：

$$\sum_{j=1}^{k+1} j = \left( \sum_{j=1}^k j \right) + (k+1) = \frac{k(k+1)}{2} + (k+1) = (k+1) \left( \frac{k}{2} + 1 \right) = \frac{(k+1)(k+2)}{2}$$

命题对 $n=k+1$ 也成立。 根据数学归纳法，命题对所有正整数均成立。

例 3.2 证明 $2^n > n$ 对所有 $n \geqslant 0$ 成立。 证明：

1. $n=0$：$2^0 = 1 > 0$，成立。
2. 假设 $2^k > k$。则 $2^{k+1} = 2 \cdot 2^k > 2k$。 当 $k \geqslant 1$ 时，$2k = k+k \geqslant k+1$。 当 $k=0$ 时，$2^1 = 2 > 1$。 因此对所有情况，$2^{k+1} > k+1$。

3.2 强归纳法

有时候，仅仅假设 $P(n)$ 成立并不足以推导出 $P(n+1)$，我们需要更强的假设。

@theorem-2 强归纳法（Strong/Complete Induction）：若对任意 $n \in \mathbb{N}$，命题“$\forall k < n,\, P(k)$ 成立”蕴含 $P(n)$ 成立，则对所有 $n \in \mathbb{N}$，$P(n)$ 成立。

证明思路：定义新命题 $Q(n) \equiv \forall k \leqslant n,\, P(k)$。对 $Q(n)$ 使用第一归纳法即可证明强归纳法的有效性。

例 3.3 证明算术基本定理（存在性部分）：每个大于 1 的自然数都可以表示为素数的乘积。 证明：设 $n > 1$。

1. 若 $n=2$，$2$ 本身是素数，成立。
2. 假设对所有 $2 \leqslant k < n$ 的数都成立。 对于 $n$：

• 若 $n$ 是素数，结论成立。
• 若 $n$ 是合数，则 $n = a \cdot b$，其中 $1 < a,\, b < n$。根据归纳假设，$a$ 和 $b$ 都可以分解为素数之积，因此 $n$ 也可以。

3.3 良序原理

良序性是自然数集合最深刻的性质之一。

@theorem-3 良序原理（Well-Ordering Principle）：$\mathbb{N}$ 的每一个非空子集都存在一个最小元素。

证明思路：可以使用归纳法证明其等价性。假设 $\mathbb{N}$ 的子集 $A$ 没有最小元，我们可以用强归纳法证明对任意 $n$，$n \notin A$，从而 $A = \emptyset$。这说明若 $A \neq \emptyset$，则必有最小元。

4. 递归定义

我们经常通过“前面项的值”来定义“当前项的值”，这种方法称为递归定义。但这种定义是否真的能确定一个函数呢？

@theorem-4 递归定理（Recursion Theorem）：给定集合 $A$ 中的一个元素 $a \in A$ 以及一个映射 $h: A \to A$，存在唯一的函数 $f: \mathbb{N} \to A$ 满足：

• $f(0) = a$
• $f(S(n)) = h(f(n))$ 对所有 $n \in \mathbb{N}$ 成立。

递归定义的合理性：递归定理保证了这种“一步接一步”的定义方式能够产生一个良定义的全局函数。在集合论中，这种函数的存在性是通过构造符合要求的有序对集合（即关系的子集）并利用归纳法证明其唯一性和全定义性来完成的。

例 4.1 阶乘函数的递归定义：

• $0! = 1$
• $(n+1)! = (n+1) \cdot n!$ 这里 $a = 1$，$h(x, n) = (n+1) \cdot x$（这是递归定理的一个稍微泛化的版本，其中 $h$ 可以依赖于 $n$）。

例 4.2 Fibonacci 数列：

• $F_0 = 0,\, F_1 = 1$
• $F_{n+2} = F_{n+1} + F_n$ 这被称为二阶递归，同样可以通过递归定理的推广来保证其存在唯一性。

5. 自然数上的算术

有了递归定义，我们就可以严谨地定义加法和乘法了。

5.1 加法

定义 加法（Addition）通过对第二个加数进行递归定义：

1. $m + 0 = m$
2. $m + S(n) = S(m + n)$

利用这个定义和归纳法，我们可以证明算术运算的所有性质。

定理：加法交换律 $m + n = n + m$。 证明： 首先我们需要证明两个引理：

• 引理 1：$0 + n = n$。对 $n$ 归纳可证。
• 引理 2：$S(m) + n = S(m + n)$。对 $n$ 归纳：
  • 当 $n=0$ 时，$S(m) + 0 = S(m) = S(m + 0)$，成立。
  • 假设 $S(m) + k = S(m + k)$，则 $S(m) + S(k) = S(S(m) + k) = S(S(m + k)) = S(m + S(k))$，成立。

现在证明交换律：对 $n$ 归纳。

1. $n = 0$：$m + 0 = m$，而 $0 + m = m$（引理 1），成立。
2. 假设 $m + k = k + m$。 则 $m + S(k) = S(m + k) = S(k + m) = S(k) + m$（最后一步用了引理 2）。 归纳完成。

5.2 乘法

定义 乘法（Multiplication）同样采用递归定义：

1. $m \cdot 0 = 0$
2. $m \cdot S(n) = m \cdot n + m$

在这个基础上，我们可以进一步证明：

• 结合律：$(m \cdot n) \cdot p = m \cdot (n \cdot p)$
• 分配律：$m \cdot (n + p) = m \cdot n + m \cdot p$
• 交换律：$m \cdot n = n \cdot m$

这些证明思路与加法类似，都是固定一个变量，对另一个变量进行归纳。

5.3 序关系

自然数的序关系可以通过算术运算定义： 定义 小于等于（Less than or equal to）：

$$m \leqslant n \Leftrightarrow \exists k \in \mathbb{N},\, m + k = n$$

在 Von Neumann 构造下，这个定义等价于集合包含关系 $m \subseteq n$。 我们可以证明 $(\mathbb{N},\, \leqslant)$ 是一个全序集（Total Ordered Set），即对于任意两个自然数 $m$ 和 $n$，必有 $m \leqslant n$ 或 $n \leqslant m$。

6. 数系的扩张

虽然自然数对于计数来说已经足够，但在处理减法（如 $3-5$）或除法（如 $1/2$）时就会遇到困难。集合论为我们提供了一套标准流程，将自然数逐步扩张。

1. 从 $\mathbb{N}$ 到 $\mathbb{Z}$： 我们定义整数为自然数对的等价类。直观上，有序对 $(a,\, b)$ 代表差 $a - b$。由于不同的对可能代表相同的差（如 $(5,\, 3)$ 和 $(6,\, 4)$），我们定义等价关系：

   $$(a,\, b) \sim (c,\, d) \Leftrightarrow a + d = b + c$$

   得到的商集即为整数集 $\mathbb{Z}$。

2. 从 $\mathbb{Z}$ 到 $\mathbb{Q}$： 类似地，有理数被定义为整数对 $(a,\, b)$（其中 $b \neq 0$）构成的等价类，代表商 $a/b$：

   $$(a,\, b) \sim (c,\, d) \Leftrightarrow a \cdot d = b \cdot c$$

3. 从 $\mathbb{Q}$ 到 $\mathbb{R}$： 实数的构造更为精细，最著名的方法是 Dedekind 分割。我们将实数定义为有理数集的一个特定子集，这个子集代表了实数轴上的一个“截断点”。另一种方法是使用有理数柯西序列（Cauchy sequences）的等价类。

这些扩张证明了一个深刻的事实：整个现代数学的大厦——从微积分到复分析——最终都可以完全建立在集合论的基石之上。只要我们接受了集合论的公理，自然数、实数乃至更复杂的数学对象就都有了坚实的基础。