哥德爾不完備定理

哥德爾不完備定理（Gödel's incompleteness theorems）是數理邏輯中的兩條定理，探討了形式化公理系統中可證明性的局限性。這些結果由庫爾特·哥德爾於1931年發表，在數理邏輯和數學哲學領域都具有重要意義。人們普遍認為，這些定理表明希爾伯特計劃——即為所有數學尋找一套完備且一致的公理系統——是不可能實現的。

第一定理指出：

任何自洽的形式系統，只要蘊涵皮亞諾算術公理，就可以在其中構造在系統中不能被證明的真命題，因此通過推理演繹不能得到所有真命題（即系統是不完備的）。

這是形式邏輯中的定理，容易被錯誤表述。有許多命題聽起來很像是哥德爾不完備定理，但事實上並不是。具體實例見對哥德爾定理的誤解。

把第一條定理的證明過程在系統內部形式化後，哥德爾延伸出了第二定理。該定理指出：

任何邏輯自洽的形式系統，只要蘊涵皮亞諾算術公理，它就不能用於證明其本身的自洽性。

大衛·希爾伯特提出，像實分析那樣較為複雜的系統的相容性，可以用較為簡單的系統中的手段來證明。最終，全部數學的相容性都可以歸結為基本算術的相容性。但哥德爾的第二條定理證明了基本算術的相容性不能在自身內部證明，因此當然就不能用來證明比它更強的系統的相容性了。

通過運用對角論證法，哥德爾不完備定理成為了探討形式系統局限性的一系列密切相關定理中最早提出的一批。緊隨其後的還有關於真理在形式上不可定義的塔斯基不可定義定理、邱奇關於希爾伯特可判定性問題不可解的證明，以及圖靈關於停機問題無解演算法的定理。

## 形式系統：完備性、一致性和有效公理化

不完備性定理適用於足夠複雜，可以表示自然數算術的形式系統，而這種形式系統是自洽的，可以被公理化的。這些概念的詳細含義會在後面給出。尤其是在一階邏輯的語境中，形式系統也被稱為"形式定理"。一般地，一個形式系統被定義為含有一組特定公理集合以及符號變換規則(或者是推導規則)的演繹工具。這樣的一個形式系統的例子是一階算術系統，在這個系統中，所有變量都代表為自然數。而在其他系統中，例如集合論，只有部分屬於形式系統的表述才表示了自然數算術。不完備性理論是關於這些形式系統中的形式可證明性，而不是關於非形式意義上的"可證明性"。

形式系統可能具有的性質如下，完備性、一致性和有效公理化的存在性。不完備性定理則表明任何蘊含皮亞諾算術公理的形式系統不能同時具有這三個性質。

### 有效公理化

如果形式系統中的定理集是遞歸可列舉的集合(Franzén 2004, p. 112)，那麼該形式系統是"有效公理化的"(也被稱為「生成定理的有效性」)。

這意味著，在原則上電腦程式能夠列舉出系統中所有的定理，而不列出任何非定理的陳述。皮亞諾公理和策梅洛-弗蘭克爾集合論 (ZFC) 都是有效生成定理的例子。

現在被稱為真算術的理論不僅有皮亞諾算術中關於整數的正確陳述，而且是自洽和完備的，並有足夠的運算公理。但是它的定理集不是遞歸可列舉的集合，因此也不滿足不完備定理的假設。

## 證明思路

- 只要證明了初等算數理論Π是不完全的，採用相同的方法就可以證明任何包含Π的形式理論都是不完全的
- 證明Π的不完全性的關鍵是在於構造出初等算數語言Ľ中的一個含義為真的語句Α，證明如果Α能被證明則將推出矛盾
- 包含初等算數理論的意義是它包含所有正整數（無窮元素）。而命題和證明都可以被映射到正整數。另一方面，它還支持歸納集，即及由一些初始元素及新元素構成的集合，而新元素都是由初始元素歸納（運算）而得的。形式理論由公理及定理構成，定理可以看作是公理及已知定理的歸納，因而形式理論本身可以表示成以某些正整數為初始元素的某種歸納集。這使得可證性變為算術命題
- 所構造的語句Α類似於「說謊者悖論」（即「這句話在說謊」），但Α是「本語句不可證」。對這一形式化的Α如果假設Α可證將推出矛盾，但假設Α不可證卻不能推出矛盾，所以Α不是一個悖論。而Α的含義是它不可證，而它又被證明是不可證的，因此Α是個不可證的真命題
- Ľ不完全，那麼包含Ľ的Π不完全，那麼包含Π的形式系統不完全。得證。

## 含義

哥德爾巧妙地利用了命題的「真值為真」和「含義為真」的區別，從而構造出了含義為真而真值不可證的命題，又避免了悖論的陷阱。形式邏輯系統的命題本身是沒有含義的。命題只有真值而沒有含義。公理命題的真值為真。其它命題的真值為真若且唯若該命題可以被證明，為假若且唯若該命題的非可以被證明。當形式邏輯系統被實際應用時，系統中的符號都被映射到實際概念上，從而有了語義。這種映射叫做一個模型。有了模型，命題就有了含義（語義）。例如，在ZF公理化集合論中，系統中的對象（object）被影射到「集合」這一概念，∈被映射到「屬於」這一概念就是模型的一個例子。而ZF公理化系統本身即使沒有模型也可以成立。如果換一個模型，形式系統沒變，只是它不再是集合論了。當然，ZF公理化系統是為了集合論量身打造的，很適合於集合論。如果換一個模型，很難找到可理解的語義。但這說明了「真值為真」和「含義為真」是有區別的。

在常見情況下，命題的「真值為真」和「含義為真」是一致的。例如，設A為一命題,則命題A↔¬A的含義是「本命題A為假」，這時A的真值為真和含義為真是一致的，結果形成了否定循環而構成了悖論。而邏輯系統不能含有悖論，所以這樣的A應該是構造不出來的。哥德爾定理證明的巧妙之處就在於將悖論的「為假」改為了「為不可證」使得真值為真和含義為真成為不一致（含義為真是不可證，而真值為真或假都是可證），因而產生了自我否定又避免了循環的效果，也就避免了悖論。

理解了這一點，就可以理解哥德爾定理不是說存在真值為真又不可證這種自相矛盾的悖論命題（實際上應該構造不出來），而是存在含義為真但不可證（即真值不可知）的命題。哥德爾定理也不只是說存在既不可證真，也不可證偽的命題，這樣的命題有很多，哥德爾定理的重要之處在於它還說了該不可證的命題是含義為真的。

哥德爾定理是一階邏輯的定理，故最終只能在這個框架內理解。在形式邏輯中，數學命題及其證明皆以一種符號語言描述，只要檢查每一個證明的有效性，便可從一組公理開始無可辯駁地證明一條定理。理論上，這樣的證明可以在電腦上檢查，事實上這樣的有效性檢查程序也已經有了。

為了這個過程得以進行，需確定手頭有什麼樣的公理。可以從一組有限的公理集開始，例如歐幾里得幾何。或者更一般地，由一個可以允許無窮的公理列表開始，只要能機械地判斷給定的命題是否是一條公理就行。在電腦科學裡面，這被稱為公理的遞歸集。儘管無窮的公理列表聽起來有些奇怪，實際上自然數的通常理論中(被稱為皮亞諾公理)就是如此。

哥德爾的第一條不完備定理表明任何一個允許定義自然數的系統必定是不完備的：它包含了不能在此系統內以一階謂詞邏輯形式證明的命題，並且該命題的否命題也不能在該系統內以一階謂詞邏輯的形式證明。

存在不完備的系統這一事實本身並不使人感到特別驚訝。例如，在歐幾里得幾何中，如果把平行公設去掉，就得到一個不完備的系統。不完備的系統可能只意味著尚未找出所有必須的公理而已。

但哥德爾揭示的是在多數情況下，例如在數論或者實分析中，永遠不能找出公理的完整集合。換句話說，每一次將一個命題作為公理加入，將總有另一個命題出現在所能形式證明的範圍之外。

如果加入無窮條公理（例如，所有真命題）到公理列表中，確保所有命題都可證明為真或假，但得到的公理列表將不再是遞歸集。給出任意一條命題，將沒有機械的方法判定它是否是系統的一條公理。如果給出一個證明，一般來說也無法檢查它是否正確。

在電腦科學的語言中，哥德爾定理有另一種表述方式。在一階邏輯中，定理是遞歸可枚舉的：即可以編寫一個可以枚舉出其所有有效證明的程序。同時可以考慮是否可以將結論加強為遞歸的：可以編寫一個在有限時間內判定命題真假的程序嗎？然而根據哥德爾定理，答案是一般來說不能。

## 不確定命題的例子

哥德爾和保羅·寇恩得出的一些結果結合起來給出了不確定命題（既不能證明也不能否證的命題）的一個實際例子：選擇公理和連續統假設都是集合論的標準公理系統內的不確定命題。

在1973年，同調代數中的懷特海問題被證明是集合論中的不確定命題。

1977年，Paris和Harrington證明了組合論中的一個命題，拉姆賽理論的某個版本，在皮阿諾公理給出的算術公理系統中是不確定的，但可以在集合論的一個更大系統中證明為真。

在電腦科學中用到的Kruskal的樹問題，也是在皮亞諾公理中不確定而在集合論中可證明的。

古德斯坦定理是一個關於自然數的相對簡單的命題，它在皮亞諾算術中是不確定的。

古格里·錢頓（Gregory Chaitin）在演算法資訊理論中構造了一個不確定命題，即「Chaitin隨機數Ω的第n個字節是否為0」這樣的命題在ZFC內是不可判定的。

計算邏輯中的停機問題不可解，亦是哥德爾不完備定理的一種表現形式。

## 對哥德爾定理的一些誤解

以下列出的誤解都是針對第一條定理而產生的。

- 該定理並不意味著任何公理系統都是不完備的。例如，歐幾里得幾何可以被一階公理化為一個完備的系統（事實上，歐幾里得的原創公理集已經非常接近於完備的系統。所缺少的公理是非常直觀的，以至於直到出現了形式化證明之後才注意到需要它們）。
- 該定理需假設公理系統可以「定義」自然數。就算這些系統擁有包括自然數作為子集的模型，也不一定就能定義自然數。必須透過公理和一階邏輯，在系統中表達出「x是一個自然數」這個概念才行。有許多系統包含自然數，卻是完備的。例如，塔斯基（Tarski）證明了實數和複數理論都是完備的一階公理化系統。

## 討論和推論

不完備性的結論影響了數學哲學以及形式化主義（使用形式符號描述原理）中的一些觀點。第一定理可以被解釋為：「不存在一個萬能的公理系統，使得其既能夠證明一切數學真理，又能證偽任何謬誤。」

以下對第二定理的另一種說法甚至更令人不安：

如果一個（強度足以證明基本算術公理的）公理系統可以用來證明它自身的相容性，那麼它是不相容的。

於是，為了確立系統S的相容性，就要構建另一個系統T，但是T中的證明並不是完全可信的，除非不使用S就能確立T的相容性。舉個例子，自然數上的皮亞諾公理的相容性可以在集合論中證明，但不能單獨在自然數理論範圍內證明。這對大衛·希爾伯特的著名的未解決的23個數學問題中的第二個給出了一個否定回答。

理論上，哥德爾理論仍留下了一線希望：也許可以給出一個演算法判定一個給定的命題是否是不確定的，讓數學家可以忽略掉這些不確定的命題。然而，對可判定性問題的否定回答表明不存在這樣的演算法。

值得注意的是，符合哥德爾不完備定理的系統，必須要蘊涵皮亞諾算術公理以承載對第一不完備定理證明過程的編碼。基本上，這就要求系統能將一些基本操作例如加法和乘法形式化，例如在魯賓遜算術Q中那樣。有一些更弱的公理系統是相容而且完備的，例如Presburger算術，它包括所有的一階邏輯的真命題和關於加法的真命題。

公理系統可能含有無窮條公理（例如皮亞諾算術就是這樣），但要哥德爾定理生效，必須存在檢驗證明是否正確的有效演算法。例如，可以將關於自然數的所有在標準模型中為真的一階語句組成一個集合。這個公理系統是完備的；哥德爾定理之所以無效，是因為不存在決定任何一條語句是否正確的有效演算法。從另一方面說，這個演算法的不存在正是哥德爾定理的直接結果。

另一個哥德爾定理不適用的特殊情況是：將關於自然數的所有語句首先按長度然後按字典順序排序，並從皮亞諾公理集開始，一個一個遍歷列表，如果發現一條語句既不能證明又不能否證，就將它作為公理加入。這樣得到的系統是完備的，兼容的，並且是足夠強大的，但不是遞歸可枚舉的。

哥德爾本人只證明了以上定理的一個較弱版本；以上定理的第一個證明是羅素（Russel）於1936年給出的。

基本上，第一定理的證明是通過在形式公理系統中構造如下命題

𝑝 = 「此命題是不可證明的」

來完成的。這樣，它可以看成是說謊者悖論的一個現代變種。

如果公理系統是相容的，哥德爾證明了𝑝（及其否定）不能在系統內證明。因此p是真命題（p聲稱它不可證明，而它確實不能），儘管其證明不能在系統內形式化。請注意將𝑝作為公理加入系統並不能解決問題：擴大了的系統中會有另一個哥德爾語句出現。

羅傑·彭羅斯聲稱「可被機械地證明的」和「對人類來說看起來是真的」的這一區別，表明了人類智能在本質上不同於機械過程。這一觀點未被普遍接受，因為正如馬文·閔斯基所指出的，人類智能有犯錯誤和理解不相容和謬誤句子的能力。但馬文·閔斯基透露說庫爾特·哥德爾私下告訴他，他相信人類有一種到達真理的直覺方法，但因為跟電腦式的方法不同，人類可以知道為真的事情並不受他的定理限制。

對以上認為該定理揭示了人類具有超出形式邏輯之能力的這種觀點，也可以作如下評論：p無法被證明，也無法被證偽，因為無法知道系統是否是相容的。因此實際上在此公理系統可證明範圍以外的真命題不在考慮範圍之內。於是可以說明一個命題：

要麼𝑝在系統內部無法證明，要麼該系統是不相容的。

這樣的命題之前已經在系統內部被證明。實際上，這樣的證明可以如下給出。

## 第一不完備定理的證明要點

證明目標：在任何足夠強大且一致的遞歸可枚舉公理系統中，必定存在一個命題，它既不能被證明為真，也不能被證明為假。證明的核心步驟如下：

### 1. 哥德爾編碼

哥德爾的關鍵想法是：將數學命題、證明步驟和演繹規則轉換為數字，從而將數理邏輯轉化為數論問題。

- 透過哥德爾編碼，可以把每個數學語句、證明、證明步驟用一個數字來表示，這些數字稱為哥德爾數（Gödel Number）。
- 這樣一來，「某個語句有證明」的性質，就變成一個關於自然數的可計算性質。

### 2. 構造自指命題

哥德爾構造了一個特殊的命題 G，它的語意是：「本命題不可證明」形式化來說，這是利用"對角化法（Diagonalization）"構造出的命題，類似於「這句話是錯的」的悖論，但這次是在數學系統內嚴格定義的。

- 具體而言，哥德爾引入了一個公式 Proof(x, y)，表示「數字編碼為 x 的命題由編碼為 y 的證明所證明」。
- 透過對角化技術，哥德爾構造出一個命題 G，其含義為： ¬Proof(Go¨delNumber(G),y) 這表示 G 無法在系統內被證明。

### 3. 分析命題 G 的真偽

考慮兩種情況：

- 若系統可以證明 G，則 G 斷言「G 不能被證明」，產生矛盾。
- 因此，G 不能被證明。
- 如果系統能夠證明 ¬G（即 G 是假的），那麼這表示 G 是假的，這意味著 G 是可證的，矛盾！
- 因此，G 也不能被證偽。

由以上可知，G 既無法被證明為真，也無法被證明為假，這證明了系統的不完備性。

## 第二不完備定理的證明要點

第二不完備定理是第一定理的延伸，主要說明：任何足夠強大且一致的系統都無法證明自身的一致性。大致證明思路：

- 利用第一不完備定理，已知存在某個命題 G，它在系統內是無法證明的。
- 如果系統能夠證明自身的一致性（即「系統無矛盾」），則可以藉由此推導出 G 是真的，從而證明 G。
- 但 G 是不可證的，這導致矛盾，因此「系統能證明自身一致性」的假設不成立。

因此，系統無法證明自身的一致性，這表明如果想確認一個系統是無矛盾的，就需要依賴一個更強的系統，而不是該系統本身。

## 與不確定性原理的關係

有學者指出不完備定理和不確定性原理有某種聯繫。

## 外部連結

- K. Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik, 38 (1931), pp. 173-198. Translated in van Heijenoort: From Frege to Gödel. Harvard University Press, 1971.
- B. Rosser: Extensions of some theorems of Gödel and Church. Journal of Symbolic Logic, 1 (1936), N1, pp. 87-91
- Karl Podnieks: Around Goedel's Theorem, http://www.ltn.lv/~podnieks/gt.html
- D. Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid, 1979, ISBN 0-465-02685-0. (1999 reprint: ISBN 0-465-02656-7).
- Ernest Nagel, James Roy Newman, Douglas R. Hofstadter: Gödel's Proof, revised edition (2002). ISBN 0-8147-5816-9.
- Hilbert's second problem（English translation）
- Norbert Domeisen, Logik der Antinomien. Bern etc.: Peter Lang. 142 S. 1990. (ISBN 3-261-04214-1), Zentralblatt MATH