博文

Zmn-0875 thebeater: 科普一下数学归纳法

已有 1203 次阅读 2022-8-15 09:46 |个人分类:数学啄木鸟|系统分类:论文交流

Zmn-0875 thebeater: 科普一下数学归纳法

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

科普一下数学归纳法

thebeater

首先固定一下记号。记N是自然数集，s: N->N+是映射s(x)=x+1，N+是正的自然数。

我们从数学归纳法的角度出发，证明如下命题：s是N到N+的双射。换句话说，s是定义良好的单射，并且每个正自然数y都存在自然数x使得y=x+1。

这个命题看起来非常显然，但是李鸿仪在0870的评论[26]中认为这是不对的，薛问天先生已经在0873给出了一个很简短的证明。但是我们这里希望通过最底层的自然数理论，也就是公理化的方法，证明这一个命题。

一、 Peano公理和数学归纳法
公理化方法是现今数学常用的办法。假如我们想研究自然数的问题，比如素数的性质等等，其实没必要回归到这样底层的公理，因为大多数人对自然数是什么这一问题持相同看法。但是，如果偶尔有人觉得自然数的底层问题不够清楚，那最好的方法就是回归到最底层的公理，这些是一切关于自然数的命题的出发点。
自然数的公理化并不唯一，不同的公理化给出的都是等价的。现今常用的是Peano的公理系统，即如下的五条公理：
1、0是自然数
2、每一个确定的自然数a，都有一个确定的后继a’，a’也是自然数
3、对于每个自然数b、c，b=c当且仅当b的后继数=c的后继数
4、0不是任何自然数的后继数
5、任意关于自然数的命题，如果证明：它对自然数0是真的，且假定它对自然数a为真时，可以证明对a' 也真。那么，命题对所有自然数都真。

前四条是关于后继运算的，也就是开头的s，一些很基本的性质。第五条通常被称为数学归纳法，是非常有用的一个证明方法。这个方法可以比喻成多米诺骨牌，如果第一块骨牌被推倒了，并且每一块骨牌都可以推倒下一个骨牌，那么每一块骨牌都会被推倒。
数学归纳法可能很多人都听过，但是可能确实有人对此不太熟悉，所以借这个机会通过下面具体的证明科普一下。

二、数学归纳法证明s是双射
前四条公理已经给出了s的很多性质了。第二条表明，后继映射s可以定义在每个自然数上。第三条表明，后继映射是单射。但是，前四条并不能得出，每个非零自然数都是另一个自然数的后继，这里必须使用数学归纳法。我们把证明简单写一下：
首先，我们要考虑的关于自然数a的命题是：要么a是0，要么a是某个自然数的后继。这个命题记为P。
第一步，P对0成立。因为0是0，这是不证自明的。
第二步，要证明如果P对a成立，那么P对a的后继a’成立。此时， a’是a的后继，并且根据公理4，a’不是0。所以命题P对a’成立。
结合以上两步和公理5，我们就证明了所需的命题。
事实上，如果没有数学归纳法，这个命题未必是对的。比如，加入自然数上的后继运算是x->x+100，那么这个运算满足前四条公理，但是不满足第五条，并且确实1不是任何自然数+100。

三、其他的证明方法
Peano公理仅仅利用了后继这一运算就给出了公理，但是实际上自然数上还有很多我们熟悉的运算，比如四则运算，比如大小关系。这些结构都可以用Peano公理定义出来，在此不一一赘述。如果我们熟悉这些运算的话，可以给出原命题的更简单的证明。
1、利用减法。因为所有正自然数y都满足y-1也是自然数，所以y=(y-1)+1就完成了证明
2、利用自然数的序关系两个事实：任何非空自然数集都有最小元，和小于某个给定自然数的自然数只有有限多个。假设存在正自然数y不是任何自然数+1得到的，那么我们考虑所有这样的y中最小的那一个，记为y0. 那么小于y0的自然数只有有限个，所以可以找一个最大的，记为x0. 那么x0+1=y0，这就导出了矛盾。

四、对李鸿仪的评论
从以上的过程中可以看出，既然李鸿仪不懂这个命题，那么只有一种可能，他的“自然数”和我们通常理解的自然数不一样。他的“自然数”不满足Peano公理，具体来说，他的“自然数”：
1、不满足数学归纳法
2、没有减法
3、任何非空自然数集都有最小元，和小于某个给定自然数的自然数只有有限多个，二者至少有一个不成立
我并不介意讨论一个新生的理论，只要你不犯任何逻辑错误，并且这个理论确实可以帮助我们解决或者理解某个数学问题。但是，我觉得你不应该把你的结论和现有的我们熟悉的结论混为一谈，尤其是术语上不要有重复。正如本文所分析的，你的“自然数”和通常的自然数是不同的，满足的公理都不一样。除此之外，“映射”、“集合”、“双射”、“奇数偶数”等等概念也都与通常理解的不同。这个不同不仅仅体现在表面的结论上，更体现在深层次的公理上。你必须有一套从你的最初的公理出发，到你的后续结论的完整证明，否则当你说“自然数”的时候，我们的理解就是那个满足Peano公理的自然数，从而得出结论，你是错的。

五、附录，李鸿仪的逻辑错误
正如前面所说，只要不犯逻辑错误就没问题，但是犯了逻辑错误就要指出来。鉴于李鸿仪到现在为止只给出过这么一个完整的证明（定理1），我也只能从这里面挑了。这里错误其实很明显，我在0870里已经指出来了。鉴于他没看，所以我只能再具体写一下。先是他号称的定理1：若A与B之间存在双射，且A=A1UA2，B=B1UB2，这时，若A1与B1之间存在双射，则A2与B2之间必然存在双射; 同理，若A2与B2之间存在双射，则A1与B1之间必然存在双射。
及其证明：双射必须发生在A和B全部元素之间，所以部分元素之间是否有双射都必须考虑。如果A2和B2之间不存在双射，即A2(或B2)中有部分元素在B2(或A2)中没有原像，则由于A1与B1已经双射，所以这部分元素在B1(或A1)中也不可能有原像，即这部分元素在B(或A)中没有原像，由于这部分元素属于A(或B)，在B或A)中又没有原像，所以A与B之间不存在双射。证毕
我们省去一些推理过程，整理一下他的逻辑链。首先设A与B之间存在双射f:A->B。然后（不妨设）B2中有元素x在A2中没有关于f的原像。也就是不管怎么说，他找出了B2中的一个比较特殊的元素x。然后他就说（我把映射补出来了）：“由于A1与B1之间存在双射g，所以x在A1中也不可能有关于f的原像”。
然而真的是这样吗？他的这句推理其实使用了如下引理：
引理1 记号同前。设f:A->B是双射，并且g:A1->B1是双射。那么任何B2中的、在A2中没有关于f的原像的元素x，在A1中也没有关于f的原像。
注意这里f与g并没有什么关系。然而，这个引理1有反例，有限集就可以做到。假设A={a1, a2}，B={b1, b2}，A1={a1}，A2={a2}，B1={b1}，B2={b2}。假设f:A->B是f(a1)=b2, f(a2)=b1，此时B2中有元素x=b2在A2中没有关于f的原像，并且A1与B1之间确实存在双射g:A1->B1，g(a1)=b1，但是x=b2在A1中确实有关于f的原像。
当然了，如果引理1中f和g是有关的，具体来说，如果f在A1上的限制就是g，那么确实这个引理是对的。并且此时定理1也是成立的，也就是如下的定理：
定理1’ 若A与B之间存在双射f，且A=A1UA2，B=B1UB2，这时，若f是A1与B1之间的双射，则f也是A2与B2之间的双射。
当然了，定理1’是极其显然的，我不觉得有任何必要把他单独列出来称为一个定理。也许你得定理1，在你的公理系统里面是对的，但是至少现在的证明是错的。

返转到

zmn-000文清慧：发扬啄木鸟精神-《数学啄木鸟专栏》开场白及目录