翻譯：哥德爾是怎樣證明數學的內在的局限性

原文

哥德爾的不完備定理是那種能敲碎你的腦殼的定理。

在上一篇博客，我們討論了定理本身及其影響。簡短的說，它們顯示出了數學本身的內在局限性。

哥德爾第一定理與一致性、可證明性這兩個概念有關。一個數學系統（一個假設的集合。這些假設被稱作是「公理」）稱為一致的，如果它們沒有矛盾存在。換句話說，你不能證明一個既真又假的語句。

在任何邏輯系統內，都有很多語句，也就是那些你能說出的東西。比如，我像這樣說「所有的素數都比十億小」。它是一個錯誤的語句，但我仍然說出它。

(上圖中的文字：嘿)

但是，僅僅因為我能說出一個語句，並不意味著我可以證明它為真或者假。大多數情況下，那個語句是難以證明的，所以你不知道如何證明它。可是，存在既不能證明為真，也不能證明為假的語句，這也是可能的。這種語句，我們稱為不可證明的語句。任何擁有不可證明語句的邏輯系統（公理集）成為不完備的。

哥德爾第一不完備定理說了：如果你有一個一致的數學系統（也就是，沒有矛盾的公理集），並且你可以做算數運算，那麼，一定存在使用那個公理集不能證明的語句。[原注1]

換句話說，數學是不完備的。證明所有的事情，是不可能的。（譯者注: 籠統地說數學是不完備的，是不對的。此文作者是哥德爾定理的，不過此處說話不嚴謹。）

(上圖中的文字：這個宇宙，就我所知它。。。是破碎的)

哥德爾第一不完備定理的最基礎的想法，就是這句話：「這句話是不可證明的」。

如果你能證明這句話是正確的，根據定義，它就是可證明的。但是這句話自己說了它是不可以證明的；同時由於它是真的，它也是不可以證明的。但是它不能既是可證明的又是不可證明的。

因此，這句話必須緊緊是不可證明的。

這就是我們將來採用的基礎的想法，問題是，在數學裡面，並不存在一個明顯的形式化的方法來說「這句話是不可證明的」。你說的可證明是什麼意思？「這句話」指什麼？使用什麼公理呢？

哥德爾的證明必須讓所有的這些都完美的嚴格化。

第一步是顯示出：任何嚴格的數學語句都可以轉化為一個數，反過來也可以。

這一步是精妙的，不過並不複雜。從某種意義上說，這就像一段代碼，它把每一字母都轉化成一個數。比如，我們可以這樣做：a轉換成1，b轉換成2，等等。單詞」math"將會轉化成"13-1-20-8"。計算機使用了類似的模式來存儲像1, 0這些文本。

為了把數賦給嚴格的數學語句，哥德爾使用了類似的方法來進行編碼。存在很多的方法來實現這一點，不過我將要講一種與哥德爾最初的方法比較接近的方法。

（上圖中的文字：畢竟，我過去是聰明的。。）

第一步，對於你的某個數學系統的每一個數學符號，給予一個數。[原注2]比如，也許」0"被存儲為1, 「=」被存為儲2， "+"存儲為3.

一條數學語句就是這些符號的一個列表。使用數對單個的符號進行編碼，就可以等價地說，語句就是數的列表。例如

0=0

等價於(1,2,1)

為了把語句編碼為唯一的數，我們讓它的哥德爾數等於一部分素數的冪的乘積，冪的次數為數學符號在列表中的位置。因此，0=0的哥德爾數是

對於一個語句S，比如」0= 0」,我們使用記號G(S)來指代它的哥德爾數。因此，

G(0=0) = 90

正如你所想像的，即使是對中等長度的語句，哥德爾數也會很快變得非常大。不過，大小不是一個問題，我們不需要把它們寫下來。

（上圖中的文字：唷！）

關鍵的問題是:對於任一個數，我們可以返回來得到一條數學語句。

每一個數都可以唯一地分解為素數的乘積。如145530 = 2^1 * 3^3 * 5^1 * 7^2 * 11^1,所以145530代表了 0 + 0 = 0.

任一嚴格的數學語句都可以用這種方式翻譯成一個數。乃至一個證明，也僅僅是一些捆綁在一起的語句而已。(「A」 蘊含「B」, 並且「B」蘊含「C」,所以「A」蘊含「C」)。那就意味著，我們展示了所有的數學都能夠僅用數來寫出來。[原注3]

類似地,存在一個算數的方法來檢查一串使用哥德爾數來表示的語句，是否是另一串使用哥德爾數來表示的語句的證明。[原注4]

把數學語句翻譯成數，看起來像是有興趣的竅門，它是哥德爾不完備定理的證明的關鍵。

它如此重要的原因在於，它讓我們把任何關於證明、可證明性的問題轉化為關於數的算數問題。因此，為了證明任何可證明的語句，我們可以僅僅使用數以及它們的性質。

（上圖中的文字：現在，我可以與數一起工作了！）

例如，考慮這個被我稱為Unprovavle(y)的語句。這個語句是：「y是某個語句的哥德爾數，並且不存在一個數x使得x是那個語句的證明的哥德爾數」。

因此，unprovable(y)本質上在說「y所代表的語句」是不可證明的。但是，它除了是一個關於證明與語句的問題以外，它還完全是一個關於數、數的算數關係的問題。

這個準確的算術關係是非常複雜的，不過可以被精確地定義。類似的，Prime(y),這個簡單得多的語句語句「y是一個素數」, 存在一個算術關係Unprovable(y)。於是，Prime(y)斷言了一個數如何，這個斷言可以被一些相對而言比較簡單的算術來判定。

現在，我們將來來帶長途征程的最後一部分了。

（上圖中的文字：在那兒。。幾乎所有的。。）

哥德爾的證明的原創的想法是這句話：「這句話是不可證明的」。使用Unprovable(y)這句精確的數學語句，我們可以讓這句不精確的語句完全精確。[原注5]

為了得到「這句話是不可證明的」的精確版本，我們將使用 「對角線引理」。（一條引理只是你用於證明其它定理的定理[原注6]）。對角線引理表明了，就我們正在使用的數學系統而言，存在一個語句S它滿足：S是真的，當且僅當Unprovable(G(S))是真的[原注7]。（注意，unprovable(y)的輸入是某個語句的哥德爾數。這個例子中，這個語句即S）

清楚一點說，對角線引理並沒有證明S或者Unprovable(G(S))是真的，僅僅證明了它們或者同真或者同假。這意味著什麼？

（上圖中的文字：21212意味著什麼？）

對角線引理也表明了:一個未知的可能非常長的數學語句S,是真的，當且僅當 unprovable(G(S))是真的。但是unprovable(G(S))是真的，（根據unprovable（y）的定義）意味著S是不可證明的。

所以，如果我們能夠證明「 語句S是真的」，對角線引理表明我也能證明「unprovable(G(S))是真的」。但是，unprobable(G(S))說的是「S是不可證明的」！因此，S既是可證明的又是不可證明的,這就是一個矛盾。

因此，S必然在事實上是不可證明的。

語句S就是我們正在尋找的 「這句話是不可證明的」 這個語句的準確的版本。因此，不是每一個語句都是可以證明的。

悲慘的、有缺陷的數學。。。

（上圖中的文字：你弄壞它了！）

[原注]

[1] 關於數學系統，還有很多更加技術性的假定，比如，它必須是「有效的」，又叫做「可遞歸地枚舉的」。對哥德爾的證明來說，這些假定是至關重要的。就我想向外行讀者做介紹的這篇文章的主要部分來說，我覺得它們過於技術化了。我會在後面的腳註裡面解釋為什麼那個系統需要是有效的。

[2] 算術的公理化也就是皮亞諾算術，並沒有顯式地提及所有的自然數。事實上，它僅提及了0.它擁有一個能否計算下一個數的「後繼函數」S。因此，S(0)就是1的定義，S(S(0))是2的定義。所以，當把數學語句翻譯成哥德爾數的時候，我們的編碼僅需要給0、S賦值，而不需要給每一個數單獨賦值。那意味著我們的編碼僅需要考慮有限多個符號。

[3]這裡指任何從我們的公理、選定的符號所生起的數學。

[4] 在上一篇文章中，我們忽略了很多重要的技術性的假設。其中之一，在這裡說一下。那就是，你的數學系統(公理的集合)是有效的(effective)。在本質上，這意味著，存在一個這樣的計算機程序：從理論上，能夠列出你的數學系統的所有定理，而不列出任何不是定理的語句。對於不完備定理所考察的基本的數學系統--皮亞諾算術， 這一點是真的。對於標準集合論（ZFC）,這一點也是真的。還存在一些不有效的系統，它們趨向於無用或無趣。比如有一個這樣的系統：把算術中所有真的語句都作為公理。於是，任何真的東西都是公理，從而證明上是平凡的。為了讓算術證明的校驗(check)能工作，你的數學系統是有效的，這個假定是至關重要的。

[5] 哥德爾找到了一個直接說這個語句的方法。我們會採取一個略微不同的、更容易理解的途徑， 不過哥德爾證明的主要動機是一樣的。

[6] 引理一般是相對容易證明的，對角線引理也是這樣。然後，它的證明是技術性的，並不是很有啟發性。

推薦閱讀：