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個盒子中相矛盾.證畢.