本頁使用了標題或全文手工轉換

哥德爾不完備定理

維基百科,自由的百科全書
前往: 導覽搜尋

數理邏輯中,哥德爾不完備定理庫爾特·哥德爾於1931年證明並發表的兩條定理。簡單地說,第一條定理指出:

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

這條定理是在數學界以外最著名的定理之一,也是誤解最多的定理之一。它是形式邏輯中的定理,所以容易被錯誤表述。有許多命題聽起來很像是哥德爾不完備定理,但事實上是錯誤的。稍後我們可以看到一些對哥德爾定理的誤解

把第一條定理的證明過程在體系內部形式化後,哥德爾證明了他的第二條定理。該定理指出:

任何相容形式系統,只要蘊涵皮亞諾算術公理,它就不能用於證明它本身的相容性。

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

哥德爾不完全性定理的證明思路[編輯]

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

哥德爾不完備定理的含義[編輯]

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

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

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

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

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

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

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

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

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

在計算機科學的語言中,哥德爾定理有另一種表述方式。在一階邏輯中,定理是遞迴可枚舉的:你可以編寫一個可以枚舉出其所有有效證明的程序。你可以問是否可以將結論加強為遞迴的:可以編寫一個在有限時間內判定命題真假的程序嗎?根據哥德爾定理,答案是一般來說不能。

不確定命題的例子[編輯]

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

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

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

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

Goodstein定理英語Goodstein's Theorem是一個關於自然數的相對簡單的命題,它在皮亞諾算術中是不確定的。

Gregory Chaitin算法資訊理論中構造了一個不確定命題,即「Chaitin隨機數Ω的第n個字節是否為0」這樣的命題在ZFC內是不可判定的。

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

對哥德爾定理的一些誤解[編輯]

哥德爾的第一條定理有不少誤解。我們就此稍作說明:

  1. 該定理並不意味著任何有趣的公理系統都是不完備的。例如,歐幾里得幾何可以被一階公理化為一個完備的系統(事實上,歐幾里得的原創公理集已經非常接近於完備的系統。所缺少的公理是非常直觀的,以至於直到出現了形式化證明之後才注意到需要它們)
  2. 該定理需假設公理系統可以「定義」自然數。就算這些系統擁有包括自然數作為子集的模型,也不一定就能定義自然數。必須透過公理和一階邏輯,在系統中表達出「x是一個自然數」這個概念才行。有許多系統包含自然數,卻是完備的。例如,塔斯基(Tarski)證明了實數複數理論都是完備的一階公理化系統。
  3. 這理論用在人工智慧上,則指出有些道理可能是我們能夠判別,但機器單純用一階公理化系統卻無法得知的道理。不過機器可以用非一階公理化系統,例如實驗、經驗。

討論和推論[編輯]

不完備性的結論影響了數學哲學以及形式化主義(使用形式符號描述原理)中的一些觀點。我們可以將第一定理解釋為「我們永遠不能發現一個萬能的公理系統能夠證明一切數學真理,而不能證明任何謬誤」
以下對第二定理的另一種說法甚至更令人不安:

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

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

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

要注意哥德爾理論只適用於較強的公理系統。「較強」意味著該理論包含了足夠的算術以便承載對第一不完備定理證明過程的編碼。基本上,這就要求系統能將一些基本操作例如加法和乘法形式化,例如在魯賓遜算術Q中那樣。有一些更弱的公理系統是相容而且完備的,例如Presburger算術英語Presburger arithmetic,它包括所有的一階邏輯的真命題和關於加法的真命題。

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

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

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

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

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

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

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

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

對以上認為該定理揭示了人類具有超出形式邏輯之能力的這種觀點,也可以作如下評論:我們其實不知道p是真是假,因為我們並不(也無法)知道系統是否是相容的。因此實際上我們並不知道系統之外的任何真理。我們所確知的只有這樣一個命題:

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

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

第一不完備定理的證明要點[編輯]

要充實對證明要點的描述,主要的問題在於:為了構造相當於「p是不可證明的」這樣的命題pp就必須包含有自身的引用,而這很容易陷入無窮循環。將要介紹的哥德爾巧妙的把戲,後來被艾倫·圖靈用於解決可判定性問題

首先,每個公式或者說可形式化的命題都被我們的系統賦予一個數,稱為哥德爾數,例如,假設形式系統有100個符號,用0至99對這些符號進行編碼,這樣,一個命題的公式就是一個位數為公式長度的100進位的整數,公式可以有不同的寫法,因此可以對應多個數,但每一個數或者不對應任何公式,如果對應某個公式,則只對應唯一的一個公式,可能有多個數對應同一個公式。因為系統包含所有正整數,因此也就足以表述公式的概念了。一個證明可以表示為一個有窮的命題序列,例如將推理過程表示為命題序列。用同樣的原理也可以將一個證明表示為一個正整數。當然,表示一個命題的正整數和表示一個證明的正整數具有不同的含義,因此不能混在一起。

F(x)這樣的公式含有一個自由變量x,它們稱為命題形式。一旦x被一個特定的數代替,它就馬上變成一個真正的特定命題,於是它要麼是在系統中可證明的,要麼不。命題形式自身並不是命題,因此不能被證明也不能被否證。但每一個命題形式F(x)都有一個哥德爾數,可用G(F)表示。自由變量的選擇與G(F)的賦值無關。

通過小心地分析系統的公理和推理規則,可以寫下一個命題形式P(x),它表示x是系統中一個可以證明的命題的哥德爾數。形式描述如下:如果x是一個可證明命題對應的哥德爾數,P(x)就可被證明,而其否定~P(x)則不能。(儘管這作為一個證明要點來說已經足夠,但在技術上卻不太嚴格。請參見哥德爾和羅素的有關論文,關鍵字是「omega-consistency」。)

現在,哥德爾的把戲來了:一個命題形式F(x)稱為不可自證的,若且唯若把命題形式F的哥德爾數G(F)代入F中所得的命題F(G(F))是不可證明的。這個定義可以形式化,於是可以構造一個命題形式SU(z),表示z是某個不可自證命題形式的哥德爾數。SU(z)的形式描述如下:

對某個命題形式F(x)有z = G(F),而且設y是命題F(G(F))的哥德爾數,則有~P(y)成立。

現在我們所要的語句p就可以如下定義:

p = SU(G(SU))

直觀上,當問到p是否為真的時候,我們是在問:「不可自證這個特性本身是不可自證的嗎?」這很容易讓人聯想到理髮師悖論,那個理髮師只替那些不替自己理髮的人理髮:他替自己理髮嗎?

現在讓我們假定公理系統是相容的。

如果p可以證明,於是SU(G(SU))為真,根據SU的定義,z = G(SU)就是某個不可自證命題形式的哥德爾數。於是SU就是不可自證的,根據不可自證的定義,SU(G(SU))是不可證明的。這一矛盾說明p是不可證明的。

如果p = SU(G(SU))的否定是可以證明的,則根據SU的定義,z = G(SU)就不是不可自證命題形式的哥德爾數。這意味著SU不是不可自證的。根據不可自證的定義,我們斷定SU(G(SU))是可以證明的,同樣得到矛盾。這說明p的否定也是不可證明的。

因此,p既不可在系統內證明也不可在系統內否證。

第二不完備定理的證明要點[編輯]

p是如上構造的不確定命題,且假定系統的相容性可以在系統內部證明。我們已經看到,如果系統是相容的,則p是不可自證的。這個證明過程可以在系統內部形式化,因此命題「p是不可證明的」或者「~P(p)」可以在系統內證明。

但是最後一個命題就等價於p自己(而且這種等價性可以在系統內部證明),從而p就可以在系統內證明。這一矛盾說明系統是不相容的。

與不確定性原理的關係[編輯]

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

參見[編輯]

參考資料[編輯]

  1. ^ 康托爾、哥德爾、圖靈——永恆的金色對角線
  2. ^ Gödel's incompleteness theorem
  3. ^ http://research.cs.queensu.ca/home/akl/cisc879/papers/SELECTED_PAPERS_FROM_VARIOUS_SOURCES/aqi4.pdf Algorithmic Randomness, Quantum Physics, and Incompleteness

外部連結[編輯]