自然數歸納法

自然數歸納法，是一種數學證明方法，

通常被用於證明某個給定命題在整個（或者局部）自然數範圍內成立。它可以用一個有限的方式寫出一個無限的證明。

後續文章中我們會看到，

這種用有限表示無限的方法，其實是有侷限性的，並不能用來解決所有的問題，

它能處理的只是無限中的一個子集罷了。

自然數歸納法，我們可以描述如下：

為證明對每一個自然數 ，命題 為真，只需要證明兩件事，（1）對於自然數 ，命題 為真（2）如果對於自然數 ，命題 為真，那麼對於自然數 ，命題 也為真

其中，第(1)條稱為起始條件，第(2)條稱為遞推條件，或者稱為歸納步驟。

第(2)條中，為了證明 而假設的 ，稱為歸納假設。

這似乎是很顯然的事情，我們可以在一張無限長的紙帶開頭寫上初始條件 ，

接著根據遞推條件，由 我們可以證明 成立，

重複這種思想，我們可以由 證明 成立，如此不斷的進行下去，

最終，對於每個自然數 ，我們都能證明 成立。

但是，這樣並不算是一個有效的證明。

要證明自然數歸納法的正確性，我們還需要補充一些集合論方面的知識。然而，在此之前，我們還是先來看自然數歸納法的一個例子吧。

例子

在上一篇，我們在定義遞歸函數fact的時候，

先找到了「遞推式」，再找到了「終止條件」，然後寫出了fact的定義：

fact :: Int -> Intfact 1 = 1fact n = n * fact (n-1)

我們還提到，有一個步驟是必不可少的，

那就是證明fact的正確性，即證明這樣定義的fact就是階乘函數 。

現在，我們正好可以用自然數歸納法來證明它。

我們假設命題 為：fact n的值為

（1）對於自然數 ，命題 ：fact 1的值為 ，成立

（2）假設對於自然數 ，命題 ：fact m的值為 ，成立

那麼，我們可以得到fact (m+1) = (m+1) * fact m，值為 ，也成立。

所以，對於任意自然數（ ），fact n的值就是 。

於是，我們證明瞭fact就是階乘函數 。

自然數歸納法還有另外一種等價形式，

如果要證明 對每一個自然數 為真，只要證明對於任意自然數 ，如果 當 為真，那麼 也為真。

集合上的關係

關係是一個日常生活用語，例如，「同學關係」，「我們的關係很好」之類的。

然而，它也是一個集合論中的概念，這給我們帶來了很多困擾。為了避免歧義，本文中從這裡開始，我們開始談論數學，我們要對集合上的「關係」進行定義。

直觀的說，集合 的元素和集合 的元素之間的關係是一個二元性質 ，

使得對於每個 和 而言， 要麼為真，要麼為假。

關係通常表示為一個集合，它是笛卡爾積的子集，即，

集合 和集合 之間的關係 是它們笛卡爾積的一個子集 。如果序對 屬於子集 ，則認為 與 之間的關係為真，否則認為 與 之間的關係為假。

通常關係直接描述為 ，或者 ，而不用 。

除了二元關係之外，對任何正整數 ，還可以定義 元關係。

如果 為集合，則在 上的 元關係，是笛卡爾積 的一個子集。

某個集合上的二元關係有很多性質，例如自反性，對稱性，反對稱性，傳遞性。

一個關係 是自反的，如果 對於所有的 成立；是對稱的，如果 就有 ，對於所有的 都成立；是反對稱的，如果 且 則 是同一個元素，對於所有的 都成立；是傳遞的，如果 和 能推出 ，對於所有的 都成立。（注意，反對稱性不是對稱性的否定。

等價關係是同時具有自反性，對稱性和傳遞性的關係。

偏序關係是具有自反性，反對稱性和傳遞性的關係。等價關係的一個例子就是相等性，相等性關係 當且僅當 是同一個元素。偏序關係，例如通常的序關係 ， 當且僅當 。

良基關係

歸納法有各種各樣的形式，自然數歸納法只是其中的一種應用，

在數理邏輯和形式語言理論中，用的最多的是結構歸納法，在樹形結構上進行歸納，後續文章中我們會提到。

人們總結了各種歸納法的共性，提出了良基關係的概念，

於是，自然數歸納法和結構歸納法都變成了在良基關係上通用歸納法的具體應用了。

集合 上的良基關係（well-founded relation），是 上的一個二元關係 ，

如果不存在無限下降序列（infinite descending sequence） 。

例如，自然數上的關係 ，就是一個良基關係。但是 卻不是，因為存在一個無限下降序列 。

根據良基關係，我們可以定義集合中的最小元，

為最小元，如果不存在 ，使得 。

對於良基關係，有一個等價的定義，

上的二元關係 是良基的，當且僅當 的每一個非空子集 有最小元。

我們可以證明一下這兩種說法等價性。

要證當且僅當，我們需要證明充分性和必要性，

（1）充分性

要證： 上的二元關係 是良基的，則 的每一個非空子集 有最小元。

使用反證法，如果 沒有最小元，則對於每個 ，總可以找到 ，使得 。

但是，如果這樣的話，我們就可以對任何 ，以 開始構造一個無限下降序列 ，這與 是一個良基關係矛盾。

充分性證畢。

（2） 必要性

要證：如果 的每一個非空子集 都有最小元，

則 上用於比較的二元關係 是良基的。

由於 的每一個非空子集 都有最小元，

則不可能存在無限下降序列 ，因此， 是良基的。

必要性證畢。

因此， 上的二元關係 是良基的，當且僅當 的每一個非空子集 有最小元。

良基歸納法

設 為集合 上的良基二元關係，並且設 為關於 中元素的某個命題，

如果 對於所有的 成立，就必然有 成立，那麼 就對所有的 成立。

我們看到 確實是自然數集上的良基關係，因此自然數歸納法只是良基歸納法的一種特例。

現在我們有了足夠的能力來證明自然數歸納法的正確性了，

只要我們證明瞭良基歸納法是正確的。

還是用反證法：

我們期望證明，

前提：如果 對於所有的 成立，必然有 成立，結論：那麼對於所有的 ， 都成立。

如若不然，假設存在 ，使得 不成立，

則集合 非空，因此根據良基關係的等價定義，集合 必有最小元 ，而且， 成立。

則根據前提的逆否命題，一定存在 ，使得 成立，

所以，我們有 ，且 ，與 是 的最小元矛盾。

證畢。

由此，我們證明瞭良基歸納法的正確性。

理解良基關係和偏序關係，是理解遞歸和不動點運算元的第一步。

總結

本文從自然數歸納法出發，補充了一些集合論方面的知識，

讓我們熟悉了集合上的幾種常用關係，例如，等價關係，偏序關係和良基關係，這些關係在以後的文章中還會被再次提到。

最後，我們證明瞭良基歸納法，從而證明瞭自然數歸納法的正確性。

不知道是否很明顯了，遞歸的步驟和歸納的步驟，簡直是太像了，這一定不是偶然。

在The Little Prover一書中，為了證明遞歸函數是否全函數（total function），

作者使用了測度（measure）的概念，這實際上定義了參數集上的一個良基關係。全函數是可計算理論中一個很重要的概念，到底什麼是全函數，什麼是測度？下文我們再詳細討論。

---

參考

維基百科 - 數學歸納法

維基百科 - 二元關係 維基百科 - 良基關係 程序設計語言的形式語義

---

下一篇：遞歸函數（四）：全函數與計算的可終止性

推薦閱讀：