4.3 归纳定义和归纳证明

4.3.1 数学归纳法与良序原理

第一数学归纳法

• 目标：证明命题 $\forall n P(n)$
• 归纳基：$P(0)$ 成立
• 归纳步：$\forall k (P(k) \to P(k + 1))$ 成立

第二数学归纳法

• 目标：证明命题 $\forall n \ge c (P(n))$
• 归纳基：逐一验证 $P(c), P(c+1), \cdots, P(c + j)$ 成立
• 归纳步：假定 $P(c), P(c+1), \cdots, P(k)$ 成立，证明 $P(k +1)$ 成立

*良序原理

良序原理：自然数集的任意非空子集都存在最小自然数。

良序原理说明数学归纳法有效性：记 $S = {n \in \mathbb N \mid n \ge c \land \lnot P(n)}$，如果它是非空子集，那么一定有最小值 $m = \min S$，而 $P(m - 1)$ 是成立的，且 $P(m - 1) \to P(m)$ 成立，故 $P(m)$ 成立，矛盾。故 $S$ 是空集。

4.3.2 归纳定义和结构归纳法

集合的归纳定义：

• 归纳基：给出集合的一些基本元素
• 归纳步：给出从集合中的一些元素构造另外一个元素的规则
• 最小化声明

归纳定义集合元素的构造树：

• 根是要构造的元素
• 每个节点的儿子是用某个规则构造出该节点的所有元素
• 叶子结点是基本元素

结构归纳证明集合的元素存在某些性质 $\forall x \in A P (x)$：

• 归纳基：集合的基本元素 $P(a)$
• 归纳步：对于每种规则，用 $a_1, a_2, \cdots, a_n$ 推出 $a$，则需要证明在 $P(a_1), P(a_2), \cdots, P(a_n)$ 的情况下，$P(a)$ 也为真。