您好,欢迎访问三七文档
当前位置:首页 > 机械/制造/汽车 > 机械/模具设计 > 数学归纳原理和最小数原理的等价性证明
数学归纳原理和最小数原理的等价性证明这两个原理都是自然数公理系统中最基本的原理,人们常常用最小数原理证明数学归纳原理。我发现用数学归纳原理也可以证最小数原理。所谓的最小数原理是指:自然数集合的任意非空子集必有最小元素。一:用数学归纳原理证最小数原理。当自然数的非空子集只含一个元素时,这个元素就是最小元素。设n元集有最小元素,对于n+1元集,新加入的元素与n元集中的最小数比较,若新加入的元素不大于该最小数,则新加入的元素为最小数,否则,原来的n元集中的最小数仍是n+1元集的最小数。由数学归纳原理,含任意个自然数数目的自然数子集都有最小数。得证。二:用最小数原理证数学归纳原理:p(o)成立,且p(n)成立可导出p(n+1)成立,则对于一切自然数n,p(n)成立。否则,若对于若干个(可能有限个,也可能无限个)自然数m1,……mi……(i≥1)使命题不成立,由最小数原理,这若干个自然数有最小数记为w,而且,w一定是正数,那么,就一定存在唯一的自然数b,b+1=w.b不属于这个使命题不成立的元素组成的集合,因为b比最小数还小。则p(b)是成立的,由规则,p(b+1)也成立即p(w)成立。矛盾。故对于一切自然数n,p(n)成立。证毕。其实以上发现也没啥大不了的,很直观浅显。这两个原理的等价性得证后,两者中的任意一条都可以作为皮亚杰五条公理中的一条吗?不行!因为最小数原理中的小于最开始还是没有定义的!。还有,该等价关系非我第一次发现,由于其十分简单,在我发现等价性后,我在华罗庚的《数学归纳法》最后找到了同样的结论。归纳原理和数学归纳法1.数学归纳法的理论依据归纳法和演绎法都是重要的数学方法.归纳法中的完全归纳法和演绎法都是逻辑方法;不完全归纳法是非逻辑方法,只适用于数学发现思维,不适用数学严格证明.数学归纳法既不是归纳法,也不是演绎法,是一种递归推理,其理论依据是下列佩亚诺公理Ⅰ—Ⅴ中的归纳公理:Ⅰ.存在一个自然数0∈N;Ⅱ.每个自然数a有一个后继元素a′,如果a′是a的后继元素,则a叫做a′的生成元素;Ⅲ.自然数0无生成元素;Ⅳ.如果a′=b′,则a=b;Ⅴ.(归纳公理)自然数集N的每个子集合M,如果M含有0,并且含有M内每个元素的后继元素,则M=N自然数就是满足上述佩亚诺公理的集合N中的元素.关于自然数的所有性质都是这些公理的直接推论.由佩亚诺公理可知,0是自然数关于“后继”的起始元素,如果记0′=1,1′=2,2′=3,…,n′=n+1,…,则N={0,1,2,…,n,…}由佩亚诺公理所定义的自然数与前面由集合所定义的自然数,在本质上是一致的.90年代以前的中学数学教材中,将自然数的起始元素视作1,则自然数集即为正整数集.现在已统一采取上面的记法,将0作为第一个自然数.定理1(最小数原理)自然数集N的任一非空子集A都有最小数.这本是自然数集N关于序关系∈(<)为良序集的定义.现在用归纳公理来证明.证设M是不大于A中任何数的所有自然数的集合,即M={n|n∈N且n≤m,对任意m∈A}由于A非空,至少有一自然数a∈A,而a+1(>a)不在M中.所然,就有1°0∈M(0不大于任一自然数);2°若m∈M,则m+1∈M.根据归纳公理,应有M=N.此与M≠N相矛盾.这个自然数m0就是集合A的最小数.因为对任何a∈A,都有m0意a∈A,于是m0+1∈M,这又与m0的选取相矛盾.反之,利用最小数原理也可以证明归纳公理.因此,最小数原理与归纳公理是等价的.定理2(数学归纳法原理)一个与自然数相关的命题T(n),如果1°T(n0)(n0≥0)为真;2°假设T(n)(n≥n0)为真,则可以推出T(n+1)也为真.那么,对所有大于等于n0的自然数n,命题T(n)为真.证用反证法.若命题T(n)不是对所有自然数n为真,则M={m|m∈N,m≥n0且T(m)不真}非空.根据定理1,M中有最小数m0.由1°,m0>n0,从而m0-1≥n0且T(m0-1)为真.由2°,取n=m0-1即知T(m0)为真.此与T(m0)不真相矛盾.从而证明了定理2.在具体运用数学归纳法进行数学证明时,有多种不同形式.运用定理2中两个步骤进行证明的,为Ⅰ型数学归纳法.经常使用的还有Ⅱ型数学归纳法,Ⅱ型数学归纳法是:如果命题T(n)满足1°对某一自然数n0≥0,T(n0)为真;2°假设对n0≤k≤n的k,T(k)为真,则可以推出T(n+1)也真.那么.对所有大于等于n0的自然数,命题T(n)都真.定理3Ⅰ型数学归纳法和Ⅱ型数学归纳法等价.证假设命题T(n)对n=n0为真,于是只须证明“由T(n)(n≥n0)为真,可以推出T(n+1)也为真”的充要条件为“由T(k)(n0≤k≤n)为真,可以推出T(n+1)也为真.”1°充分性若“由T(n)(n≥n0)为真,可以推出T(n+1)也为真”,则对n0≤k≤n,T(k)为真,特别T(n)为真,因此T(n+1)也为真.2°必要性用反证法.若“由T(k)(n0≤k≤n)为真,可以推出T(n+1)也为真”,但并非对所有大于等于n0的自然数n,由T(n)为真,可以推出T(n+1)也为真,则M={m|m∈N,m≥n0且由T(n)为真推不出T(n+1)也为真}非空.由定理1,M中有最小数m0,且对n0≤k<m0的k,由T(k)为真,可以推出T(k+1)也为真.特别由T(n0)为真可知T(n0+1)为真,由T(n0+1)为真可知T(n0+2)为真,……,由T(m0-1)为真可知T(m0)为真.现已知T(n0)为真,所以T(n0),T(n0+1),…,T(m0)都为真,由此可知T(m0+1)也为真,所以由T(m0)为真推出了T(m0+1)也为真.这与m0的选取矛盾.由定理3可知,Ⅱ型数学归纳法也是合理的推理方法.2.数学归纳法在应用中要注意的问题第一,证明的两个步骤缺一不可第一步是归纳的基础,第二步是归纳的传递.尤其是不可忽视第一步的验证.例1试证1+3+5+…+(2n+1)=(n+1)2+1证假设当n=k时公式成立,则1+3+5+…+(2n-1)+(2n+1)=[1+3+5+…+(2n-1)]+(2n+1)=n2+1+2n+1=(n+1)2+1完成了数学归纳法的第二步,但结论显然是错误的.为什么?因为缺少第一步.事实上,当n=0时,公式不成立.如果缺了第二步,则不论对多少个自然数来验证命题T(n)的正确性,都不能肯定命题对所有自然数都正确.例如,哥德巴赫猜想“任何不小于6的偶数都可以表成两个奇素数之和”,虽然对大量偶数进行了具体验证,但因缺少第二步归纳传递,所以仍只停留在归纳的第一步上.它至今仍只是个猜想而已.第二,第二步在证明T(n+1)为真时,一定要用到归纳假设,即要把“T(n)为真推出T(n+1)为真”或“T(n0),T(n0+1),…,T(k-1)为真推出T(k)为真”的实质蕴含真正体现出来.否则不是数学归纳法证明.例2设a1,…,an为n个正数,b1,…,bn是它的一个排列.试证证1°当n=1时,命题显然成立.2°假设(*)式对n=k成立,则当n=k+1时根据数学归纳法原理,(*)式对所有大于等于1的自然数n都成立.这里虽然形式上完成了数学归纳法的两个步骤,但第二步在证(*)式对n+1成立的过程中,并没用到(*)对n成立的归纳假设.因此,不能说上述证法是采用了数学归纳法.事实上,在上述证明中无须用数学归纳法,用平均值不等式证明就行了.第三,并不是凡与自然数相关的命题T(n),都要用数学归纳法来证明;而且也不是所有这类命题都能用数学归纳法给以证明的.这一命题是与自然数相关的命题,尽管可以对n=0,1,2,…进行验证,但无法实现数学归纳法的第二步,因此不能用数学归纳法进行证明.事实上,数学归纳法只适用于具有递归性的命题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)=S[f(0),f(1),…,f(n-1)]那么,就把这个函数f(n),称作归纳定义的函数.简称递归函数.在具体的递归函数例子中,关系组S可能有几个表达式,或者没有明确的解析表达式,也可能需要给出f(n)的开头若干个值.这样定义函数是合理的,因为我们有:定理4当递推关系组S给定后,定义在N上的满足上述条件(1)、(2)的函数f(n)是存在而且唯一的.证首先指出:对任一自然数k,总可以在片断|0,k|上定义一个函数fk(n),使fk(0)=a,对于片断上其他自然数n,f(n)=S[f(0),…,f(n-1)].这个函数fk(n)是在|0,k|上唯一确定的.现对k进行归纳证明:1°当k=0时,f0(0)=a是唯一确定的;2°假定在|0,k|上已经由(1)、(2)定义了一个唯一确定的函数fk(n),令则fk+1(n)在片断|0,k+1|上有定义,且(1)fk+1(0)=fk(0)=a;(2)fk+1(n)=S[fk(0),…,fk(n-1)]=S[fk+1(0),…,fk+1(n-1)],n=1,2,…,k.因此,函数人fk+1(n)满足条件(1)、(2).由数学归纳法知,对任何自然数k,函数fk(n)在片断|0,k|上唯一确定,且满足(1)、(2).又若k1<k2,则fk1(n)与fk2(n)在片断|0,k1|上完全一致.现作一新的函数:f(n)=fn(n),n∈N.首先,函数f(n)对任一n∈N都有定义,且f(n)=fn(n)=S[fn-1(0),…,fn-1(n-1)]=S[f0(0),…,fn-1(n-1)]=S[f(0),…,f(n-1)]又显然f(0)=f0(0)=a.故函数f(n)是定义在N上且满足(1)、(2)的唯一确定的函数.例4设函数f∶N→N,且(1)f(0)=2,f(1)=3;(2)f(n+1)=3f(n)-2f(n-1),n≥1.证明:f(n)=2n+1.这里给出的递归函数由f(0)、f(1)两个值和一个关系式给定的关系组S确定.但有的递归函数f(0)的值隐含于关系组S之中而未直接给出.例5(IMO-19试题)设f:N+→N+,且(S)f(n+1)>f(f(n)),n∈N+求证:对于任意n∈N+,f(n)=n.证先用数学归纳法证明命题An:任意正整数n,若m≥n,则f(m)≥n.显然A1真.假设An-1真,则对任意m≥n,f(m-1)≥n-1,故f(m)>f(f(m-1))≥2n-1,于是f(m)≥n,从而An真.由此可知,f(n)≥n,f(n+1)>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)的值没有明显给出,但实际上隐含于关系组(S)中.4.递归命题一个与自然数相关的命题T(n),一般来说,它未必是一个函数问题.现在采取如下方式来构造命题T(n)的真值函数f∶N→{1,0}.如果命题T(n)的真值函数f(n)是递归函数,即1°f(0)=1;2°f(n+1)=S[f(0),…,f(n)],且当f(0)=…=f(n)=1时,f(n+1)=1.那么就称T(n)是具有递归性质的命题,或简称递归命题.实际上,所谓递归命题,就是一个与自然数相关的命题T(n),开头(如n=0时)为真,且真值可传递并不是所有与自然数相关的命题都是递归命题.例如本节例3中的命题是与自然数相关的命题,而且对任何n∈N,它都为真,但却不具有递归性,它的真值是不可传递的.一般而言,大多数数论问题,如哥德巴赫猜想、费马问题、孪生素数问题等,都不是递归命题.只有递归命题才能用数学归纳法来证明.因此判别一个与自然数相关的命题T(n)是不是递归命题,是运用数学归纳法的前提.判别的关键在于,探究和发现T(n)的真值对于T(0),…,T(n-1)真值的依赖性.而这种探究本身对于数学归纳法第二步证明,也有直接帮助.例6(1963年北京市竞赛题)2n(n∈N+
本文标题:数学归纳原理和最小数原理的等价性证明
链接地址:https://www.777doc.com/doc-5632391 .html