原文作者，Dr. Dilts，俄勒岡大學數學博士。
翻譯作者，風無名，哆嗒數學網翻譯組成員。
校對，Math001。
關注 哆嗒數學網 每天獲得更多數學趣文
哥德爾的不完備定理是那種能把你腦漿敲出來的一個定理。
在上一篇博客，我們討論了定理本身及其影響。簡單說來，它們顯示出了數學本身的內在局限性。
哥德爾第一定理與一致性、可證明性這兩個概念有關。一個數學系統（由一些假設組成，這些假設被稱作是「公理」）稱為一致的，如果它們沒有矛盾存在。換句話說，你不能證明一個既真又假的語句。
在任何邏輯系統內，都有很多語句，也就是那些你能說出的東西。比如，我像這樣說「所有的素數都比十億小」。它是一個錯誤的語句，但是我仍能說出它。
但是，僅僅因為我能說出一個語句，並不意味著我可以證明它為真或者假。大多數情況下，那個語句是難以證明的，所以你不知道如何證明它。可是，還有一種可能，存在既不能證明為真，也不能證明為假的語句。這種語句，我們稱為不可證明的語句。任何擁有不可證明語句的邏輯系統（公理集）成為不完備的。
哥德爾第一不完備定理說了：如果你有一個一致的數學系統（也就是，一堆互不矛盾的公理），並且你可以做算數運算，那麼，一定存在使用那些公理不能證明的語句。[原注1]
換句話說，數學是不完備的。證明所有的事情，是不可能的。（譯者注: 籠統地說數學是不完備的，是不對的。此文作者這裡提供的是一個不嚴謹的簡單說法。）
哥德爾第一不完備定理的最基礎的想法，就是這句話：「這句話是不可證明的」。
如果你能證明這句話是正確的，根據定義，它就是可證明的。但是這句話自己說了它是不可以證明的；同時由於它是真的，它也是不可以證明的。但是它不能既是可證明的又是不可證明的。因此，這句話必須只能是不可證明的。
雖然這就是我們將來採用的基礎的想法，問題是，在數學裡面，並不存在一個明顯的形式化的方法來說「這句話是不可證明的」。你說的可證明是什麼意思？「這句話」指什麼？使用什麼公理呢？
哥德爾的證明必須讓所有的這些都完美的嚴格化。
第一步要證明的是：任何嚴格的數學語句都可以轉化為一個數，反過來也可以。
這一步是精妙的，不過並不複雜。從某種意義上說，這就像一段代碼，它把每一字母都轉化成一個數。比如，我們可以這樣做：a轉換成1，b轉換成2，等等。單詞」math"將會轉化成"13-1-20-8"。計算機也使用了類似的模式來把文本存儲像成0和1的形式。
為了把數賦給嚴格的數學語句，哥德爾使用了類似的方法來進行編碼。實現這種編碼的方式並不唯一，不過我將要講一種與哥德爾最初的方法比較接近的方法。
第一步，對於你的某個數學系統的每一個數學符號，給予一個數。[原注2]比如，也許」0"被存儲為1, 「=」被存為儲2， "+"存儲為3.
一條數學語句就是這些符號的一個列表。使用數對單個的符號進行編碼，就可以等價地說，語句就是數的列表。例如 0=0等價於(1,2,1)。
為了把語句編碼為唯一的數，我們讓它的哥德爾數等於一部分素數的冪的乘積，冪的次數為數學符號在列表中的位置。因此，0=0的哥德爾數是2^1 · 3^2 · 5^1 = 90。
對於一個語句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))是真的。（注意，unprovable(y)的輸入是某個語句的哥德爾數。這個例子中，這個語句即S）
清楚一點說，對角線引理並沒有證明S或者Unprovable(G(S))是真的，僅僅證明了它們或者同時為真或者同時為假。你開動腦筋，想想這到底啥意思？
對角線引理也表明了:一個未知的可能非常長的數學語句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] 引理一般是相對容易證明的，對角線引理也是這樣。然後，它的證明是技術性的，並不是很有啟發性。
關注 哆嗒數學網 每天獲得更多數學趣文