哥德爾定理(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、 一個系統(tǒng)在自身內(nèi)部證明了自己的一致性≠這個系統(tǒng)的一致性得到了證明。因為一個不一致的系統(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)更強，因此由哥德爾定理，它的一致性同樣在自身內(nèi)部是不可證的，要證明Y系統(tǒng)的一致性，需要更強的工具。這是否說明，算術(shù)系統(tǒng)一致性的證明，注定是相對的。,,,第二個

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

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

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

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

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

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

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