哥德爾定理(1)

1、,哥德爾不完全性定理 中國人民大學(xué) 哲學(xué)系 陳慕澤,,,第一講 哥德爾不完全性定理的背景、內(nèi)容和影響第二講 哥德爾第一不完全性定理和第二不完全性定理的證明,,,,,哥德爾不完全性定理的背景、內(nèi)容和影響 哥德爾其人 哥德爾不完全性定理的背景

2、哥德爾不完全性定理內(nèi)容及其證明的直觀描述 哥德爾不完全性定理的挑戰(zhàn)性影響,,,,,,,,,,,,哥德爾是20世紀(jì)最偉大的數(shù)學(xué)家和邏輯學(xué)家之一。 在邏輯學(xué)中的地位，一般都將他與亞里士多德和萊布尼茲相比；在數(shù)學(xué)中的地位，愛因斯坦把哥德爾的貢獻(xiàn)與他本人對物理學(xué)的貢獻(xiàn)視為同類。1952年6月美國哈佛大學(xué)授予哥德爾榮譽(yù)理學(xué)學(xué)位時(shí)，稱他為“20世紀(jì)最有意義的數(shù)學(xué)真理的發(fā)現(xiàn)者”。,,在哥德爾所發(fā)現(xiàn)的被稱為“20世紀(jì)最有意義的數(shù)學(xué)

3、真理”當(dāng)中，最杰出，最具有代表性、最有震撼力的是哥德爾不完全性定理。,,哥德爾第一不完全性定理 一個(gè)不弱于初等數(shù)論的形式系統(tǒng)如果是一致的，則是不完全的。其直觀意思大致可以這樣描述： 一個(gè)理論，如果具備足夠的表達(dá)能力和推理能力，那么，只要它不會(huì)證明自相矛盾的結(jié)論，就必然存在某種真理，它不可能證明。,,,,一個(gè)人，如果說的都是真話，那么，必定并非所有的真話他都能說（即總有真話他不能說）。,,哥德爾第二不完全性定

4、理 一個(gè)不弱于初等數(shù)論的形式系統(tǒng)如果是一致的，則這種一致性在該系統(tǒng)內(nèi)不可證明。其直觀意思大致可以這樣描述： 一個(gè)理論，如果不自相矛盾，那么這種不自相矛盾的性質(zhì)在該理論中不可證。,,,,一個(gè)人，如果始終如一，從不自相矛盾，那么，他必定無法說明，自己為什么會(huì)具備這種品質(zhì)。,,曾有人問哥德爾，是否可以將不完全性定理推廣到數(shù)學(xué)以外，哥德爾嘗試給出了一個(gè)自己認(rèn)為合理的表述： 一個(gè)處處按統(tǒng)一

5、法則行事的社會(huì)，就其行為而言，或者是不一致的，或者是不完全的，即無力解決某些可能是極端重要的問題。當(dāng)社會(huì)面臨困難處境時(shí)，這兩者都會(huì)危及社會(huì)的生存。,,哥德爾定理是一種特殊的數(shù)學(xué)命題，稱為元數(shù)學(xué)命題。 什么是元數(shù)學(xué)？ 什么是元邏輯？ 或者一般地，什么是元理論？ 科學(xué)的嚴(yán)格的元理論，何以成為可能？,,,元理論 對象理論

6、 對象 這應(yīng)當(dāng)是科學(xué)理論的理想結(jié)構(gòu)模式 （邏輯）元理論的目標(biāo)：分析和論證對象理論的 元邏輯性質(zhì)，最重要的是可靠性、一致性和完全 性，以及獨(dú)立性和可判定性等。 元理論必須比對象理論豐富。一般地，一個(gè)對象 理論不能同時(shí)成為自己的元理論。 科學(xué)元理論的前提：對象理

7、論的足夠嚴(yán)格。,,,,,,,,,,,數(shù)理邏輯為數(shù)學(xué)和邏輯建立了嚴(yán)格的元理論，其前提是，它為邏輯和數(shù)學(xué)建立了最為嚴(yán)格的對象理論。,,在抽象性和嚴(yán)格性上達(dá)到極致的理論形態(tài)：形式系統(tǒng),,非公理系統(tǒng)科學(xué) 科學(xué)知識 理論 實(shí)質(zhì)公理系統(tǒng) 公理系統(tǒng)

8、 形式公理系統(tǒng) （形式系統(tǒng)） 科學(xué)知識和科學(xué)理論的區(qū)別是什么？ 非公理系統(tǒng)和公理系統(tǒng)的區(qū)別是什么？ 實(shí)質(zhì)公理系統(tǒng)和形式系統(tǒng)的區(qū)別是什么？ 構(gòu)造形式系統(tǒng)的目的和意義何在？,,,,,,,,,,,什么是公理化 科學(xué)理論的“內(nèi)在循環(huán)”公理化方法的兩個(gè)要點(diǎn)

9、 公理的古典含義和現(xiàn)代含義,,,,,,什么是形式化 非形式的、形式的和形式化的 形式化方法和形式系統(tǒng) 形式化方法的兩個(gè)要點(diǎn) 語法和語義 對象理論和元理論 形式化和公理化 形式化的意義,,,,,,,,形式系統(tǒng)的語法 符號庫

10、 形式語言 形成規(guī)則 形式系統(tǒng) 公理 演繹結(jié)構(gòu) 推導(dǎo)規(guī)則 “可證”—— 核心語法概念,,,,,,,形式系統(tǒng)的極端抽象性 形式系統(tǒng)的語法理論只涉及符

11、號與符號之間的關(guān)系，不涉及符號的意義。,,,形式系統(tǒng)的極端嚴(yán)格性 能行方法 形式系統(tǒng)的極端嚴(yán)格性：任給一個(gè)符號，可以能行地判定是否為系統(tǒng)中的符號；任給一個(gè)符號串，可以能行地判定是否為系統(tǒng)中的公式；任給一個(gè)系統(tǒng)中公式，可以能行地判定是否為系統(tǒng)中的公理；任給一個(gè)系統(tǒng)中公式序列，可以能行地判定是為系統(tǒng)中的一個(gè)證明。,,,,,形式系統(tǒng)的語義 形式系統(tǒng)的語義理論的目標(biāo)

12、 “真”—— 核心語義概念 同一形式系統(tǒng)的不同語義解釋,,,,,,形式系統(tǒng)的元理論 可靠性 一致性 完全性 可判定性 獨(dú)立性,,,,,,,,形式化的重要概念 對象語言和元語言 對象理論和元理論

13、 語法和語義 系統(tǒng)內(nèi)的證明和關(guān)于系統(tǒng)的證明 內(nèi)定理和元定理,,,,,,,,構(gòu)造形式系統(tǒng)的意義，或者說形式化方法的意義在于： 第一，使系統(tǒng)內(nèi)的推導(dǎo)和論證的嚴(yán)格性達(dá)到了極致； 第二，使區(qū)分對象理論和元理論，建立嚴(yán)格的元理論成為可能。,,在幾乎所有的科學(xué)理論中，只有形式化的數(shù)理邏輯把自己的理論明確區(qū)分為兩個(gè)部分：對象理論和元理論。

14、 一個(gè)系統(tǒng)的元理論要解決的兩個(gè)最基本的問題是：第一，這個(gè)系統(tǒng)是否一致？即是否不矛盾，是否能確保兩個(gè)互相矛盾的命題在系統(tǒng)中不都可證？第二，這個(gè)系統(tǒng)是否完全？即相關(guān)的真理（真命題）在系統(tǒng)中是否都可證？ 一致性有關(guān)一個(gè)理論能否成立，顯然，一個(gè)不一致，即自相矛盾的理論，不可能是科學(xué)理論；而完全性有關(guān)一個(gè)理論證明相關(guān)真理的能力及其限度。,,也就是說，數(shù)理邏輯作為科學(xué)理論，具有一個(gè)極其鮮明的特點(diǎn)：它在構(gòu)造自己以說明思維

15、或數(shù)學(xué)的規(guī)律的時(shí)候，首先極其負(fù)責(zé)地審視自己：自己是否一致？如果是的話，如何證明？自己是否有足夠的能力把握思維和數(shù)學(xué)領(lǐng)域中的所有真理？如果是的話，如何證明？如果不是的話，這種能力的限度在哪里？如何證明？,,數(shù)理邏輯的這種“責(zé)任心”不是 自發(fā)地產(chǎn)生的，而是科學(xué)發(fā)展的 實(shí)踐“迫使”它具備的。,,問題最早源于2000多年前的歐氏幾何… 令人不放心的歐氏幾何第五條公理。 取消公理五的公理資格，證明它！

16、 世紀(jì)努力的失?。褐苯幼C明走不通。18世紀(jì)：反證！無意中構(gòu)造了一個(gè)非歐幾何：構(gòu)造它的目的是為了從中推出矛盾，即通過證明非歐幾何的不一致，在歐氏幾何中完成對第五公理的證明。 非歐幾何：怪誕 ? 矛盾 思維急轉(zhuǎn)彎：非歐幾何是否可能不矛盾？,,,,,,,,,這時(shí)，一個(gè)出乎數(shù)學(xué)家們意料的結(jié)論被證明了：歐氏幾何和自然數(shù)算術(shù)與非歐幾何在一致性上是等價(jià)的！ 就是說，如果歐氏幾何

17、或自然數(shù)算術(shù)是不矛盾的，則非歐幾何也是不矛盾的；也就是說，如果“怪誕的”非歐幾何是自相矛盾的，則歐氏幾何和自然數(shù)算術(shù)也是自相矛盾的！而人們構(gòu)造非歐幾何的目的，正是試圖證明它的自相矛盾！,,這樣，作為人類智慧杰作的歐氏幾何，似乎是天經(jīng)地義的自然數(shù)算術(shù)，其作為科學(xué)理論的合法性，立刻變得十分可疑。數(shù)學(xué)家突然認(rèn)識到：第一，歐氏幾何和自然數(shù)算術(shù)的一致性尚未得到證明；第二，這種一致性必須加以證明，否則，人們就沒有理由相信幾何與算術(shù)的定理為真理，因?yàn)?/p>

18、，如果這樣的系統(tǒng)是不一致的，那么，這些定理的反命題同樣是可證的。 這是科學(xué)發(fā)展史上一個(gè)多么應(yīng)當(dāng)引起重視的亮點(diǎn)！一個(gè)科學(xué)理論，在研究相關(guān)領(lǐng)域客觀規(guī)律的同時(shí)，嚴(yán)格的自我審視原來竟是如此至關(guān)重要！,,,,,正當(dāng)數(shù)學(xué)家們把證明數(shù)學(xué)系統(tǒng)一致性的希望寄托在集合論身上……,,1901年，整整一個(gè)世紀(jì)前，羅素發(fā)現(xiàn)了“集合論”悖論！ 概括原則和外延原則 依據(jù)概括原則，羅素定義了這樣一個(gè)集合S：S以所有

19、不以自己為元素的集合作為自己的元素。問：S是否以自己為元素？ 羅素悖論的俗本：理發(fā)師悖論 對素樸集合論的修補(bǔ)：公理集合論和羅素的分支類型論。筑起圍墻擋住了已發(fā)現(xiàn)的大灰狼，并不意味著能保證圍墻內(nèi)不再會(huì)出現(xiàn)大灰狼！,,,,,,,第一次數(shù)學(xué)危機(jī)。 畢達(dá)哥拉斯悖論：“不可公度線段存在性的證明”。 第二次數(shù)學(xué)危機(jī)。 貝克萊悖論：“無窮小量既是0又不是0”。第三次數(shù)學(xué)危機(jī)。

20、 羅素悖論：“集合論悖論”,,邏輯的數(shù)學(xué)轉(zhuǎn)向：數(shù)學(xué)基礎(chǔ)的研究 關(guān)于邏輯轉(zhuǎn)向,,,數(shù)理邏輯的三大流派： 羅素的邏輯主義； 希爾伯特的形式主義； 布拉維爾的直覺主義。,,希爾伯特綱領(lǐng) 目標(biāo) 三種數(shù)學(xué) 有窮方法,,,,,用數(shù)理邏輯的工具重新表達(dá)和構(gòu)造數(shù)學(xué)系統(tǒng)，并證明它們的一致性，以及另外一些

21、重要的元性質(zhì)，這就是形式化的數(shù)理邏輯給自己提出的任務(wù)。 這是一個(gè)巨大的挑戰(zhàn)和艱辛的探索。在這一過程中，數(shù)理邏輯自身得到了長足的發(fā)展而臻于成熟。哥德爾不完全性定理正是在這種探索過程中所取得的最杰出的成果。,,哥德爾不完全性定理包括兩個(gè)重要結(jié)論：,,第一個(gè)結(jié)論（哥德爾第二不完全性定理）：算術(shù)形式系統(tǒng)（以及一切不弱于算術(shù)系統(tǒng)的形式系統(tǒng)）如果是一致的，則這種一致性在系統(tǒng)內(nèi)是不可證的。 一個(gè)

22、形式系統(tǒng)的能力，包括它的形式語言的刻劃能力和演繹結(jié)構(gòu)的推導(dǎo)能力。所謂不弱于算術(shù)系統(tǒng)，就是指這種刻劃和推導(dǎo)能力不弱于算術(shù)系統(tǒng)。上述結(jié)論告訴我們：這樣的系統(tǒng)的一致性，即不矛盾性的證明，不可能在本系統(tǒng)內(nèi)作出，要完成這樣的證明，必須使用（至少在某些方面）比本系統(tǒng)更強(qiáng)、更復(fù)雜些的工具才有可能。,,,不要誤解哥德爾第二不完全性定理 形式系統(tǒng)的一致性不可知？不可證？,,,如果一個(gè)系統(tǒng)在自身內(nèi)部證明了自己的一致性又怎么樣？

23、 一個(gè)系統(tǒng)在自身內(nèi)部證明了自己的一致性≠這個(gè)系統(tǒng)的一致性得到了證明。因?yàn)橐粋€(gè)不一致的系統(tǒng)可以證明任何結(jié)論，包括自己的一致性。 命題演算在系統(tǒng)內(nèi)證明了不矛盾律 ?（A ∧ ?A）不等于證明了自身的不矛盾性（一致性）。,,,哥德爾第二不完全性定理宣告了希爾伯 特綱領(lǐng)的破產(chǎn)？,,,算術(shù)系統(tǒng)的一致性的證明到底解決了沒有？ 甘岑、阿

24、克曼分別用超窮方法證明了算術(shù)系統(tǒng)的一致性。哥德爾在使用有限型泛函法所構(gòu)造的系統(tǒng)（稱為Y系統(tǒng)）中，也證明了算術(shù)系統(tǒng)的一致性。 現(xiàn)在的問題是：例如，Y系統(tǒng)如何證明自己的一致性？如果它不能形式化，則甚至不具備討論它的一致性的基礎(chǔ)；如果它能形式化，則由于它比算術(shù)系統(tǒng)更強(qiáng)，因此由哥德爾定理，它的一致性同樣在自身內(nèi)部是不可證的，要證明Y系統(tǒng)的一致性，需要更強(qiáng)的工具。這是否說明，算術(shù)系統(tǒng)一致性的證明，注定是相對的。,,,第二個(gè)

25、結(jié)論（哥德爾第一不完全性定理）：算術(shù)形式系統(tǒng)（以及一切不弱于算術(shù)系統(tǒng)的形式系統(tǒng)）如果是一致的，則是不完全的，即存在著一個(gè)系統(tǒng)內(nèi)的真命題，在系統(tǒng)內(nèi)不可證。,,,哥德爾第一不完全性定理的證明是極其漂亮的。 哥德爾定理的魅力，不僅在于它的內(nèi)容，而且在于它的證明思路和方法。,,哥德爾在形式算術(shù)系統(tǒng)中構(gòu)造了這樣一個(gè)命題A，它的含義恰恰是：“命題A在系統(tǒng)中不可證”。 第一，A不可能假。 如果命題A假，即“命題A在系

26、統(tǒng)中不可證”假，即事實(shí)上命題A在系統(tǒng)中可證。由可靠性，A是真命題。矛盾！所以命題A必定真。 第二，真命題A斷定的正是自身在系統(tǒng)中不可證。 所以命題A就是一個(gè)在系統(tǒng)中不可證的真命題！即如果系統(tǒng)是一致的，則是不完全的。,,注意：命題A這樣的命題具有兩個(gè)特點(diǎn)： 第一，命題A斷定自身的不可證性。這種斷定是基于形式定義之上的，是嚴(yán)格的，無歧義的。 第二，命題A就其意義來說是元數(shù)學(xué)命題

27、，但它完全是用對象語言表達(dá)的，即完全是算術(shù)形式系統(tǒng)內(nèi)的算術(shù)公式。 也就是說，哥德爾做了一件看來有悖于形式化的基本定義的事：他用對象語言構(gòu)造了一個(gè)元理論的命題。,,命題A這樣的命題，稱為不可判定性命題。 不可判定性命題一旦構(gòu)造出來，哥德爾定理的證明也就接近完成了。 哥德爾定理證明的實(shí)質(zhì)內(nèi)容，就是不可判定性命題的構(gòu)造，即在算術(shù)形式系統(tǒng)內(nèi)，用對象語言構(gòu)造一個(gè)元數(shù)學(xué)內(nèi)容的命題，它斷定自身在系統(tǒng)中不可證。,,,數(shù)

28、學(xué)不但是不完全（incomplete）的，而且是不可完全（ incompletable ）的。 是數(shù)學(xué)形式系統(tǒng)不可完全，還是數(shù)學(xué)不可完全？ 哥德爾定理揭示了形式化方法的局限？,,,,,在數(shù)理邏輯這段令人眼花繚亂的發(fā)展歷史和科學(xué)成果中，我認(rèn)為，至少以下幾點(diǎn)應(yīng)該引起我國的人文科學(xué)工作者，包括馬克思主義哲學(xué)工作者的注意和思考。,,第一，一個(gè)科學(xué)理論，在研究特定的對象世界的同時(shí)，應(yīng)該把審視和研究自

29、身作為本理論的一個(gè)組成部分。,,2000年的研究生入學(xué)政治考試中有一道試題：用對立統(tǒng)一規(guī)律分析改革開放的巨大成就和負(fù)面影響的關(guān)系。答案要點(diǎn)：（1）兩點(diǎn)論：改革開放取得巨大成就的同時(shí)出現(xiàn)某些負(fù)面影響是必然的；（2）重點(diǎn)論：巨大成就是矛盾的主要方面，決定改革開放的性質(zhì)；（3）轉(zhuǎn)化論：不能忽視負(fù)面影響，在一定的條件下負(fù)面影響有可能轉(zhuǎn)化為矛盾的主要方面，而改變改革開放的性質(zhì)。不難發(fā)現(xiàn)，上述這些理論要點(diǎn)，當(dāng)年就是用來證明“文化大革命成績最大最大最

30、大，損失最小最小最小”的，就是用來分析“大躍進(jìn)”的“九個(gè)指頭”和“一個(gè)指頭”的關(guān)系的?，F(xiàn)在幾乎一字不動(dòng)地用來論證改革開放。如果上述這樣的哲學(xué)分析都是成立的，則允許作此種分析的哲學(xué)理論的一致性就應(yīng)受到嚴(yán)重質(zhì)疑。,,（A ∧ ?A）? B 這個(gè)命題邏輯中的重言式說明：一個(gè)不一致的理論可以證明任何結(jié)論。,,第二，一個(gè)科學(xué)理論，對于說明自身是不夠的。,,第三，哥德爾不完全定理說明，數(shù)理邏輯是這樣一種科學(xué)理論和真理形式，它

31、明確揭示和證明自己把握真理的能力限度。,,最后順便提一下，上文所提到的“怪誕”的非歐幾何，在它的理論形態(tài)產(chǎn)生的數(shù)百年后，在微觀和宇觀世界中找到了自己的模型和實(shí)際應(yīng)用，而被證明是和歐氏幾何一樣的科學(xué)理論。 非歐幾何是從哪里來的？是從實(shí)踐中來的嗎？不是。是基于感性經(jīng)驗(yàn)的嗎？也不是。它是如此地違背人們的實(shí)踐經(jīng)驗(yàn)和感性直覺，以至人們當(dāng)初構(gòu)造它的唯一目的是想證明它的不可能成立。它是在自己的理論形態(tài)出現(xiàn)幾百年后才找到自己的現(xiàn)實(shí)