哥德爾不完備定理
哥德爾不完全性定理的證明思路
只要證明了初等算數(shù)理論Π是不完全的,采用相同的方法就可以證明任何包含Π的形式理論都是不完全的
證明Π的不完全性的關(guān)鍵是在于構(gòu)造出初等算數(shù)語言?中的一個(gè)含義為真的語句Α,證明如果Α能被證明則將推出矛盾
包含初等算數(shù)理論的意義是它包含所有正整數(shù)(無窮元素)。而命題和證明都可以被映射到正整數(shù)。另一方面,它還支持歸納集,即及由一些初始元素及新元素構(gòu)成的集合,而新元素都是由初始元素歸納(運(yùn)算)而得的。形式理論由公理及定理構(gòu)成,定理可以看作是公理及已知定理的歸納,因而形式理論本身可以表示成以某些正整數(shù)為初始元素的某種歸納集。這使得可證性變?yōu)樗阈g(shù)命題
所構(gòu)造的語句Α類似于“說謊者悖論”(即“我在說謊”),但Α是“本語句不可證”。對這一形式化的Α如果假設(shè)Α可證將推出矛盾,但假設(shè)Α不可證卻不能推出矛盾,所以Α不是一個(gè)悖論。而Α的含義是它不可證,而它又被證明是不可證的,因此Α是個(gè)不可證的真命題
?不完全,那么包含?的Π不完全,那么包含Π的形式系統(tǒng)不完全。得證。
哥德爾不完備定理的含義
哥德爾定理巧妙地利用了命題的“真值為真”和“含義為真”的區(qū)別,從而構(gòu)造出了含義為真而真值不可證的命題,又避免了悖論的陷阱。形式邏輯系統(tǒng)的命題本身是沒有含義的。命題只有真值而沒有含義。公理命題的真值為真。其它命題的真值為真當(dāng)且僅當(dāng)該命題可以被證明,為假當(dāng)且僅當(dāng)該命題的非可以被證明。當(dāng)形式邏輯系統(tǒng)被實(shí)際應(yīng)用時(shí),系統(tǒng)中的符號都被映射到實(shí)際概念上,從而有了語義。這種映射叫做一個(gè)模型。有了模型,命題就有了含義(語義)。例如,在ZF公理化集合論中,系統(tǒng)中的對象(object)被影射到“集合”這一概念,∈被映射到“屬于”這一概念就是模型的一個(gè)例子。而ZF公理化系統(tǒng)本身即使沒有模型也可以成立。如果換一個(gè)模型,形式系統(tǒng)沒變,只是它不再是集合論了。當(dāng)然,ZF公理化系統(tǒng)是為了集合論量身打造的,很適合于集合論。如果換一個(gè)模型,很難找到可理解的語義。但這說明了“真值為真”和“含義為真”是有區(qū)別的。
在大多數(shù)情況下,命題的“真值為真”和“含義為真”是一致的。例如,設(shè)A為一命題,則命題A??A的含義是“本命題A為假”,這時(shí)A的真值為真和含義為真是一致的,結(jié)果形成了否定循環(huán)而構(gòu)成了悖論。而邏輯系統(tǒng)不能含有悖論,所以這樣的A應(yīng)該是構(gòu)造不出來得。哥德爾定理證明的巧妙之處就在于將悖論的“為假”改為了“為不可證”使得真值為真和含義為真成為不一致(含義為真是不可證,而真值為真或假都是可證),因而產(chǎn)生了自我否定又避免了循環(huán)的效果,也就避免了悖論。
理解了這一點(diǎn),就可以理解哥德爾定理不是說存在真值為真又不可證這種自相矛盾的悖論命題(實(shí)際上應(yīng)該構(gòu)造不出來),而是存在含義為真但不可證(即真值不可知)的命題。哥德爾定理也不只是說存在既不可證真,也不可證偽的命題,這樣的命題有很多,哥德爾定理的重要之處在于它還說了該不可證的命題是含義為真的。
哥德爾定理是一階邏輯的定理,故最終只能在這個(gè)框架內(nèi)理解。在形式邏輯中,數(shù)學(xué)命題及其證明都是用一種符號語言描述的,在這里我們可以機(jī)械地檢查每個(gè)證明的有效性,于是便可以從一組公理開始無可辯駁地證明一條定理。理論上,這樣的證明可以在電腦上檢查,事實(shí)上這樣的有效性檢查程序也已經(jīng)有了。
為了這個(gè)過程得以進(jìn)行,我們需要知道手頭有什么樣的公理。我們可以從一組有限的公理集開始,例如歐幾里得幾何?;蛘吒话愕?,我們可以允許無窮的公理列表,只要能機(jī)械地判斷給定的命題是否是一條公理就行。在計(jì)算機(jī)科學(xué)里面,這被稱為公理的遞歸集。盡管無窮的公理列表聽起來有些奇怪,實(shí)際上自然數(shù)的通常理論中,稱為皮亞諾公理的就是如此。
哥德爾的第一條不完備定理表明任何一個(gè)允許定義自然數(shù)的體系必定是不完全的:它包含了不能在此體系內(nèi)以一階謂詞邏輯形式證明的命題,并且該命題的否命題也不能在該體系內(nèi)以一階謂詞邏輯的形式證明。
存在不完備的體系這一事實(shí)本身并不使人感到特別驚訝。例如,在歐幾里得幾何中,如果把平行公設(shè)去掉,就得到一個(gè)不完備的體系。不完備的體系可能只意味著尚未找出所有必須的公理而已。
但哥德爾揭示的是在多數(shù)情況下,例如在數(shù)論或者實(shí)分析中,你永遠(yuǎn)不能找出公理的完整集合。每一次你將一個(gè)命題作為公理加入,將總有另一個(gè)命題出現(xiàn)在你的所能形式證明的范圍之外。
你可以加入無窮條公理(例如,所有真命題)到公理列表中,確保所有命題都可證明為真或假,但你得到的公理列表將不再是遞歸集。給出任意一條命題,將沒有機(jī)械的方法判定它是否是系統(tǒng)的一條公理。如果給出一個(gè)證明,一般來說也無法檢查它是否正確。
在計(jì)算機(jī)科學(xué)的語言中,哥德爾定理有另一種表述方式。在一階邏輯中,定理是遞歸可枚舉的:你可以編寫一個(gè)可以枚舉出其所有有效證明的程序。你可以問是否可以將結(jié)論加強(qiáng)為遞歸的:可以編寫一個(gè)在有限時(shí)間內(nèi)判定命題真假的程序嗎?根據(jù)哥德爾定理,答案是一般來說不能。
不確定命題的例子
哥德爾和保羅·寇恩得出的一些結(jié)果結(jié)合起來給出了不確定命題(既不能證明也不能否證的命題)的一個(gè)實(shí)際例子:選擇公理和連續(xù)統(tǒng)假設(shè)都是集合論的標(biāo)準(zhǔn)公理系統(tǒng)內(nèi)的不確定命題。
在1973年,同調(diào)代數(shù)中的懷特海問題被證明是集合論中的不確定命題。
1977年,Paris和Harrington證明了組合論中的一個(gè)命題,拉姆賽理論的某個(gè)版本,在皮阿諾公理給出的算術(shù)公理系統(tǒng)中是不確定的,但可以在集合論的一個(gè)更大體系中證明為真。
在計(jì)算機(jī)科學(xué)中用到的Kruskal的樹問題,也是在皮亞諾公理中不確定而在集合論中可證明的。
Goodstein定理(英語:Goodstein"s Theorem)是一個(gè)關(guān)于自然數(shù)的相對簡單的命題,它在皮亞諾算術(shù)中是不確定的。
Gregory Chaitin在算法信息論中構(gòu)造了一個(gè)不確定命題,即“Chaitin隨機(jī)數(shù)Ω的第n個(gè)字節(jié)是否為0”這樣的命題在ZFC內(nèi)是不可判定的。
計(jì)算邏輯中的停機(jī)問題不可解,亦是哥德爾不完備定理的一種表現(xiàn)形式。
對哥德爾定理的一些誤解
哥德爾的第一條定理有不少誤解。我們就此稍作說明:
該定理并不意味著任何有趣的公理系統(tǒng)都是不完備的。例如,歐幾里得幾何可以被一階公理化為一個(gè)完備的系統(tǒng)(事實(shí)上,歐幾里得的原創(chuàng)公理集已經(jīng)非常接近于完備的系統(tǒng)。所缺少的公理是非常直觀的,以至于直到出現(xiàn)了形式化證明之后才注意到需要它們)
該定理需假設(shè)公理系統(tǒng)可以“定義”自然數(shù)。就算這些系統(tǒng)擁有包括自然數(shù)作為子集的模型,也不一定就能定義自然數(shù)。必須透過公理和一階邏輯,在系統(tǒng)中表達(dá)出“x是一個(gè)自然數(shù)”這個(gè)概念才行。有許多系統(tǒng)包含自然數(shù),卻是完備的。例如,塔斯基(Tarski)證明了實(shí)數(shù)和復(fù)數(shù)理論都是完備的一階公理化系統(tǒng)。
這理論用在人工智能上,則指出有些道理可能是我們能夠判別,但機(jī)器單純用一階公理化系統(tǒng)卻無法得知的道理。不過機(jī)器可以用非一階公理化系統(tǒng),例如實(shí)驗(yàn)、經(jīng)驗(yàn)。
討論和推論
不完備性的結(jié)論影響了數(shù)學(xué)哲學(xué)以及形式化主義(使用形式符號描述原理)中的一些觀點(diǎn)。我們可以將第一定理解釋為“我們永遠(yuǎn)不能發(fā)現(xiàn)一個(gè)萬能的公理系統(tǒng)能夠證明一切數(shù)學(xué)真理,而不能證明任何謬誤” 以下對第二定理的另一種說法甚至更令人不安:
于是,為了確立系統(tǒng)S的相容性,就要構(gòu)建另一個(gè)系統(tǒng)T,但是T中的證明并不是完全可信的,除非不使用S就能確立T的相容性。舉個(gè)例子,自然數(shù)上的皮亞諾公理的相容性可以在集合論中證明,但不能單獨(dú)在自然數(shù)理論范圍內(nèi)證明。這對大衛(wèi)·希爾伯特的著名的未解決的23個(gè)數(shù)學(xué)問題中的第二個(gè)給出了一個(gè)否定回答。
理論上,哥德爾理論仍留下了一線希望:也許可以給出一個(gè)算法判定一個(gè)給定的命題是否是不確定的,讓數(shù)學(xué)家可以忽略掉這些不確定的命題。然而,對可判定性問題的否定回答表明不存在這樣的算法。
要注意哥德爾理論只適用于較強(qiáng)的公理系統(tǒng)?!拜^強(qiáng)”意味著該理論包含了足夠的算術(shù)以便承載對第一不完備定理證明過程的編碼?;旧?,這就要求系統(tǒng)能將一些基本操作例如加法和乘法形式化,例如在魯賓遜算術(shù)Q中那樣。有一些更弱的公理系統(tǒng)是相容而且完備的,例如Presburger算術(shù)(英語:Presburger arithmetic),它包括所有的一階邏輯的真命題和關(guān)于加法的真命題。
公理系統(tǒng)可能含有無窮條公理(例如皮亞諾算術(shù)就是這樣),但要哥德爾定理生效,必須存在檢驗(yàn)證明是否正確的有效算法。例如,可以將關(guān)于自然數(shù)的所有在標(biāo)準(zhǔn)模型中為真的一階語句組成一個(gè)集合。這個(gè)公理系統(tǒng)是完備的;哥德爾定理之所以無效,是因?yàn)椴淮嬖跊Q定任何一條語句是否公理的有效算法。從另一方面說,這個(gè)算法的不存在正是哥德爾定理的直接結(jié)果。
另一個(gè)哥德爾定理不適用的特殊情況是:將關(guān)于自然數(shù)的所有語句首先按長度然后按字典順序排序,并從皮亞諾公理集開始,一個(gè)一個(gè)遍歷列表,如果發(fā)現(xiàn)一條語句既不能證明又不能否證,就將它作為公理加入。這樣得到的系統(tǒng)是完備的,兼容的,并且是足夠強(qiáng)大的,但不是遞歸可枚舉的。
哥德爾本人只證明了以上定理的一個(gè)較弱版本;以上定理的第一個(gè)證明是羅梭(Russel)于1936年給出的。
基本上,第一定理的證明是通過在形式公理系統(tǒng)中構(gòu)造如下命題
來完成的。這樣,它可以看成是說謊者悖論的一個(gè)現(xiàn)代變種。
如果公理系統(tǒng)是相容的,哥德爾證明了p(及其否定)不能在系統(tǒng)內(nèi)證明。因此p是真命題(p聲稱它不可證明,而它確實(shí)不能),盡管其證明不能在系統(tǒng)內(nèi)形式化。請注意將p作為公理加入系統(tǒng)并不能解決問題:擴(kuò)大了的系統(tǒng)中會(huì)有另一個(gè)哥德爾語句出現(xiàn)。
羅杰·彭羅斯聲稱“可被機(jī)械地證明的”和“對人類來說看起來是真的”的這一區(qū)別,表明了人類智能在本質(zhì)上不同于機(jī)械過程。這一觀點(diǎn)未被普遍接受,因?yàn)檎鏜arvin Minsky 所指出的,人類智能有犯錯(cuò)誤和理解不相容和謬誤句子的能力。但Marvin Minsky透露說庫爾特·哥德爾私下告訴他,他相信人類有一種到達(dá)真理的直覺方法,但因?yàn)楦?jì)算機(jī)式的方法不同,人類可以知道為真的事情并不受他的定理限制。
對以上認(rèn)為該定理揭示了人類具有超出形式邏輯之能力的這種觀點(diǎn),也可以作如下評論:我們其實(shí)不知道p是真是假,因?yàn)槲覀儾⒉唬ㄒ矡o法)知道系統(tǒng)是否是相容的。因此實(shí)際上我們并不知道系統(tǒng)之外的任何真理。我們所確知的只有這樣一個(gè)命題:
這樣的命題之前已經(jīng)在系統(tǒng)內(nèi)部被證明。實(shí)際上,這樣的證明可以如下給出。
第一不完備定理的證明要點(diǎn)
要充實(shí)對證明要點(diǎn)的描述,主要的問題在于:為了構(gòu)造相當(dāng)于“p是不可證明的”這樣的命題p,p就必須包含有自身的引用,而這很容易陷入無窮循環(huán)。將要介紹的哥德爾巧妙的把戲,后來被艾倫·圖靈用于解決可判定性問題。
首先,每個(gè)公式或者說可形式化的命題都被我們的系統(tǒng)賦予一個(gè)數(shù),稱為哥德爾數(shù),例如,假設(shè)形式系統(tǒng)有100個(gè)符號,用0至99對這些符號進(jìn)行編碼,這樣,一個(gè)命題的公式就是一個(gè)位數(shù)為公式長度的100進(jìn)制的整數(shù),公式可以有不同的寫法,因此可以對應(yīng)多個(gè)數(shù),但每一個(gè)數(shù)或者不對應(yīng)任何公式,如果對應(yīng)某個(gè)公式,則只對應(yīng)唯一的一個(gè)公式,可能有多個(gè)數(shù)對應(yīng)同一個(gè)公式。因?yàn)橄到y(tǒng)包含所有正整數(shù),因此也就足以表述公式的概念了。一個(gè)證明可以表示為一個(gè)有窮的命題序列,例如將推理過程表示為命題序列。用同樣的原理也可以將一個(gè)證明表示為一個(gè)正整數(shù)。當(dāng)然,表示一個(gè)命題的正整數(shù)和表示一個(gè)證明的正整數(shù)具有不同的含義,因此不能混在一起。
像F(x)這樣的公式含有一個(gè)自由變量x,它們稱為命題形式。一旦x被一個(gè)特定的數(shù)代替,它就馬上變成一個(gè)真正的特定命題,于是它要么是在系統(tǒng)中可證明的,要么不。命題形式自身并不是命題,因此不能被證明也不能被否證。但每一個(gè)命題形式F(x)都有一個(gè)哥德爾數(shù),可用G(F)表示。自由變量的選擇與G(F)的賦值無關(guān)。
通過小心地分析系統(tǒng)的公理和推理規(guī)則,可以寫下一個(gè)命題形式P(x),它表示x是系統(tǒng)中一個(gè)可以證明的命題的哥德爾數(shù)。形式描述如下:如果x是一個(gè)可證明命題對應(yīng)的哥德爾數(shù),P(x)就可被證明,而其否定~P(x)則不能。(盡管這作為一個(gè)證明要點(diǎn)來說已經(jīng)足夠,但在技術(shù)上卻不太嚴(yán)格。請參見哥德爾和羅素的有關(guān)論文,關(guān)鍵字是“omega-consistency”。)
現(xiàn)在,哥德爾的把戲來了:一個(gè)命題形式F(x)稱為不可自證的,當(dāng)且僅當(dāng)把命題形式F的哥德爾數(shù)G(F)代入F中所得的命題F(G(F))是不可證明的。這個(gè)定義可以形式化,于是可以構(gòu)造一個(gè)命題形式SU(z),表示z是某個(gè)不可自證命題形式的哥德爾數(shù)。SU(z)的形式描述如下:
現(xiàn)在我們所要的語句p就可以如下定義:
直觀上,當(dāng)問到p是否為真的時(shí)候,我們是在問:“不可自證這個(gè)特性本身是不可自證的嗎?”這很容易讓人聯(lián)想到理發(fā)師悖論,那個(gè)理發(fā)師只替那些不替自己理發(fā)的人理發(fā):他替自己理發(fā)嗎?
現(xiàn)在讓我們假定公理系統(tǒng)是相容的。
如果p可以證明,于是SU(G(SU))為真,根據(jù)SU的定義,z = G(SU)就是某個(gè)不可自證命題形式的哥德爾數(shù)。于是SU就是不可自證的,根據(jù)不可自證的定義,SU(G(SU))是不可證明的。這一矛盾說明p是不可證明的。
如果p = SU(G(SU))的否定是可以證明的,則根據(jù)SU的定義,z = G(SU)就不是不可自證命題形式的哥德爾數(shù)。這意味著SU不是不可自證的。根據(jù)不可自證的定義,我們斷定SU(G(SU))是可以證明的,同樣得到矛盾。這說明p的否定也是不可證明的。
因此,p既不可在系統(tǒng)內(nèi)證明也不可在系統(tǒng)內(nèi)否證。
第二不完備定理的證明要點(diǎn)
令p是如上構(gòu)造的不確定命題,且假定系統(tǒng)的相容性可以在系統(tǒng)內(nèi)部證明。我們已經(jīng)看到,如果系統(tǒng)是相容的,則p是不可自證的。這個(gè)證明過程可以在系統(tǒng)內(nèi)部形式化,因此命題“p是不可證明的”或者“~P(p)”可以在系統(tǒng)內(nèi)證明。
但是最后一個(gè)命題就等價(jià)于p自己(而且這種等價(jià)性可以在系統(tǒng)內(nèi)部證明),從而p就可以在系統(tǒng)內(nèi)證明。這一矛盾說明系統(tǒng)是不相容的。
與不確定性原理的關(guān)系
有學(xué)者指出不完備定理和不確定性原理有某種聯(lián)系。
參見
相容性
自我引用
邏輯主義
哥德爾定理
哥德爾完備性定理
ZFC系統(tǒng)無法確定的命題列表
參考資料
免責(zé)聲明:以上內(nèi)容版權(quán)歸原作者所有,如有侵犯您的原創(chuàng)版權(quán)請告知,我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者,感謝每一位的分享。
- 有價(jià)值
- 一般般
- 沒價(jià)值
{{item.userName}} 舉報(bào)
{{item.time}} {{item.replyListShow ? '收起' : '展開'}}評論 {{curReplyId == item.id ? '取消回復(fù)' : '回復(fù)'}}
{{_reply.userName}} 舉報(bào)
{{_reply.time}}