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