基本介紹
- 中文名：哥德爾不完全性定理
- 外文名：Goedel
- 時間：1931年
- 提出：哥德爾
- 又稱：不完備定理
- 分類：數學 邏輯學
簡介,內容,第一定理,第二定理,引入,由來,誤解,推論,影響,
簡介
哥德爾是奧地利裔美國著名數學家，不完備性定理是他在1931年提出來的。這一理論使數學基礎研究發生了劃時代的變化，更是現代邏輯史上很重要的一座里程碑。該定理與塔爾斯基的形式語言的真理論，圖靈機和判定問題，被讚譽為現代邏輯科學在哲學方面的三大成果。哥德爾證明了任何一個形式系統，只要包括了簡單的初等數論描述，而且是自洽的，它必定包含某些系統內所允許的方法既不能證明真也不能證偽的命題。
哥德爾是20世紀最偉大的數學家和邏輯學家。在邏輯學中的地位，一般都將他與亞里士多德和萊布尼茲相比；在數學中的地位，愛因斯坦把哥德爾的貢獻與他本人對物理學的貢獻相提並論。1952年6月美國哈佛大學授予哥德爾榮譽理學學位時，稱他為“20世紀最有意義的數學真理的發現者”。在哥德爾所發現的被稱為“20世紀最有意義的數學真理”當中，最傑出、最具有有代表性、最有震撼力的是哥德爾不完全性定理。
內容
第一定理
任意一個包含一階謂詞邏輯與初等數論的形式系統，都存在一個命題，它在這個系統中既不能被證明為真，也不能被證明為否。
第二定理
如果系統S含有初等數論，當S無矛盾時，它的無矛盾性不可能在S內證明。
引入
悖論就是邏輯上的自相矛盾。
本命題是假命題
這種悖論屬於語義悖論。悖論的種類還有循環悖論等。此處從略。
由來
20世紀，一小部分聰明人才隱約覺察到，在悖論中有著一些深刻的數學理論。
事情要從崇尚理性的文藝復興時期談起，當時的學者如笛卡兒、萊布尼茨等都想創造一個理論解決一切問題。萊布尼茨甚至構想把邏輯學用數學符號表示，以後每逢爭論，拿支筆一算就見分曉了。事實證明，萊布尼茨的對符號邏輯的建立起了很大作用。
值得指出的是，希爾伯特所說的公理不是我們通常認為的公理，而是經過了徹底的形式化。他們存在於一門叫做元數學的分支中。元數學與一般數學理論的關係有點像計算機中應用程式和普通檔案的關係。
希爾伯特的計畫也確實有一定的進展，幾乎全世界的數學家都樂觀地看著數學大廈即將竣工。正當一切都越來越明朗之際，突然一聲晴天霹靂。1931年，在希爾伯特提出計畫不到3年，年輕的哥德爾就使希爾伯特的夢想變成了令人沮喪的噩夢。哥德爾證明：任何無矛盾的公理體系，只要包含初等算術的陳述，則必定存在一個不可判定命題，用這組公理不能判定其真假。也就是說，“無矛盾”和“完備”是不能同時滿足的！這便是聞名於世的哥德爾不完全性定理。
誤解
由於哥德爾的第一條定理有不少誤解。我們舉出一些例子：
該定理並不意味著任何有意義的公理系統都是不完備的。該定理需假設公理系統可以“定義”自然數。不過並非所有系統都能定義自然數，就算這些系統擁有包括自然數作為子集的模型。例如，歐幾里得幾何可以被一階公理化為一個完備的系統（事實上，歐幾里得的原創公理集已經非常接近於完備的系統。所缺少的公理是非常直觀的，以至於直到出現了形式化證明之後才注意到需要它們），塔爾斯基（Tarski）證明了實數和複數理論都是完備的一階公理化系統。這理論用在人工智慧上，則指出有些道理可能是我們能夠判別，但機器單純用一階公理化系統斷卻無法得知的道理。不過機器可以用非一階公理化系統，例如實驗、經驗。
推論
不完備性的結論影響了數學哲學以及形式化主義（使用形式符號描述原理）中的一些觀點。我們可以將第一定理解釋為“我們永遠不能發現一個萬能的公理系統能夠證明一切數學真理，而不能證明任何謬誤”
以下對第二定理的另一種說法甚至更令人不安：
如果一個（強度足以證明基本算術公理的）公理系統可以用來證明它自身的相容性，那么它是不相容的。於是，為了確立系統S的相容性，就要構建另一個系統T，但是T中的證明並不是完全可信的，除非不使用S就能確立T的相容性。舉個例子，自然數上的皮亞諾公理的相容性可以在集合論中證明，但不能單獨在自然數理論範圍內證明。這對大衛·希爾伯特的著名的未解決的23個數學問題中的第二個給出了一個否定回答。
理論上，哥德爾理論仍留下了一線希望：也許可以給出一個算法判定一個給定的命題是否是不確定的，讓數學家可以忽略掉這些不確定的命題。然而，對可判定性問題的否定回答表明不存在這樣的算法。（此處的算法為嚴格定義，要求對任何輸入都能在有限時間內停機）
要注意哥德爾理論只適用於較強的公理系統。“較強”意味著該理論包含了足夠的算術以便承載對第一不完備定理證明過程的編碼。基本上，這就要求系統能將一些基本操作例如加法和乘法形式化，例如在魯賓遜算術Q中那樣。有一些更弱的公理系統是相容而且完備的，例如Presburger算術，它包括所有的一階邏輯的真命題和關於加法的真命題。
另一個哥德爾定理不適用的特殊情況是：將關於自然數的所有語句首先按長度然後按字典順序排序，並從皮亞諾公理集開始，一個一個遍歷列表，如果發現一條語句既不能證明又不能否證，就將它作為公理加入。這樣得到的系統是完備的，兼容的，並且是足夠強大的，但不是遞歸可枚舉的。
哥德爾本人只證明了以上定理的一個較弱版本；以上定理的第一個證明是羅梭(Russel)於1936年給出的。
基本上，第一定理的證明是通過在形式公理系統中構造如下命題
p = “此命題是不可證明的”來完成的。這樣，它可以看成是說謊者悖論的一個現代變種。
如果公理系統是相容的，哥德爾證明了p（及其否定）不能在系統內證明。因此p是真命題（p聲稱它不可證明，而它確實不能），儘管其證明不能在系統內形式化。請注意將p作為公理加入系統並不能解決問題：擴大了的系統中會有另一個哥德爾語句出現。
羅傑·彭羅斯聲稱“可被機械地證明的”和“對人類來說看起來是真的”的這一區別表明人類智慧型不同於自然的無意識過程。這一觀點未被普遍接受，因為正如Marvin Minsky所指出的，人類智慧型有犯錯誤和理解不相容和謬誤句子的能力。但Marvin Minsky透露說哥德爾私下告訴他，他相信人類有一種到達真理的直覺方法，但因為跟計算機式的方法不同，人類可以知道為真的事情並不受他的定理限制。
對以上認為該定理揭示了人類具有超出形式邏輯之能力的這種觀點也可以作如下評論：我們其實不知道p是真是假，因為我們並不（也無法）知道系統是否是相容的。因此實際上我們並不知道系統之外的任何真理。我們所確知的只有這樣一個命題：
要么p在系統內部無法證明，要么該系統是不相容的。這樣的命題之前已經在系統內部被證明。實際上，這樣的證明已經給出。
影響
哥德爾不完全性定理一舉粉碎了數學家兩千年來的信念。他告訴我們，真與可證是兩個概念。可證的一定是真的，但真的不一定可證。某種意義上，悖論的陰影將永遠伴隨著我們。無怪乎大數學家外爾發出這樣的感嘆：“上帝是存在的，因為數學無疑是相容的；魔鬼也是存在的，因為我們不能證明這種相容性。”
但是哥德爾不完全性定理的影響遠遠超出了數學的範圍。它不僅使數學、邏輯學發生革命性的變化，引發了許多富有挑戰性的問題，而且還涉及哲學、語言學和計算機科學，甚至宇宙學。2002年8月17日，著名宇宙學家霍金在北京舉行的國際弦理論會議上發表了題為《哥德爾與M理論》的報告，認為建立一個單一的描述宇宙的大統一理論是不太可能的，這一推測也正是基於哥德爾不完全性定理。
有意思的是，在現今十分熱門的人工智慧領域，哥德爾不完全性定理是否適用也成為了人們議論的焦點。1961年，牛津大學的哲學家盧卡斯提出，根據哥德爾不完全性定理，機器不可能具有人的心智。他的觀點激起了很多人反對。他們認為，哥德爾不完全性定理與機器有無心智其實沒有關係，但哥德爾不完全性定理對人的限制，同樣也適用於機器倒是事實。
哥德爾不完全性定理的影響如此之廣泛，難怪哥德爾會被看作當代最有影響力的智慧巨人之一，受到人們的永恆懷念。美國《時代》雜誌曾評選出20世紀100個最偉大的人物，在數學家中，排在第一的就是哥德爾。
