哥德爾不完全性定理數(shù)理邏輯術(shù)語01簡介引入內(nèi)容由來目錄03020405誤解影響推論目錄0706基本信息哥德爾是奧地利裔美國著名數(shù)學(xué)家，不完備性定理是他在1931年提出來的。這一理論使數(shù)學(xué)基礎(chǔ)研究發(fā)生了劃時代的變化，更是現(xiàn)代邏輯史上很重要的一座里程碑。該定理與塔爾斯基的形式語言的真理論，圖靈機(jī)和判定問題，被贊譽(yù)為現(xiàn)代邏輯科學(xué)在哲學(xué)方面的三大成果。哥德爾證明了任何一個形式系統(tǒng)，只要包括了簡單的初等數(shù)論描述，而且是自洽的，它必定包含某些系統(tǒng)內(nèi)所允許的方法既不能證明真也不能證偽的命題。簡介簡介哥德爾是奧地利裔美國著名數(shù)學(xué)家，不完備性定理是他在1931年提出來的。這一理論使數(shù)學(xué)基礎(chǔ)研究發(fā)生了劃時代的變化，更是現(xiàn)代邏輯史上很重要的一座里程碑。該定理與塔爾斯基的形式語言的真理論，圖靈機(jī)和判定問題，被贊譽(yù)為現(xiàn)代邏輯科學(xué)在哲學(xué)方面的三大成果。哥德爾證明了任何一個形式系統(tǒng)，只要包括了簡單的初等數(shù)論描述，而且是自洽的，它必定包含某些系統(tǒng)內(nèi)所允許的方法既不能證明真也不能證偽的命題。哥德爾是20世紀(jì)最偉大的數(shù)學(xué)家和邏輯學(xué)家。在邏輯學(xué)中的地位，一般都將他與亞里士多德和萊布尼茲相比；在數(shù)學(xué)中的地位，愛因斯坦把哥德爾的貢獻(xiàn)與他本人對物理學(xué)的貢獻(xiàn)相提并論。1952年6月美國哈佛大學(xué)授予哥德爾榮譽(yù)理學(xué)學(xué)位時，稱他為“20世紀(jì)最有意義的數(shù)學(xué)真理的發(fā)現(xiàn)者”。在哥德爾所發(fā)現(xiàn)的被稱為“20世紀(jì)最有意義的數(shù)學(xué)真理”當(dāng)中，最杰出、最具有有代表性、最有震撼力的是哥德爾不完全性定理

。內(nèi)容第二定理第一定理內(nèi)容第一定理任意一個包含一階謂詞邏輯與初等數(shù)論的形式系統(tǒng)，都存在一個命題，它在這個系統(tǒng)中既不能被證明為真，也不能被證明為否。第二定理如果系統(tǒng)S含有初等數(shù)論，當(dāng)S無矛盾時，它的無矛盾性不可能在S內(nèi)證明。引入引入悖論就是邏輯上的自相矛盾。最古老的悖論是兩千多年前的“說謊者悖論”，若你說它是假命題的話，就可推出它是真命題，反之亦然。其最簡形式就是：本命題是假命題這種悖論屬于語義悖論。悖論的種類還有循環(huán)悖論等。此處從略。由來由來20世紀(jì)，一小部分聰明人才隱約覺察到，在悖論中有著一些深刻的數(shù)學(xué)理論。事情要從崇尚理性的文藝復(fù)興時期談起，當(dāng)時的學(xué)者如笛卡兒、萊布尼茨等都想創(chuàng)造一個理論解決一切問題。萊布尼茨甚至設(shè)想把邏輯學(xué)用數(shù)學(xué)符號表示，以后每逢爭論，拿支筆一算就見分曉了。事實證明，萊布尼茨的對符號邏輯的建立起了很大作用。萊布尼茨太超前了，沒能完成他的夙愿。又過了200年，著名學(xué)者康托爾提出集合論，為統(tǒng)一數(shù)學(xué)提供了一線希望。集合論的出現(xiàn)，為近代數(shù)學(xué)的發(fā)展提供了有力的工具。就在數(shù)學(xué)家躊躇滿志的時候，集合論中出現(xiàn)了悖論。康托爾自己就發(fā)現(xiàn)了康托爾悖論（包含一切集合的集合是否存在？），更嚴(yán)重的是羅素悖論，其中涉及的是以自己為元素的集合。這被稱為“第三次數(shù)學(xué)危機(jī)”。后來這種定義被公理排斥掉了，危機(jī)得以解決。20世紀(jì)20年代，在集合論不斷發(fā)展的基礎(chǔ)上，大數(shù)學(xué)家希爾伯特向全世界的數(shù)學(xué)家拋出了個宏偉計劃，其大意是建立一組公理體系，使一切數(shù)學(xué)命題原則上都可由此經(jīng)有限步推定真?zhèn)危@叫做公理體系的“完備性”；希爾伯特還要求公理體系保持“獨(dú)立性”（即所有公理都是互相獨(dú)立的，使公理系統(tǒng)盡可能的簡潔）和“無矛盾性”（即相容性，不能從公理系統(tǒng)導(dǎo)出矛盾）。值得指出的是，希爾伯特所說的公理不是我們通常認(rèn)為的公理，而是經(jīng)過了徹底的形式化。誤解誤解由于哥德爾的第一條定理有不少誤解。我們舉出一些例子：該定理并不意味著任何有意義的公理系統(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)。這理論用在人工智能上，則指出有些道理可能是我們能夠判別，但機(jī)器單純用一階公理化系統(tǒng)斷卻無法得知的道理。不過機(jī)器可以用非一階公理化系統(tǒng)，例如實驗、經(jīng)驗。推論推論不完備性的結(jié)論影響了數(shù)學(xué)哲學(xué)以及形式化主義（使用形式符號描述原理）中的一些觀點(diǎn)。我們可以將第一定理解釋為“我們永遠(yuǎn)不能發(fā)現(xiàn)一個萬能的公理系統(tǒng)能夠證明一切數(shù)學(xué)真理，而不能證明任何謬誤”以下對第二定理的另一種說法甚至更令人不安：如果一個（強(qiáng)度足以證明基本算術(shù)公理的）公理系統(tǒng)可以用來證明它自身的相容性，那么它是不相容的。于是，為了確立系統(tǒng)S的相容性，就要構(gòu)建另一個系統(tǒng)T，但是T中的證明并不是完全可信的，除非不使用S就能確立T的相容性。舉個例子，自然數(shù)上的皮亞諾公理的相容性可以在集合論中證明，但不能單獨(dú)在自然數(shù)理論范圍內(nèi)證明。這對大衛(wèi)·希爾伯特的著名的未解決的23個數(shù)學(xué)問題中的第二個給出了一個否定回答。理論上，哥德爾理論仍留下了一線希望：也許可以給出一個算法判定一個給定的命題是否是不確定的，讓數(shù)學(xué)家可以忽略掉這些不確定的命題。然而，對可判定性問題的否定回答表明不存在這樣的算法。（此處的算法為嚴(yán)格定義，要求對任何輸入都能在有限時間內(nèi)停機(jī)）要注意哥德爾理論只適用于較強(qiáng)的公理系統(tǒng)?！拜^強(qiáng)”意味著該理論包含了足夠的算術(shù)以便承載對第一不完備定理證明過程的編碼?；旧?，這就要求系統(tǒng)能將一些基本操作例如加法和乘法形式化，例如在魯賓遜算術(shù)Q中那樣。有一些更弱的公理系統(tǒng)是相容而且完備的，例如Presburger算術(shù)，它包括所有的一階邏輯的真命題和關(guān)于加法的真命題。影響影響哥德爾不完全性定理一舉粉碎了數(shù)學(xué)家兩千年來的信念。他告訴我們，真與可證是兩個概念?？勺C的一定是真的，但真的不一定可證。某種意義上，悖論的陰影將永遠(yuǎn)伴隨著我們。無怪乎大數(shù)學(xué)家外爾發(fā)出這樣的感嘆：“上帝是存在的，因為數(shù)學(xué)無疑是相容的；魔鬼也是存在的，因為我們不能證明這種相容性。”但是哥德爾不完全性定理的影響遠(yuǎn)遠(yuǎn)超出了數(shù)學(xué)的范圍。它不僅使數(shù)學(xué)、邏輯學(xué)發(fā)生革命性的變化，引發(fā)了許多富有挑戰(zhàn)性的問題，而且還涉及哲學(xué)、語言學(xué)和計算機(jī)科學(xué)，甚至宇宙學(xué)。2002年8月17日，著名宇宙學(xué)家霍金在北京舉行的國際弦理論會議上發(fā)表了題為《哥德爾與M理論》的報告，認(rèn)為建立一個單一的描述宇宙的大統(tǒng)一理論是不太可能的，這一推測也正是基于哥德爾不完全性定理。有意思的是，在現(xiàn)今十分熱門的人工智能領(lǐng)域，哥德爾不完全性定理是否適用也成為了人們議論的焦點(diǎn)。1961年，牛津大學(xué)的哲學(xué)家盧卡斯提出，根據(jù)哥德爾不完全性定理，機(jī)器不可能具有人的心智。他的觀點(diǎn)激起了很多人反對。他們認(rèn)為，哥德爾不完全性定理