1.2　最小自然数原理与数学归纳原理

应该指出，自然数完全源于经验，它的概念与符号的形成，它的运算、关系和性质，都是人类社会在实践经验的基础上逐步积累总结而形成的，认为是“显然”正确的.在此基础上，合理地引入了“零”和“负整数”，得到整数集合，它的性质是在自然数性质的基础之上，严格地建立起来的.随着数学的发展，人们开始思考究竟什么是“自然数”，它的概念、运算、关系和性质，在理论上是否可靠正确？经过数学家的不断研究，最终由G.Peano在1889年用公理化方法完成了这一工作.他把“自然数”定义为这样一个集合N：首先，在这集合的元素间引进了一种称为“后继”的关系，其次要求它的元素及这种关系满足一组他所提出的公理.这样的集合就称为自然数集合，它的元素就称为自然数.在附录一中我们将详细讨论Peano公理.在此基础上，我们所熟知的自然数的运算、关系及性质都可给出严格的定义与证明.简单说来，自然数的本质属性是由归纳原理（或称归纳公理）刻画的，它是自然数公理化定义的核心，用通常的语言可表述如下：

归纳原（公）理设S是N的一个子集，满足条件：

（i）1∈S；

（ii）如果n∈S，则n+1∈S，

那么S=N.

应该指出，在严格的表述中，这里的加法运算“+”是用“后继”关系来刻画的（见附录一）.这原理是我们常用的数学归纳法的基础，两者实际上是一回事.

定理1（数学归纳法）设P（n）是关于自然数n的一种性质或命题.如果

（i）当n=1时，P（1）成立；

（ii）由P（n）成立必可推出P（n+1）成立，

那么P（n）对所有自然数n成立.

证设使P（n）成立的所有自然数n组成的集合是S.S是N的子集.由条件（i）知1∈S；由条件（ii）知，若n∈S，则n+1∈S.所以由归纳原理知S=N.证毕.

整除理论和初等数论的基本内容远在Peano公理提出之前就已经建立起来了，当然不会用到归纳公理和数学归纳法.这时人们利用的是“公认”正确的性质，这就是下面的最小自然数原理及最大自然数原理.

定理2（最小自然数原理）设T是N的一个非空子集.那么，必有t₀∈T，使对任意的t∈T有t₀≤t，即t₀是T中的最小自然数.

定理3（最大自然数原理）设M是N的非空子集.若M有上界，即存在a∈N，使对任意的m∈M有m≤a，那么，必有m₀∈M，使对任意的m∈M有m≤m₀，即m₀是M中的最大自然数.

由归纳原理可以证明这两个在数学中，特别是初等数论中常用的自然数的重要性质.

定理2的证明考虑由所有这样的自然数s组成的集合S：对任意的t∈T必有s≤t.由于1满足这样的条件，所以1∈S，S非空.此外，若t₁∈T（因T非空所以必有t₁），则t₁+1＞t₁，所以t₁+1∉S.由这两点及归纳原理就推出：必有s₀∈S使得s₀+1∉S（为什么）.我们来证明必有s₀∈T.因若不然，则对任意的t∈T必有t＞s₀，因而t≥s₀+1.这表明s₀+1∈S，矛盾.取t₀=s₀就证明了定理2.

定理3的证明考虑由所有这样的自然数t组成的集合T：对任意的m∈M有m≤t.由条件知a∈T，所以T非空.由定理2知，集合T中有最小自然数t₀.我们来证明t₀∈M.若不然，则对任意的m∈M必有m＜t₀，因而m≤t₀-1.这样就推出t₀-1∈T，但这和t₀的最小性矛盾.取m₀=t₀就证明了定理3.

定理2和定理3是等价的，请读者自证.

最小自然数原理是我们常用的第二种数学归纳法的基础.

定理4（第二种数学归纳法）设P（n）是关于自然数n的一种性质或命题.如果

（i）当n=1时，P（1）成立；

（ii）对n＞1，若对所有的自然数m＜n，P（m）成立，则必可推出P（n）成立，

那么P（n）对所有自然数n成立.

证用反证法.若定理不成立，设T是使P（n）不成立的所有自然数组成的集合，T非空.由定理2知集合T必有最小自然数t₀.由于P（1）成立，所以t₀＞1.由条件（ii）（取n=t₀）知，必有自然数m＜t₀使P（m）不成立.由T的定义知m∈T，但这和t₀的最小性矛盾.证毕.

有的读者可能会感到奇怪，为什么这些“显然”正确的事实，在这里作为重要的定理列出并加以证明，认为这样是没有必要的.关于这一点我们不想在此作进一步的讨论，也不要求读者去深入探究，因为这涉及数学的一些基本问题.有兴趣的读者，特别是准备当教师的读者，为了对“自然数”有更正确的认识，可阅读附录一，那里介绍了自然数的公理化定义，并初步讨论了上面所提的问题（亦见附录一的习题）.这里特别要指出的是：尽管凡是用数学归纳法证明的命题都可用最小自然数原理来证明，但是国内外不少书（注：例如，《数学归纳法》（华罗庚著，科学出版社，2002年重版）中就有这样的错误断言和错误证明（见第82页倒数第2行至第83页第5行）.更应指出的是，书中所给出的由数学归纳法（即数学归纳原理）推出最小自然数原理的“证明”也是错误的.这是因为作者混淆了第一种数学归纳法（即数学归纳法）与第二种数学归纳法，这个“证明”实际上是由第二种数学归纳法推出最小自然数原理.事实上，第二种数学归纳法与最小自然数原理是等价的.虽然出现了这样的理论上的疏忽，但这是学习如何应用数学归纳法的一本很好的书.参看附录一.上断言，由最小自然数原理可推出归纳原理，都是错误的.在附录一中指出了这为什么是错误的.

以上列出的性质和定理是初等数论的基础，读者必须熟练掌握.

此外，在初等数论中还经常用到的一个工具是：

定理5（鸽巢原理）（注：亦称为盒子原理或Dirichlet原理.）设n是一个自然数.现有n个盒子和n+1个物体.无论怎样把这n+1个物体放入这n个盒子中，一定有一个盒子中被放了两个或两个以上的物体.

证用反证法.假设结论不成立，即每个盒子中至多有一个物体，那么，这n个盒子中总共有的物体个数≤n.这和有n+1个物体放到了这n个盒子中相矛盾.证毕.