「数学归纳法」为什幺会对?






给定一个关于正整数 $${n}$$ 的叙述 $${P(n)}$$,数学归纳法用下面两个步骤证明 $${P(n)}$$ 对于所有正整数 $${n}$$ 都成立:

1、(归纳基础)证明 $$n=1$$ 时,$${P(1)}$$ 成立。
2、(归纳步骤)假设 $$n=k$$ 时 $${P(k)}$$ 成立,证明当 $$n=k+1$$ 时 $$P(k+1)$$ 成立。

在一般教科书里,有时会给出其他形式的数学归纳法。譬如,给定一个正整数 $$m$$,下面这种形式的数学归纳法,可以在两步内证明 $${P(n)}$$ 对于所有不小于 $$m$$ 的正整数 $$n$$ 都成立:

1’、(归纳基础)证明 $$n=m$$ 时,$${P(m)}$$ 成立。
2’、(归纳步骤)假设 $${n=k}\geq{m}$$ 时 $${P(k)}$$ 成立,证明当 $$n=k+1$$ 时 $${P(k+1)}$$ 成立。

还有一种方式称为「完全数学归纳法」,它的两个步骤如下:

1”、(归纳基础)证明 $${P(n)}$$ 成立。
2”、(归纳步骤)假设 $$n=k$$ 时,对于所有 $${0

如此也就证明了$${P(n)}$$ 对于所有正整数 $$n$$ 都成立。

各种形式的数学归纳法所以都对的理由,其实奠基于下面的这条原则,它陈述了一项关于正整数非常根本的性质:

(最小元素原则)1每一个非空的正整数集合,都拥有一个最小的元素。

我们用第一种数学归纳法为例,说明所谓奠基于以此原则的意义。我们先假设最小原则为真,再假设数学归纳法的归纳基础与归纳步骤都完成了,就应该会推导出 $${P(n)}$$ 对于所有正整数 $$n$$ 成立的结论。如若不然,令 $$A$$ 是所有使 $${P(n)}$$ 不成立的 $$n$$ 所构成的集合,那幺 $$A$$ 就是一个非空集合。根据最小元素原则,$$A$$ 有一个最小元素 $$a$$。这个元素 $$a$$ 不会是 $$1$$,因为归纳基础保证 $$1$$ 不属于 $$A$$。于是 $$a-1$$ 会是不属于 $$A$$ 的正整数,所以 $${P(a-1)}$$ 成立,再经由归纳步骤便推得 $${P(a)}$$ 成立,也就是说 $$a$$ 不属于 $$A$$,我们于是得到一个矛盾。另外两种数学归纳法也可类似地得到验证。

我们为什幺会接受最小元素原则呢?假设 $$A$$ 是任何一个由正整数构成的集合,它里面可能有无穷多个元素,也可能只有有限个元素。我们现在拿出一个元素 $$\chi_1$$,如果 $$\chi_1$$ 不是 $$A$$ 里最小的元素,那幺便可在 $$A$$ 里找到另一个元素 $$\chi_2$$,而且 $${\chi_2}<{\chi_1}$$。如果 $$\chi_2$$ 还不是 $$A$$ 里最小的元素,那幺又可以再找一个更小的元素 $$\chi_3$$。如此继续下去,势必要找到 $$A$$ 里最小的元素,否则 $$A$$ 里面就会包含无穷多个严格递减的元素。然而 $$A$$ 里比 $$\chi_1$$ 小的元素最多也只有 $${\chi_1}-1$$ 个,不可能包含无穷多个严格递减的元素,我们因而得到一个矛盾。

其实前面这一段说明里,也有数学归纳法的风味。如果要明显地运用数学归纳法,我们可以如下论证。令 $$A$$ 是一个非空的正整数集合,假设 $$A$$ 没有最小元素,我们準备用数学归纳法证明 $$A$$ 必须是空集合,因此就得到一个矛盾,所以所以可以结论 $$A$$ 必须拥有一个最小元素。因为没有明显的方式描述 $$A$$ 的元素,所以归纳的对象叙述 $${P(n)}$$ 的选择有些巧妙。我们令 $${P(n)}$$ 表示:「所有小于 $$n$$ 的正整数 $$m$$ 都不属于 $$A$$。」

归纳基础:因为没有任何正整数会小于 $$1$$,所以 $${P(1)}$$ 成立。

归纳步骤:依据归纳法假设,当 $$n=k$$ 时 $${P(k)}$$ 成立。

现在令 $$n=k+1$$,我们需要证明所有小于 $$k+1$$ 的正整数 $$m$$ 都不属于 $$A$$。我们可以分为两种情形来讨论。

第一种情形是 $$m

第二种情形是 $$m=k$$。因为比 $$k$$ 小的正整数已经都不属于 $$A$$了,如果 $$k$$ 属于 $$A$$,$$k$$ 变成 $$A$$ 里最小的元素,这与我们的假设 $$A$$ 没有最小元素矛盾,所以 $$k$$ 也不属于 $$A$$。

根据数学归纳法,已经证明了 $${P(n)}$$ 对于所有正整数 $$n$$ 都成立。那幺 $$A$$ 就必须是空集合了,否则如果正整数 $$\chi$$ 是 $$A$$ 的元素,但是因为 $${P(\chi+1)}$$ 成立,$$\chi$$ 又不能多于 $$A$$,就得到一个矛盾了。

总而言之,前面的讨论显示数学归纳法与最小元素原则在逻辑上是彼此可以互相推导的,也可以说力量相当。我们所以能接受它们,根本是人类对于数有一种原始的直观,不论我们尝试用什幺面貌相异的话来讲,最终在逻辑上还是等价的。


参考资料

上一篇: 下一篇:

为您推荐