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

数学归纳原理和最小数原理的等价性证明这两个原理都是自然数公理系统中最基本的原理，人们常常用最小数原理证明数学归纳原理。我发现用数学归纳原理也可以证最小数原理。所谓的最小数原理是指：自然数集合的任意非空子集必有最小元素。一：用数学归纳原理证最小数原理。 当自然数的非空子集只含一个元素时，这个元素就是最小元素。设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