89年前,哥德爾提出的不完全性定理,至今數學界還沒完全理解

美籍奧地利數學家、邏輯學家庫爾特·哥德爾（KurtGdel，1906年4月28日—1978年1月14日）是二十世紀最偉大的邏輯學家之一，其最傑出的貢獻是哥德爾不完全性定理。

庫爾特·哥德爾（KurtGdel）

那個時代的數學家們為數學尋求了堅實的基礎：一系列基本的數學事實或公理，這些事實既是一致的——不會導致矛盾——也是完整的，是所有數學真理的基礎。

但是，哥德爾25歲時發表的令人震驚的不完全性定理粉碎了這一夢想。他證明了任何可以作為數學基礎的公理都不可避免地是不完整的。關於這些數字，總會有真實的事實不能被那些公理證明。他還表明，沒有任何一套公理能夠證明其自身的一致性。

他的不完全性定理意味著，不可能對所有事物都進行數學理論，對可證明的和真實的事物也無法統一。數學家可以證明的內容取決於他們的初始假設，而不是所有答案所依據的任何基本事實。

自哥德爾發現以來的89年中，數學家偶然發現了他的定理所預言的那些無法回答的問題。例如，哥德爾本人幫助建立了關於無窮大的連續性假說是不確定的，而停止問題則是不確定的，該問題詢問使用隨機輸入的電腦程式將永遠運行還是最終停止。物理學中甚至還出現了無法確定的問題，這表明哥德爾式的不完備性不僅影響數學，而且以某種不被理解的方式影響現實。

這是哥德爾如何證明他的定理的簡化的非正式總結。

哥德爾數

哥德爾的主要策略是將有關公理系統的陳述映射到系統內的陳述，即關於數字的陳述。這種映射使公理系統能夠輕鬆地談論自己。

此過程的第一步是將任何可能的數學陳述或一系列陳述映射到稱為哥德爾數的唯一數字。

歐內斯特·內格爾（Ernest Nagel）

歐內斯特·內格爾（Ernest Nagel）和詹姆士·紐曼（James Newman）在1958年出版的《哥德爾證明》中，對哥德爾方案進行了略微修改，最初以12個基本符號作為詞彙來表達一系列基本公理。 例如，存在的陳述可以用符號expressed表示，而加法則用+表示。 重要的是，符號s表示「的繼任者」，提供了一種指定數字的方式。 例如，ss0指的是2。

然後為這12個符號分配哥德爾數字1到12。

接下來，代表變量（以x，y和z開頭）的字母映射到大於12的質數（即13，13，17，19，…）。

然後，這些符號和變量的任何組合（即可以構造的任何算術公式或公式序列）都將獲得自己的哥德爾編號。

例如，假設0 =0。公式的三個符號對應於哥德爾數字6、5和6。哥德爾需要將此三數字序列更改為一個唯一的數字——其他符號序列將不會生成的數字。為此，他採用前三個質數（2、3和5），將每個質數提高到序列中相同位置的符號的哥德爾數，然後將它們相乘。因此0 = 0變為2^6×3^5×5^6或243,000,000。

該映射之所以有效，是因為沒有兩個公式會以相同的哥德爾數結尾。哥德爾數是整數，並且整數僅以一種方式分解為質數。因此，243,000,000的唯一質數分解是2^6×3^5×5^6，這意味著只有一種可能的方法可以解碼哥德爾數：公式0 = 0。

然後，哥德爾又走了一步。數學證明由一系列公式組成。因此，哥德爾也為每個公式序列賦予了唯一的哥德爾數。在這種情況下，他從之前的質數列表開始——2、3、5，依此類推。然後，他將每個素數提高到序列中相同位置的公式的哥德爾值（例如，如果先出現0 = 0，則為2243,000,000×……），然後將所有內容相乘。

算術化數學

真正的好處是，甚至有關算術公式的語句（稱為元數學語句）也可以自己轉換為具有自己的哥德爾數的公式。

首先考慮公式（0 = 0），表示「零不等於零」。 這個公式顯然是錯誤的。 但是，它有一個哥德爾數：2乘以1的冪（符號的哥德爾編號），再乘以3乘以8的冪（「空心括號」符號的哥德爾編號），依此類推 ，得出2×3^8×5^6×7^5×11^6×13^9。

因為我們可以為所有公式甚至錯誤的公式生成哥德爾數，所以我們可以通過討論它們的哥德爾數來明智地談論這些公式。

考慮以下語句：「公式（0 = 0）的第一個符號是波浪號。」關於（0 = 0）的（真實）元數學陳述轉化為關於公式的哥德爾數的陳述——即，其第一個指數為1，即代字號的哥德爾數。換句話說，我們的陳述說2×3^8×5^6×7^5×11^6×13^9隻有2的單個因數。如果（0 = 0）以除波浪號以外的任何符號開頭，則其哥德爾數至少應為這是2的兩個因數。因此，更準確地說，2是2×3^8×5^6×7^5×11^6×13^9的因數，而2^2不是因數。

我們可以將最後一個句子轉換為精確的算術公式，可以使用基本符號記下*。這個公式當然有一個哥德爾數，我們可以通過將其符號映射到素數的冪上來進行計算。

內格爾和紐曼寫道，這個例子「說明了一個非常普遍而深刻的見解，這是哥德爾發現的核心所在：可以通過討論大型整數的質因子屬性，以間接但完全準確的方式談論長鏈符號的排版屬性。」

對於超數學陳述，也可以轉換為符號：「存在一些數為x的公式序列，可以證明哥德爾數為k的公式」，或者簡而言之，「可以證明哥德爾數為k的公式。」將此類陳述「算術化」的能力為意外而成功的行動奠定了基礎。

G本身

哥德爾的獨到見解是，他可以用公式本身的公式代入自己的哥德爾數，從而避免麻煩。

要查看替換的工作原理，請考慮公式（x）（x = sy）。 （它顯示為「存在一些變量x，它是y的後繼」，或者簡而言之，「 y有一個後繼」。）像所有公式一樣，它具有哥德爾數——一些大的整數，我們將其簡稱為m 。

現在讓我們在公式中用m代替符號y。 這形成一個新公式（formulax）（x = sm），表示「 m有一個後繼」。我們怎麼稱呼這個公式的哥德爾數？需要傳達三點信息：我們從具有哥德爾數m的公式開始。在其中，我們用m代替了符號y。 根據前面介紹的映射方案，符號y的哥德爾數為17。因此，讓我們指定新公式的哥德爾數sub（m，m，17）。

替代構成了哥德爾證明的關鍵。

他認為，「無法證明具有哥德爾數sub（y，y，17）的公式」的形而上的數學陳述。回想一下我們剛剛學到的符號，具有哥德爾數sub（y，y，17）的公式是通過取帶有哥德爾數y（某些未知變量）的公式並將該變量y代入有哥德爾數為17（也就是說，在任何地方都可以）。

事情變得撲朔迷離，但是，儘管如此，我們的超數學陳述（「無法證明具有哥德爾數子（y，y，17）的公式」）肯定會轉化為具有唯一哥德爾數的公式。我們稱它為n。

現在，進行最後一輪替換：哥德爾通過將數字n替換為先前公式中存在y的位置來創建一個新公式。他的新公式為：「無法證明哥德爾數為sub（n，n，17）的公式。」我們將此新公式稱為G。

自然，G有一個哥德爾數。它有什麼價值？瞧，它必須是sub（n，n，17）。顧名思義，sub（n，n，17）是公式的哥德爾數，它是通過將哥德爾數為n的公式代入n並代入帶有哥德爾數為17的符號的任何地方而得出的。G正是這個公式！由於素數分解的唯一性，我們現在看到G所討論的公式就是G本身。

G宣稱自己無法證明。

但是可以證明G嗎？如果是這樣，則意味著存在一些公式序列，可以證明該公式具有哥德爾數sub（n，n，17）。但這與G相反，後者說不存在這樣的證明。相反的陳述G和G在一致的公理體系中都不可能成立。因此，G的真相必須不確定。

但是，儘管G不確定，但事實確實如此。 G說：「無法證明哥德爾數為sub（n，n，17）的公式。」這就是我們發現的事實！由於G是真實的，但在用於構造它的公理系統中無法確定，因此該系統是不完整的。

您可能認為您可以提出一些額外的公理，使用它證明G並解決悖論。但是你不能。哥德爾表示，增強的公理系統將允許構建新的，真實的公式G（根據與之前類似的藍圖），而該公式無法在新的增強系統中得到證明。在努力建立完整的數學系統時，您永遠無法擺脫困境。

沒有一致性證明。

我們了解到，如果一組公理是一致的，則它是不完整的。那是哥德爾的第一個不完全性定理。 第二種方法很容易遵循，即沒有一套公理可以證明其自身的一致性。

如果一套公理可以證明它永遠不會產生矛盾，那意味著什麼？這將意味著存在根據這些公理構建的一系列公式，該公式從數學上證明了「這組公理是一致的」。 按照第一個定理，這套公理就必然是不完整的。

但是，「公理集不完整」與「有一個無法證明的真實公式」相同。這個陳述等於我們的公式G，我們知道公理不能證明G。

因此，哥德爾創造了一個矛盾的證明：如果一組公理可以證明其自身的一致性，那麼我們將能夠證明G。但是我們不能。 因此，沒有一組公理可以證明其自身的一致性。

哥德爾的證明扼殺了對一個一致、完整的數學系統的追求。內格爾（Nagel）和紐曼（Newman）在1958年寫道，「不完全性的含義」還沒有被完全理解，今天仍然如此。