数学归纳法_兼与史宁中先生商榷.pdf

数? 学 ? 归 ? 纳 ? 法??? 兼与史宁中先生商榷孙 道 椿( 广州华南师范大学数学系, 510631)? ? 欧氏几何有个平行线公理:? 过线外一点有且仅有一条直线与它平行?. 历史上有许多学者宣称得到了它的证明, 结果不是发生推理错误, 就是用到了一个与它等价的命题. 用了二千多年, 人们才知道它是不可能证明的. 它是建立欧氏几何不可缺少的一个基本假定. 因此有时也称为公设.我们常用的数学归纳法, 其实也与平行线公理一样,它是建立自然数集的基础. 其实也可称它为? 数学归纳法公理?, 或? 数学归纳法公设?. 下面是常见的一组建立自然数集的公理系统:皮亚诺(Peano) 公理 ? 称一个集合 N为自然数集(包含 0), 若满足:(1) 0 ? N (即 0 是自然数).(2) 任取 n ? N, 存在唯一? 后一元?记为 n+ 1 ? N(称 n 是 n+ 1 的? 前一元?).(3) 任取 n ? N, 均有 n+ 1 ? 1 ( 即, 1 没有前一元).(4) 任取 n, m ? N. 若 n ? m, 则 n+ 1 ? m + 1(即,前一元是唯一的).(5) 若子集 S ? N 满足(i) 0 ? S; (ii) k ? S ? k+1 ? S , 则 S 就是自然数全体 S= N.公理(5)称为数学归纳法原理(虽然表述稍有不同,其实效果是一样的). 皮亚诺公理也可看成是自然数集的定义. 它有 0; 也有了 0 的? 后一元?0+ 1, 记为1; 有 1 的? 后一元?1+ 1, 记为 2; 有 2 的? 后一元?2+1,记为 3; ?不断的产生? 后一元?, 得到的一列元素 0,1,2, 3, 4, ?就得到自然数集.有了皮亚诺公理还要有加、 乘运算的定义.定义 1 ? 加法定义:( ?) 任取 n ? N, 定义 n+ 0= n.( ?) 任取 n, m ? N,定义 n+ ( m+ 1) = ( n+ m)+ 1 ? N.有了加法定义我们可用归纳法证明: 任意二个自然数可以相加, 它们的结果? 和?也是自然数, 即有下面的定理 1.定理 1 ? 任取 n, m ? N, 则其和 n+ m ? N.证明 ? 对任意 n ? N, 令Sn?= { m ? N; n+ m ? N}.(* )i) 由加法定义( ?), n+ 0= n ? N, 得 0 ? Sn;ii) 假定 k ? Sn, 即 n+ k ? N. 结合公理( 2), 可知其后一元( n+ k)+ 1 ? N. 于是由加法定义( ?), n +( k+ 1)= ( n+ k)+ 1 ? N. 由(* )可知 k+ 1 ? Sn.由数学归纳法原理(公理(5)), 有 Sn= N, 即对任意 m ? N, 恒有 n+ m ? N.由此看出, 定义二个自然数的加法, 离不开数学归纳法. 同样下面乘法的定义也离不开数学归纳法.例 1 ? 证明 4+ 3= 7;证 ? 4+ 3 =( i) 4+ ((0+ 1)+ 1)+ 1)=( ii) [ 4+ (0+ 1)+ 1)] + 1 =(iii)[ 4+ ( 0+ 1)] + 1+ 1 =( iv)[ 4+ 0] + 1+ 1+ 1=( v) 4+ 1+ 1+ 1 =( vi) 5+ 1+ 1 =( vii) 6+ 1 =(viii) 7.其中等式(i) , ( vi) , ( vii) , (viii) 是由 10 进制记数法规定; ( ii) , ( iii) , ( iv) , ( v)是由加法定义.定义 2 ? 乘法定义:( ?) 任取 n ? N, 定义 0 ? n= 0.( ?) 任取 n, m ? N, 定义( n+ 1) ? m= n ? m+m ? N.定理 2 ? 任取 n, m ? N, 则其积 n ? m ? N (证明略).就象? 平行线公理?与其它的一些公理一道可建立几何体系一样, 承认这组? 皮亚诺公理?及加法, 乘法定义, 就能严格建立自然数系;就能用严格的数学方法证明任何二个自然数可以相加, 相加的结果? 和?必是一个自然数; 任何二个自然数可以相乘, 相乘的结果? 积?必是一个自然数. 就能用严格的数学方法证明交换律, 结合律, 分配律; 就能用严格的数学方法证明 9+ 8= 15; 证明 6 ? 7= 42 ?下面仅以加法结合律为例, 看如何用公理( 5) 证明:定理 3 ? 加法的结合律: ( n+ m)+ t= n+ ( m+t).证 ? 令 S?= { t ? N; ( n+ m)+ t= n+ ( m+ t)}.36数学通讯 ?2011 年第 6 期(下半月) ??? ? ? ? ? ? ? ? ?争? 鸣?( ?) 由加法定义可知( n+ m)+ 0= n+ m= n+( m+ 0). 即 0? S ;( ?) 假设 k ? S , 即( n + m) + k= n + ( m +k)}. 则(n+ m)+ ( k+ 1) =(i)[( n+ m) + k] + 1 =(ii)[ n+( m+ k)] + 1 =( iii)n + [ ( m+ k) + 1] =( iv)n + [ m+ ( k+1)] .(其中等号( ii) 是由归纳假设; ( i) , ( iii) , ( iv)均是由加法定义. )这说明 k+ 1 ? S . 由数学归纳法公理, S =N. 即对全体自然数结合律成立.上面的表述与通常的有点不同. 但本质上是一样的.定理 4 ? 加法的交换律: n+ m = m+ n (证明略)有兴趣的读者还可用归纳法证明乘法的结合律nmt= n( mt), 交换律 nm= mn, 及分配律 t( n + m)= tm+ tn.下面我们定义二个自然数的序关系(比较大小).定义 3 ? 比较大小: 任取 n, m ? N, 若存在 p ?N, 使 n+ p = m, 则称 n 小于或等于 m, 记为 n ? m,特别若 p ?0, 使 n+ p = m, 则称 n 小于 m, 记为 n m, 若 q= 0, 使 n= 0+ m, 则称 n 等于m,记为 n= m.然后要用数学归纳法, 证明任意二个自然数可以比较大小, 即下面的序定理. 为此先证明:定理 5 ? 记 a ? N的前一元为 a-, 则有( a+ b)-= a+ b-.证明 ? 因为它们的后一元相等a+ b-+ 1= a+ ( b-+ 1)= a+ b= ( a+ b)-+ 1由公理(4)有( a+ b)-= a+ b-.定理 6(序定理) ? 任取 n, m ? N, 它们有> , n; 或 k> n, 由定义 3, 存在非零自然数 t, 使 n+ t= k. 由公理(2), 有 n+ ( t+ 1) = k+ 1.注意 t+ 1 ?0, 这说明 k+ 1> n; 或 k 1; 因为 A ( m- 1) 为真, 由上述第二步知 A( m)为真, 这是矛盾的. 因此假定? 存在使 A ( n )不为真的正整数 n?不成立. 从而证明数学归纳法是合理的.注意, 此证明中用了一个比数学归纳法原理? 高级? 许多的命题: ? 令 m 是 其中最小的?. 从皮 亚诺(Peano)公理, 推出自然数比较大小的定义, 推出自然数的子集必存在最小数, 需要做许多事情. 首先要运用数学归纳法原理推导出二个任意自然数的加法, 且加法满足交换律(否则加法不唯一), 再用加法定义比较二个自然数的大小. 即使您能想出一个办法, 不用加法定义比较大小, 为了证明任意二个自然数可以比较大小(序定理), 也一定要用到数学归纳法.也就是说: 有了数学归纳法(或等价的命题), ? 令m 是其中最小的?才有意义. 因此上面的证明方法犯了逻辑循环的错误.参考文献:[1] ? 华罗庚. 数学归纳法. 北京: 科学出版社, 2002.[2] ? 项武义. 基础分析学之一. 北京: 人民教育出版社.2004.[3] ? 晏成书. 集合论导引. 北京: 北京社会科学出版社,1994.[4] ? 莫绍揆. 数学基础. 北京: 高等教育出版社, 1991.[5] ? 史宁中. 数学思想概论. 长春: 东北师范大学出版社,2008.( 收稿日期: 2011- 04- 01)37?争? 鸣???? ? ? ? ? ?? ? 数学通讯 ?2011 年第 6 期(下半月)。