哥德爾是奧地利裔美國著名數(shù)學家，不完備性定理是他在1931年提出來的。這一理論使數(shù)學基礎(chǔ)研究發(fā)生了劃時代的變化，更是現(xiàn)代邏輯史上很重要的一座里程碑。

該定理與塔爾斯基的形式語言的真理論，圖靈機和判定問題，被贊譽為現(xiàn)代邏輯科學在哲學方面的三大成果。

哥德爾證明了任何一個形式系統(tǒng)，只要包括了簡單的初等數(shù)論描述，而且是自洽的，它必定包含某些系統(tǒng)內(nèi)所允許的方法既不能證明真也不能證偽的命題。

哥德爾是20世紀最偉大的數(shù)學家和邏輯學家。在邏輯學中的地位，一般都將他與亞里士多德和萊布尼茲相比；在數(shù)學中的地位，愛因斯坦把哥德爾的貢獻與他本人對物理學的貢獻相提并論。1952年6月美國哈佛大學授予哥德爾榮譽理學學位時，稱他為“20世紀最有意義的數(shù)學真理的發(fā)現(xiàn)者”。在哥德爾所發(fā)現(xiàn)的被稱為“20世紀最有意義的數(shù)學真理”當中，最杰出、最具有有代表性、最有震撼力的是哥德爾不完全性定理[1] 。

內(nèi)容：

第一定理

任意一個包含一階謂詞邏輯與初等數(shù)論的形式系統(tǒng)，都存在一個命題，它在這個系統(tǒng)中既不能被證明為真，也不能被證明為否。

第二定理

如果系統(tǒng)S含有初等數(shù)論，當S無矛盾時，它的無矛盾性不可能在S內(nèi)證明。

引入

悖論就是邏輯上的自相矛盾。

最古老的悖論是兩千多年前的“說謊者悖論”，若你說它是假命題的話，就可推出它是真命題，反之亦然。其最簡形式就是：

本命題是假命題

這種悖論屬于語義悖論。悖論的種類還有循環(huán)悖論等。此處從略。

由來：

20世紀，一小部分聰明人才隱約覺察到，在悖論中有著一些深刻的數(shù)學理論。

事情要從崇尚理性的文藝復(fù)興時期談起，當時的學者如笛卡兒、萊布尼茨等都想創(chuàng)造一個理論解決一切問題。萊布尼茨甚至設(shè)想把邏輯學用數(shù)學符號表示，以后每逢爭論，拿支筆一算就見分曉了。事實證明，萊布尼茨的對符號邏輯的建立起了很大作用。

萊布尼茨太超前了，沒能完成他的夙愿。又過了200年，著名學者康托爾提出集合論，為統(tǒng)一數(shù)學提供了一線希望。

集合論的出現(xiàn)，為近代數(shù)學的發(fā)展提供了有力的工具。就在數(shù)學家躊躇滿志的時候，集合論中出現(xiàn)了悖論?？低袪栕约壕桶l(fā)現(xiàn)了康托爾悖論（包含一切集合的集合是否存在？），更嚴重的是羅素悖論，其中涉及的是以自己為元素的集合。這被稱為“第三次數(shù)學危機”。后來這種定義被公理排斥掉了，危機得以解決。

20世紀20年代，在集合論不斷發(fā)展的基礎(chǔ)上，大數(shù)學家希爾伯特向全世界的數(shù)學家拋出了個宏偉計劃，其大意是建立一組公理體系，使一切數(shù)學命題原則上都可由此經(jīng)有限步推定真?zhèn)危@叫做公理體系的“完備性”；希爾伯特還要求公理體系保持“獨立性”（即所有公理都是互相獨立的，使公理系統(tǒng)盡可能的簡潔）和“無矛盾性”（即相容性，不能從公理系統(tǒng)導出矛盾）。

值得指出的是，希爾伯特所說的公理不是我們通常認為的公理，而是經(jīng)過了徹底的形式化。他們存在于一門叫做元數(shù)學的分支中。元數(shù)學與一般數(shù)學理論的關(guān)系有點像計算機中應(yīng)用程序和普通文件的關(guān)系。

希爾伯特的計劃也確實有一定的進展，幾乎全世界的數(shù)學家都樂觀地看著數(shù)學大廈即將竣工。正當一切都越來越明朗之際，突然一聲晴天霹靂。1931年，在希爾伯特提出計劃不到3年，年輕的哥德爾就使希爾伯特的夢想變成了令人沮喪的噩夢。哥德爾證明：任何無矛盾的公理體系，只要包含初等算術(shù)的陳述，則必定存在一個不可判定命題，用這組公理不能判定其真假。也就是說，“無矛盾”和“完備”是不能同時滿足的！這便是聞名于世的哥德爾不完全性定理。

由于哥德爾的第一條定理有不少誤解。我們舉出一些例子：

該定理并不意味著任何有意義的公理系統(tǒng)都是不完備的。該定理需假設(shè)公理系統(tǒng)可以“定義”自然數(shù)。不過并非所有系統(tǒng)都能定義自然數(shù)，就算這些系統(tǒng)擁有包括自然數(shù)作為子集的模型。例如，歐幾里得幾何可以被一階公理化為一個完備的系統(tǒng)（事實上，歐幾里得的原創(chuàng)公理集已經(jīng)非常接近于完備的系統(tǒng)。所缺少的公理是非常直觀的，以至于直到出現(xiàn)了形式化證明之后才注意到需要它們），塔爾斯基（Tarski）證明了實數(shù)和復(fù)數(shù)理論都是完備的一階公理化系統(tǒng)。這理論用在人工智能上，則指出有些道理可能是我們能夠判別，但機器單純用一階公理化系統(tǒng)斷卻無法得知的道理。不過機器可以用非一階公理化系統(tǒng)，例如實驗、經(jīng)驗。

推論：不完備性的結(jié)論影響了數(shù)學哲學以及形式化主義（使用形式符號描述原理）中的一些觀點。我們可以將第一定理解釋為“我們永遠不能發(fā)現(xiàn)一個萬能的公理系統(tǒng)能夠證明一切數(shù)學真理，而不能證明任何謬誤”

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

如果一個（強度足以證明基本算術(shù)公理的）公理系統(tǒng)可以用來證明它自身的相容性，那么它是不相容的。于是，為了確立系統(tǒng)S的相容性，就要構(gòu)建另一個系統(tǒng)T，但是T中的證明并不是完全可信的，除非不使用S就能確立T的相容性。舉個例子，自然數(shù)上的皮亞諾公理的相容性可以在集合論中證明，但不能單獨在自然數(shù)理論范圍內(nèi)證明。這對大衛(wèi)·希爾伯特的著名的未解決的23個數(shù)學問題中的第二個給出了一個否定回答。

理論上，哥德爾理論仍留下了一線希望：也許可以給出一個算法判定一個給定的命題是否是不確定的，讓數(shù)學家可以忽略掉這些不確定的命題。然而，對可判定性問題的否定回答表明不存在這樣的算法。（此處的算法為嚴格定義，要求對任何輸入都能在有限時間內(nèi)停機）

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

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

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

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

基本上，第一定理的證明是通過在形式公理系統(tǒng)中構(gòu)造如下命題

p = “此命題是不可證明的”來完成的。這樣，它可以看成是說謊者悖論的一個現(xiàn)代變種。

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

羅杰·彭羅斯聲稱“可被機械地證明的”和“對人類來說看起來是真的”的這一區(qū)別表明人類智能不同于自然的無意識過程。這一觀點未被普遍接受，因為正如Marvin Minsky所指出的，人類智能有犯錯誤和理解不相容和謬誤句子的能力。但Marvin Minsky透露說哥德爾私下告訴他，他相信人類有一種到達真理的直覺方法，但因為跟計算機式的方法不同，人類可以知道為真的事情并不受他的定理限制。

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

要么p在系統(tǒng)內(nèi)部無法證明，要么該系統(tǒng)是不相容的。這樣的命題之前已經(jīng)在系統(tǒng)內(nèi)部被證明。實際上，這樣的證明已經(jīng)給出。

哥德爾不完全性定理一舉粉碎了數(shù)學家兩千年來的信念。他告訴我們，真與可證是兩個概念?？勺C的一定是真的，但真的不一定可證。某種意義上，悖論的陰影將永遠伴隨著我們。無怪乎大數(shù)學家外爾發(fā)出這樣的感嘆：“上帝是存在的，因為數(shù)學無疑是相容的；魔鬼也是存在的，因為我們不能證明這種相容性?！?/p>

但是哥德爾不完全性定理的影響遠遠超出了數(shù)學的范圍。它不僅使數(shù)學、邏輯學發(fā)生革命性的變化，引發(fā)了許多富有挑戰(zhàn)性的問題，而且還涉及哲學、語言學和計算機科學，甚至宇宙學。2002年8月17日，著名宇宙學家霍金在北京舉行的國際弦理論會議上發(fā)表了題為《哥德爾與M理論》的報告，認為建立一個單一的描述宇宙的大統(tǒng)一理論是不太可能的，這一推測也正是基于哥德爾不完全性定理。

有意思的是，在現(xiàn)今十分熱門的人工智能領(lǐng)域，哥德爾不完全性定理是否適用也成為了人們議論的焦點。1961年，牛津大學的哲學家盧卡斯提出，根據(jù)哥德爾不完全性定理，機器不可能具有人的心智。他的觀點激起了很多人反對。他們認為，哥德爾不完全性定理與機器有無心智其實沒有關(guān)系，但哥德爾不完全性定理對人的限制，同樣也適用于機器倒是事實。

哥德爾不完全性定理的影響如此之廣泛，難怪哥德爾會被看作當代最有影響力的智慧巨人之一，受到人們的永恒懷念。美國《時代》雜志曾評選出20世紀100個最偉大的人物，在數(shù)學家中，排在第一的就是哥德爾。