数学归纳原理和最小数原理的等价性证明

1、数学归纳原理和最小数原理的等价性证明这两个原理都是自然数公理系统中最基本的原理，人们常常用最小数原理证明数学归纳原理。我发现用数学归纳原理也可以证最小数原理。所谓的最小数原理是指：自然数集合的任意非空子集必有最小元素。一：用数学归纳原理证最小数原理。 当自然数的非空子集只含一个元素时，这个元素就是最小元素。设n元集有最小元素，对于n+1元集，新加入的元素与n元集中的最小数比较，若新加入的元素不大于该最小数，则新加入的元素为最小数，否则，原来的n元集中的最小数仍是n+1元集的最小数。由数学归纳原理，含任意个自然数数目的自然数子集都有最小数。得证。二：用最小数原理证数学归纳原理：p(o)成立，且p

2、(n)成立可导出p(n+1)成立，则对于一切自然数n,p(n)成立。否则，若对于若干个（可能有限个，也可能无限个）自然数m1,mi(i1）使命题不成立，由最小数原理，这若干个自然数有最小数记为w，而且，w一定是正数，那么，就一定存在唯一的自然数b,b+1=w.b不属于这个使命题不成立的元素组成的集合，因为b比最小数还小。则p(b)是成立的，由规则，p(b+1)也成立即p(w)成立。矛盾。故对于一切自然数n,p(n)成立。证毕。其实以上发现也没啥大不了的，很直观浅显。这两个原理的等价性得证后，两者中的任意一条都可以作为皮亚杰五条公理中的一条吗？不行！因为最小数原理中的小于最开始还是没有定义的！。

3、还有，该等价关系非我第一次发现，由于其十分简单，在我发现等价性后，我在华罗庚的数学归纳法最后找到了同样的结论。归纳原理和数学归纳法1数学归纳法的理论依据归纳法和演绎法都是重要的数学方法归纳法中的完全归纳法和演绎法都是逻辑方法；不完全归纳法是非逻辑方法，只适用于数学发现思维，不适用数学严格证明数学归纳法既不是归纳法，也不是演绎法，是一种递归推理，其理论依据是下列佩亚诺公理中的归纳公理：存在一个自然数0N；每个自然数a有一个后继元素a，如果a是a的后继元素，则a叫做a的生成元素；自然数0无生成元素；如果a=b，则a=b；(归纳公理)自然数集N的每个子集合M，如果M含有0，并且含有M内每个元素的后继

4、元素，则MN自然数就是满足上述佩亚诺公理的集合N中的元素关于自然数的所有性质都是这些公理的直接推论由佩亚诺公理可知，0是自然数关于“后继”的起始元素，如果记01，1=2，2=3，n=n1，则N=0，1，2，n，由佩亚诺公理所定义的自然数与前面由集合所定义的自然数，在本质上是一致的90年代以前的中学数学教材中，将自然数的起始元素视作1，则自然数集即为正整数集现在已统一采取上面的记法，将0作为第一个自然数定理1(最小数原理)自然数集N的任一非空子集A都有最小数这本是自然数集N关于序关系()为良序集的定义现在用归纳公理来证明证 设M是不大于A中任何数的所有自然数的集合，即M=nnN且nm，对任意mA

5、由于A非空，至少有一自然数aA，而 a1(a)不在M中所然，就有 1 0M(0不大于任一自然数)；2 若mM，则m1M根据归纳公理，应有MN此与MN相矛盾这个自然数m0就是集合A的最小数因为对任何aA，都有m0意aA，于是m01M，这又与m0的选取相矛盾反之，利用最小数原理也可以证明归纳公理因此，最小数原理与归纳公理是等价的定理2(数学归纳法原理)一个与自然数相关的命题T(n)，如果1 T(n0)(n00)为真；2 假设T(n)(nn0)为真，则可以推出T(n1)也为真 那么，对所有大于等于n0的自然数n，命题T(n)为真 证 用反证法若命题T(n)不是对所有自然数n为真，则M=mmN，mn0

6、且T(m)不真非空根据定理1，M中有最小数m0由1， m0n0，从而m01n0且T(m0-1)为真由2，取n=m0-1即知T(m0)为真此与T(m0)不真相矛盾从而证明了定理2在具体运用数学归纳法进行数学证明时，有多种不同形式运用定理2中两个步骤进行证明的，为型数学归纳法经常使用的还有型数学归纳法，型数学归纳法是：如果命题T(n)满足1 对某一自然数n00，T(n0)为真；2 假设对n0kn的k， T(k)为真，则可以推出 T(n1)也真那么对所有大于等于n0的自然数，命题T(n)都真定理3 型数学归纳法和型数学归纳法等价证 假设命题 T(n)对n=n0为真，于是只须证明“由T(n)(nn0)

7、为真，可以推出T(n1)也为真”的充要条件为“由T(k)(n0kn)为真，可以推出T(n+1)也为真”1 充分性若“由T(n)(nn0)为真，可以推出 T(n1)也为真”，则对n0kn，T(k)为真，特别 T(n)为真，因此 T(n1)也为真2 必要性用反证法若“由 T(k)(n0kn)为真，可以推出 T(n1)也为真”，但并非对所有大于等于n0的自然数n，由T(n)为真，可以推出 T(n1)也为真，则 M=mmN， mn0且由T(n)为真推不出T(n1)也为真非空由定理1，M中有最小数m0，且对n0km0的k，由T(k)为真，可以推出T(k1)也为真特别由 T(n0)为真可知 T(n0+1)

8、为真，由T(n01)为真可知 T(n02)为真，由T(m01)为真可知 T(m0)为真现已知T(n0)为真，所以T(n0)， T(n0+1)， T(m0)都为真，由此可知 T(m01)也为真，所以由 T(m0)为真推出了T(m01)也为真这与m0的选取矛盾由定理3可知，型数学归纳法也是合理的推理方法2数学归纳法在应用中要注意的问题第一，证明的两个步骤缺一不可第一步是归纳的基础，第二步是归纳的传递尤其是不可忽视第一步的验证例1试证135(2n1)(n1)21证 假设当n=k时公式成立，则135(2n-1)(2n+1)135(2n-1)(2n1)n212n1(n1)21完成了数学归纳法的第二步，但

9、结论显然是错误的为什么？因为缺少第一步事实上，当n=0时，公式不成立如果缺了第二步，则不论对多少个自然数来验证命题T(n)的正确性，都不能肯定命题对所有自然数都正确例如，哥德巴赫猜想“任何不小于6的偶数都可以表成两个奇素数之和”，虽然对大量偶数进行了具体验证，但因缺少第二步归纳传递，所以仍只停留在归纳的第一步上它至今仍只是个猜想而已第二，第二步在证明T(n1)为真时，一定要用到归纳假设，即要把“T(n)为真推出 T(n1)为真”或“T(n0)， T(n01)，T(k-1)为真推出T(k)为真”的实质蕴含真正体现出来否则不是数学归纳法证明例2 设a1，an为n个正数，b1，bn是它的一个排列试证

10、证1当n=1时，命题显然成立2假设(*)式对n=k成立，则当n=k1时根据数学归纳法原理，(*)式对所有大于等于1的自然数n都成立这里虽然形式上完成了数学归纳法的两个步骤，但第二步在证(*)式对n1成立的过程中，并没用到(*)对n成立的归纳假设因此，不能说上述证法是采用了数学归纳法事实上，在上述证明中无须用数学归纳法，用平均值不等式证明就行了第三，并不是凡与自然数相关的命题T(n)，都要用数学归纳法来证明；而且也不是所有这类命题都能用数学归纳法给以证明的这一命题是与自然数相关的命题，尽管可以对n0，1，2，进行验证，但无法实现数学归纳法的第二步，因此不能用数学归纳法进行证明事实上，数学归纳法只

11、适用于具有递归性的命题T(n)3递归函数一个定义在自然数集N上的函数f(n)，如果它对于每个自然数n的值可以用如下方式确定：(1)f(0)=a(a为已知数)；(2)存在递推关系组S，当已知/f(0)，f(1)，f(n-1)值以后，由S唯一地确定出f(n)的值：f(n)=Sf(0)，f(1)，f(n-1)那么，就把这个函数f(n)，称作归纳定义的函数简称递归函数在具体的递归函数例子中，关系组S可能有几个表达式，或者没有明确的解析表达式，也可能需要给出f(n)的开头若干个值这样定义函数是合理的，因为我们有：定理4 当递推关系组S给定后，定义在N上的满足上述条件(1)、(2)的函数f(n)是存在而且

12、唯一的证 首先指出：对任一自然数k，总可以在片断0，k上定义一个函数fk(n)，使fk(0)=a，对于片断上其他自然数 n，f(n)=Sf(0)，f(n-1)这个函数fk(n)是在0，k上唯一确定的现对k进行归纳证明：1 当k0时，f0(0)a是唯一确定的；2假定在0，k上已经由(1)、(2)定义了一个唯一确定的函数fk(n)，令则fk+1(n)在片断0，k1上有定义，且(1)fk+1 (0)=fk(0)=a；(2)fk+1(n)=Sfk(0)，fk(n1) =Sfk+1(0)，fk+1(n1)， n=1，2，k因此，函数人fk+1(n)满足条件(1)、(2)由数学归纳法知，对任何自然数k，函

13、数fk(n)在片断0，k上唯一确定，且满足(1)、(2)又若k1k2，则 fk1(n)与fk2(n)在片断0，k1上完全一致现作一新的函数：f(n)=fn(n)， nN首先，函数f(n)对任一nN都有定义，且f(n)=fn(n)=Sfn1(0)，fn-1(n1)=Sf0(0)，fn-1(n-1)=Sf(0)，f(n-1)又显然f(0)f0(0)=a故函数f(n)是定义在N上且满足(1)、(2)的唯一确定的函数例4 设函数fNN，且(1) f(0)=2，f(1)=3；(2) f(n1)3f(n)2f(n1)，n1证明： f( n)2n1这里给出的递归函数由f(0)、f(1)两个值和一个关系式给定

14、的关系组S确定但有的递归函数f(0)的值隐含于关系组S之中而未直接给出例5(IMO19试题)设f：N+N，且(S) f(n1) f(f(n)， nN+求证：对于任意nN，f(n)n证 先用数学归纳法证明命题An：任意正整数n，若mn，则f(m) n显然 A1真假设An-1真，则对任意mn，f(m1)n-1，故f(m)f(f(m1)2n1，于是f(m)n，从而 An真由此可知，f(n)n，f(n1)f(f(n)f(n)于是f单调增加又如果有一个n使f(n)n，则f(n)n+1，f(f(n)f(n+1)，与已知条件(S)矛盾故只能有 f(n)=n本题给出的递归函数，f(1)的值没有明显给出，但实际

15、上隐含于关系组(S)中4递归命题一个与自然数相关的命题T(n)，一般来说，它未必是一个函数问题现在采取如下方式来构造命题T(n)的真值函数fN1，0 如果命题T(n)的真值函数f(n)是递归函数，即1 f(0)=1；2 f(n1)= Sf(0)，f(n)，且当f(0)=f(n)=1时， f( n1)=1那么就称T(n)是具有递归性质的命题，或简称递归命题实际上，所谓递归命题，就是一个与自然数相关的命题T(n)，开头(如n=0时)为真，且真值可传递并不是所有与自然数相关的命题都是递归命题例如本节例3中的命题是与自然数相关的命题，而且对任何nN，它都为真，但却不具有递归性，它的真值是不可传递的一般

16、而言，大多数数论问题，如哥德巴赫猜想、费马问题、孪生素数问题等，都不是递归命题只有递归命题才能用数学归纳法来证明因此判别一个与自然数相关的命题T(n)是不是递归命题，是运用数学归纳法的前提判别的关键在于，探究和发现T(n)的真值对于T(0)，T(n-1)真值的依赖性而这种探究本身对于数学归纳法第二步证明，也有直接帮助例6(1963年北京市竞赛题)2n(nN)个球分成若干堆，从中任选两堆：甲堆p个球，乙堆q个球；若pq，则从甲堆取出q个加于乙堆；这作为一次挪动(变换)证明：总可以经过有限次挪动，使所有球都归为一堆这是一个与自然数相关的命题，记为T(n)当n=1时，只有两个球，或已是一堆；或两堆，每堆一个球若后者，只须挪动一次，就变为一堆所以T(1)为真T(n)真值是否有传递性