Zmn-1099 薛问天: 数学归纳法以及强归纳法原理和向后归纳原理的证明。评一阳生先生的《1096》

【编者按。下面是薛问天先生的文章，是对一阳生先生的《Zmn-1096》一文的评论。现在发布如下，供网友们共享。请大家关注并积极评论。另外本《专栏》重申，这里纯属学术讨论，所有发布的各种意见仅代表作者本人，不代表本《专栏》编辑部的意见。《专栏》中有些文章发扬了啄木鸟精神，对一些错误的观点和言论进行了说理的批评。但请大家注意，也有些有严重错误的文章在这里发布，就是为了引起和得到广大网友们的评论。不要以为在这里发布的文章都是正确无误的。】

数学归纳法以及强归纳法原理和向后归纳原理

的证明。评一阳生先生的《1096》

薛问天

xuewentian2006@sina.cn

一阳生先生提出的数学归纳法，可用皮亚诺自然数公理的第五公理来证明。强归纳法原理和向后归纳原理，除可用第五公理来证明外，还可用数学归纳法来证明。

这个皮亚诺自然数公理的第五公理的内容是: 任何自然数都可由0经有穷次的后继(加1)运算而得到。即任何自然数n都是由对0进行n次加1得到的数。当然数学归纳法也可作自然数公理的第五公理。因为它们可以相互推出，是等价的。

一，数学归纳法的证明。

定理(数学归纳法)。设P是关于自然数的一个性质。如果P(0)是真的，而且对任何自然数k，能由P(k)是真的，推出P(k‘)也是真的。那么性质P对于所有的自然数n，P(n)都是真的。即（P(0) ∧ ∀k∈N（P(k) ⇒ P(k’)））⇒ ∀n∈N P(n)。其中N是自然数集，n′=n+1是自然数的后继运算。

证明。如果P(0)是真的，而且∀k∈N（P(k) ⇒ P(k’)）。显然可推出 P(0)是真的，

由P(0)→P(1)，可推出P(1)是真的，

由P(1)→P(2)，可推出P(2)是真的，

......

由P(n-1)→P(n)，可推出P(n)是真的。

也就是说，根据皮亚诺自然数公理的第五公理，任何自然数n都是对0进行n次加1得到的数。对于由0经n(有穷)次加1得到的自然数n，可以通过n次(有穷次)的推理，证明P(n)是真的。

于是得出结论，对任何自然数n，都可证明P(n)为真。证毕。

我们知道，在逻辑上是有要求的，推理必须在有穷步的推理中完成，不允许使用无穷步的推理。从以上证明可以看出，我们的证明完全遵守了这项规定。对任何自然数n，都可在有穷步的推理中证明P(n)为真。

我们来看一阳生先生的理解和证明，他没有根据公理五，所以表现为根据不足，另一方面没有强调推理步骤的有穷性，如说【证明了P(0)为真，即证明了P(1), P(2), P(3)等全体与P(0)共同为真、都为真，共同的具有性质P。】这在逻辑推理上是不严谨的。另外，没有必要分什么第一种第二种，有些多此一举。

二，强归纳法原理的证明。

定理（强归纳法原理）。设m₀是一个自然数，而P(m)是一个依赖于任意自然数m的性质。如果对于每个m ≥ m₀，都有下属蕴含关系：【如果P(m’)对于一切满足m₀ ≤ m’ < m的自然数m’都成立，那么P(m)也成立，】那么我们可以断定对于所有自然数m ≥ m₀， 对于一切满足m₀ ≤ m’ < m的自然数m’，P(m’)都成立，从而P(m)也成立。

如果我们做这样的定义：定义Q(n)：“P(m)对于一切m₀ ≤ m < n成立”，此定理可写为:

定理（强归纳法原理）。设m₀是一个自然数，而P(m)是一个依赖于任意自然数m的性质。如果对于每个m ≥ m₀，都有下属蕴含关系：【如果Q(m)成立，则P(m)也成立，】那么我们可以断定对于所有自然数m ≥ m₀， Q(m)成立，从而P(m)也成立。

亦即对所有自然数m，如果m ≥ m₀，都满足此蕴含关系Q(m)→P(m)，则可断定对所有m ≥ m₀，Q(m)和P(m)，都成立。

证明1(用第五公理证)。对任何自然数m，如果m<m0，因m≥m0为假，所以可以不考虑。因而只考虑m≥m0的情况。

我们先证明Q(m0)和P(m0)成立。

可先证如下的事实。设命题A是:【对任何b，b∈B→C(b)】，当B是空集时，命题A为真。理由是，当B是空集时，b∈B为假。而一个蕴涵式命题中，如果前提b∈B为假，无论结论C(b)真假如何，则都有蕴涵式的命题b∈B→C(b)为真。

所以在m=m0时，蕴含关系是：Q(m0)→P(m0)，【如果P(m’)对于一切满足m₀ ≤ m’ < m0的自然数m’都成立，那么P(m0)也成立，】m′是空集，此Q(m0)为真所以可证P(m0)也成立为真。

上述论证证明了在这个蕴含关系成立的假设下，断定Q(m0)和P(m0)成立。

现在我们证明在这个假设下，Q(m)和P(m)对于一切自然数m > m₀都成立。根据第五公理，任何自然数m都是由对0进行m次加1得到的数。所以存在k>0使m=m0+k。从而证明对于一切自然数m > m₀，Q(m)和P(m)都成立，就是证明对任何k>0，使Q(m0+k)和P(m0+k)成立。

下面可以接着证明在这个蕴含关系成立的假设下，断定P(m0+1)成立。

很简单。因为P(m0)为真，所有满足m₀ ≤ m’ < m0+1的自然数m’,就只有m0这一个数。所以对于一切满足m₀ ≤ m’ < m的自然数m’，P(m′)都成立。根据假设的蕴含关系，就断定P(m0+1)成立。

同理可根据P(m0)和p(m0+1)为真，证明P(m0+2)为真。以此类推，可证对任何k，都可推出: P(m0),P(m0+1),...,P(m0+k-1)为真，

因为m=m0+k，此即Q(m)为真，这也就推出了P(m)为真。定理证毕。

证明2(用数学归纳法证)。我们来证明对所有自然数m，如果m ≥ m₀，都满足此蕴含关系Q(m)→P(m)，则可断定此蕴含关系的前提Q(m)和结论P(m)都成立。

基始，证明m=0时成立。显然如果m≥m0，此时必有m=m0=0，前面己证Q(m0)和P(m0)成立，所以Q(0)和P(0)成立。

归纳，证明如果m=n时成立，则m=n+1时成立。

假定m=n时成立，即如果n ≥ m₀，都可根据满足此蕴含关系Q(n)→P(n)，断定Q(n)，即对于一切满足m₀ ≤ m’ < n的自然数m’，P(m’)都成立，而且P(n)也成立。可以看出，这就是对于一切满足m₀ ≤ m’ < n+1的自然数m’，P(m’)都成立，即Q(n+1)成立。从而根据蕴含关系得出P(n+1)也成立。这正是我们要证明的m=n+1要求的结果。

我己证明了m=0时定理成立，又证明了如果m=n时定理成立，则m=n+1时定理也成立。那么根据数学归纳法就证明了对于所有自然数m，定理成立。证毕。

一阳生的理解中对假设中的蕴含关系理解得不对。蕴含关系是：【如果P(m’)对于一切满足m₀ ≤ m’ < m的自然数m’都成立，那么P(m)也成立，】其中有【那么P(m)也成立】这个结论。一阳生先生忽視了这个。

接着先生说【证明强归纳原理，只须证明蕴含关系成立即可。】就没说清证明的是哪个蕴含关系。我括起来的这个是假设的不是要证明的。要证明的是在这个假设下，断定蕴含关系的前提和结论对于一切自然数m ≥ m₀都成立。

当然首先要证明在这个假设下，断定P(m0)成立。先生说【m = m₀时，m’不存在，P(m’)无定义，蕴含关系前提为假，结论P(m)成立与否无法确定，】当然不对。

实际上一阳生先生并未对此定理做出证明。可能对定理的理解上就存在问题。

三，向后归纳原理的证明。

定理(向后归纳原理)。设P(m)是一个依赖于自然数的性质，它满足条件：对于任何自然数m，只要P(m+1)成立则p(m)也成立。设n是任意自然数，且假设P(n)成立，证明对于一切自然数m ≤ n，P(m)都成立。

证明1(用第五公理证)。假设n是任意一个自然数，P(n)成立。因为对于任何自然数m，只要P(m+1)成立则p(m)也成立。所以利用一次推理，可推出P(n-1)成立，再利用同样的一次推理，可推出P(n-2)成立，余此类推，......。根据第五公理，此n可以由0经有穷次的加1运算而得到。所以经有穷次推理，即可推出

P(n)，P(n-1)，...， P(2)，P(1)，P(0)成立。此即我们要证明的对于一切自然数m ≤ n，P(m)都成立。证毕。

证明2(用数学归纳法证)。当n=0时，假设P(0)成立，由于m≤0的m只有0一个数，而且P(0)成立，所以对于一切自然数m ≤ n，P(m)都成立。定理成立。

现在假设定理对于n成立，从而当P(n)成立时，对于一切自然数m ≤ n，P(m)都成立。显然如果此时假设对于n+1，有P(n+1)成立，就可推出P(n)成立。这就有对于一切自然数m ≤ n+1，P(m)都成立。这就是我们要证明的定理对于n+1成立。

既然我们证明了定理对于n=0时成立，又证明了如果定理对于n时成立，则对于n+1也成立。那么根据数学归纳法，我们就证明了定理对所有自然数都成立。证毕。

我们来看一阳生先生的证明。他对m施行归纳证明，其实是不必的。对任何n，小于n的m都是有穷的。可实施有穷步推理。关键是要证明定理是对所有的自然数n都成立，要对n实施数学归纳法。注意数学归纳法的结论是对所有自然数都成立。关于这点原题已有提示【对变元n用归纳法】。一阳生先生可能没有完全理解。

【编者注。读者可点击頁面最上面的〖博文〗这个选項，来查找本《专栏》的其它文章。】