第一数学归纳法 vs 第二数学归纳法 vs 良序定理

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

相关：

第一数学归纳法 vs 第二数学归纳法 vs 良序定

第二数学归纳法：硬币问题和堆垛游戏

第一数学归纳法：施塔特中心的地板砖

良序原理：算术基本定理的证明

From : Mathematics for Computer Science

译者：李秋豪

第二数学归纳法（Strong induction）看起来确实要比第一数学归纳法（ordinary induction）健壮一些——它可以假设更多的条件，或者说，第一数学归纳法像是第二数学归纳法的特例。所以你可能觉得没有使用第一数学归纳法的必要。

但是，第二数学归纳法并不比第一数学归纳法“强壮”，一个简单的小程序就能够将使用第一数学归纳法的证明转换为第二数学归纳法的证明——仅仅在归纳假设的时候使用一个更普遍的量词就可以了。当然，将它们区别开还是有利于证明的可读性的。对于良序原理来说，一个用归纳法证明的命题也可以用良序原理证明，反过来也成立。事实上，第一第二数学归纳法和良序原理反映的是相同的数学原理！（译者注：在前面几篇博文中所举的例子都可以换成第一、第二归纳法或者良序原理来证明）

那么，为什么还要将这三种本质相同的方法分开列出呢？原因是有时候归纳法会显得更清楚，因为它不需要利用矛盾来证明命题。同样的，由于归纳法使用了递归，它的证明输入数据规模会更小。关于该选择使用哪个方法并没有一个准则，有的时候唯一的方法就是分别写出证明然后做对比。另外，证明的时候都要记得在开头列出来证明所使用的方法。