被誤用的哥德爾「不完備性」定理

被誤用的哥德爾「不完備性」定理
Photo Credit: AP Photo / 達志影像
我們想讓你知道的是

「哥德爾不完備性定理」是數學上非常重要而且經常被誤解的定理。

在本網台灣版讀到一篇文章[1],摘錄自《生命解碼︰從量子物理、數學演算,探索人類意識創造宇宙的生命真相》一書,提及哥德爾不完備性定理(Gödel's incompleteness theorems)。這是數理邏輯中非常容易誤解的定理,而該篇文章作者正正誤解了這定理。

除了上述書摘外,我沒讀過《生命解碼》其他章節,但簡介提到「量子力學應該是靈魂的最佳見證者」,讀到這一句已認為應該小心對待,特別是作者林文欣未有任何物理學背景,非常容易受坊間討論量子力學的文章誤導。無論是胡言亂語的偽科學,抑或出於好意簡化艱深內容、略去數學公式的科普文章,都會令外行人讀完後有錯覺以為自己了解量子力學。

該篇書摘中林文欣把「不確定性」及「不完備性」並置,但主要還是談不完備性定理,因此本文就不再多說量子力學的東西,集中討論數理邏輯。

悖論與不可判定命題

要談論哥德爾不完備性定理,自然少不免講述背景。林文欣表示︰

上世紀初,數學家在經過三次數學危機後,就一直想找到一個「完備」的絕對真理,一個能證明世上所有數學公理是真還是僞的演算法。因為之前,數學一直存在太多「既不能證明是真又不能證明是偽」的命題。

一,形式系統(formal system)中的公理就是最基本的命題[2],透過公理按變形規則轉換出來的才是定理。所以重點並非證明數學「公理」,而是「定理」。

二,他想說此前數學發現了一些「悖論」(paradox),但文中誤稱為「駁論」。相關的數學悖論有一個特點︰無論假設某命題是真是假,都會推出矛盾的結論。這跟「既不能證明是真又不能證明是偽」有重大分別,無法證明真偽的命題應是「不可判定」(undecidable),悖論存在則代表相應的數學系統隱含矛盾——根據古典邏輯中的「爆炸原理」,證明了矛盾句就可以證明任何命題。[3]

林文欣又聲稱不完備性定理「說明」了以下三件事︰

  1. 不是所有對的東西都可以被驗證,就像直覺一樣。
  2. 也沒有一種理論或真理可以永久解釋而不被超越。
  3. 同時也告訴我們,有些東西我們是不可能知道的。

當然都有問題,但容我先花點篇幅講述背景再解釋。

希爾伯特的形式主義

19世紀開始,數學變得越來越抽象,不同領域發展出各套公理。在第三次數學危機期間,數學家發現原有的「樸素集合論」(naive set theory)隱含矛盾,令他們關注數學本身是否有一個可靠的根基——例如一套可以推論出各門數學的公理系統。當時有幾個學派嘗試回答這問題,但本文重點只會放在形式主義(formalism),更準確一點說是數學家希爾伯特(David Hilbert)的形式主義。[4]

希爾伯特認為可以把較複雜的數學領域,化約至較簡單的數學系統,最終數學界只需要確保算術系統的一致性。問題是,如何用數學去證明數學系統一致?

他提出將數學變成一個形式系統,一個只有符號沒有文字的系統。公理就是一堆特定符號串,然後按明確的規則「搬弄符號」。符號代表的是數學命題,形式系統中的公理,正如對應數學系統中的公理,那些「搬弄符號」的規則就是數學上合法的推導步驟。

一致性與完備性

希爾伯特認為,當找到這套系統之後可以問一個問題︰這個系統從有限的符號串(公理)出發,按有限的規則轉換,會不會產生代表矛盾句——例如「0=1」——的符號?直觀上,這是數學可以處理的問題,就像可以證明國際象棋中不可能同時有兩隻同色「象」(主教) 在同一顏色的格中出現般。當然,證明仍然需要用到數學,希爾伯特認為證明如果只涉及有限的概念就可以接受。

2017-12-11更新︰感謝讀者秦紀維留言指出,根據國際象棋規則,在罕見的低升變(underpromotion,不升成后)情況下,卒可以變成象,因此容許多於兩隻同色主教在同顏色格。

假如能夠證明這個形式系統不會產生代表「0=1」的符號,就代表系統不會導致矛盾——否則的話,一個矛盾可以推出其他矛盾句。但是,形式系統不產生矛盾可能是因為本身太簡陋,所以希爾伯特有另一個要求︰任何能夠在該系統中表達的命題(嚴格來說是閉公式),都能夠證明或否證(即證明其否定句)。

不矛盾的要求稱為「一致性」,能證明或否證所有數學命題的要求稱為「完備性」。[5]

不完備性定理

要盡量淺白去介紹哥德爾不完備性定理的話,可以這樣說︰假設某個形式系統一致,而且可以表達基本的數學(如算術)[6],這個系統就不可能滿足「完備性」此條件。引伸的一個結果就是,用來描述算術的形式系統中,存在一些不可判定命題,無法證明也無法否證。此外,任何可以用來表示算術的系統,例如數學界普遍使用的ZFC集合論,都受到同樣限制(著名的連續統假設就是ZFC中的不可判定命題)。

讀者必須注意,在數理邏輯的相關討論,「證明」這個概念是相對於形式系統的,當提到「命題A不可證明」時,說的其實是「命題A不可在形式系統中S中證明」。事實上,要證明「不可判定命題」非常簡單,把它納入成為新公理就可以了——只是這個新形式系統又會有相應的不可判定命題。

天才橫溢的數學家馮諾曼(John von Neumann)得悉哥德爾的證明後,立即意識到其重要,並向他了解證明細節。後來馮諾曼發現了一件事︰哥德爾在算術系統中構造了一句不可判定命題,成功證明算術系統不可能完備,然而這蘊涵了另一重要命題——代表「『0=1』在本系統中不可證明」——也不可判定。可是哥德爾回覆他早已發現這一點,並於幾天前寄出手稿,後世稱這結果為「哥德爾第二不完備性定理」。[7]

我認為要談論不完備性定理之前,必須要了解一點︰這條定理固然是數理邏輯甚至數學史上的重要發現,它跟不少大定理一樣是非常技術性的結果,但因為第三次數學危機的背景,以及其後設數學(以數學去研究數學系統)的特質,非常容易引起誤解。每當讀到有人將這條定理「應用」至數學以外的範疇,就應該加倍小心。

誤解邏輯定理

林文欣文章中的最大錯誤,在於嘗試把不完備性定理「推廣」至談論人類的經驗知識發展,再把數理邏輯跟量子力學混為一談。兩者看來都跟「知識的極限」有關,然而哥德爾定理談論的是數學中的形式系統[8],而形式系統僅是人類知識的一小部分,往往不是用來發現新知識(雖然相關研究最終推動電腦的出現,就有強大的實際應用)。再者,形式系統中的「證明」跟他所用(我猜是科學中)的「驗證」有很大分別。

當然,他可以推說自己用的是「說明」,僅用不完備性定理來比喻。問題是,他說的東西有些根本不需要用不完備性定理來比喻,直接說就行。我嘗試把他的「沒有一種理論或真理可以永久解釋而不被超越」理解成「科學理論會不斷發展」,後一句當然是真的,經驗知識總有修正、推翻的可能(不代表一定會被推翻)。不過也要留意,知識同樣會累積,已有大量經驗證據支持的理論難以完全推翻。

另外,如果了解這條定理,更會知道他的比喻不倫。很多人會用不完備性定理來推論「機器不能像人類般思考」,理由是機器只能用形式系統,於是必然有不可判定命題,但人類可以「看」得出該命題為真。我猜這種誤讀導致林文欣宣稱「直覺」如此重要。

簡單來說,不完備性定理的一項重要前提是「算術系統一致」,有了這個假設,我們才可以推論出「存在不可判定命題」。可是無論是直覺或其他東西都無法讓人類「看」出「算術系統一致」這個前提為真,單看不完備性定理的限制方面,人類並沒有比機器優越。

不懂絕對沒有問題

這篇文章也許對林文欣有點嚴厲,但絕無嘲諷之意。不懂不完備性定理絕對沒有問題,畢竟數理邏輯是非常專門的學科,一般人無需要理解。

在略懂的情況下,誤解這條定理也毫不出奇。關於「達克效應」(Dunning-Kruger effect)的研究顯示,面對不太熟悉的東西時,我們容易高估自己的理解程度。事實上,我以前也對此定理有不少誤解及錯誤的「推論」,只是幸好後來有機會學到更多,發現錯誤,希望這篇文章可以幫助更多人了解這條定理。

坊間有太多誤解哥德爾不完備性定理的文章,對此定理有興趣的讀者,我建議可閱讀《哥德爾定理︰使用與濫用的不完整指南》(Gödel's Theorem: An Incomplete Guide to Its Use and Abuse)一書,作者是已故瑞典數學家費蘭辛(Torkel Franzén),好像未有中譯本。其他免費資源可以參考邏輯學家史密夫(Peter Smith)的網站Logic Matters。[9]

後記

林文欣在文章中提到︰

著名物理學家約翰・惠勒(John Archibald Wheeler)在1974年發表的文章中就斷言︰即使到了西元5000年,如果宇宙仍然存在,知識也仍然放射出光芒的話,人們仍然會把哥德爾的不完備性定理和量子力學的不確定性原理看成是一切知識的中心。

我未能查到這篇「1974年發表的文章」是甚麼,亦無法找到引言出處,在Google搜尋時只發現下面這個故事,覺得有趣,收錄在此。

算法訊息理論專家查廷(Gregory Chaitin)在《Information-theoretic Incompleteness》提到,他曾經問惠勒不完備性定理和不確定原理是否有關。惠勒沒有正面回答他,卻提到自己曾經問哥德爾兩者有沒有關係,而被哥德爾「趕離」其辦公室。

物理學家伯恩斯坦(Jeremy Bernstein)的《Quantum Profiles》一書同樣提及此事,但沒那麼戲劇化。惠勒指當他問哥德爾上述問題時,哥德爾轉換話題,談論物理學。約一年後某次小派對中,哥德爾才解釋為何不願談論量子力學中,非決定論跟數理邏輯中不可判定性的關係——因為他跟愛因斯坦討論了很久,不相信量子力學和非決定論。

相關文章︰

註︰

  1. 生命的存在,是建立在「不確定性」及「不完備性」的基礎之上
  2. 嚴格來說,「命題」涉及語意,形式系統中應使用「陳述」(statement)或「句子」(sentence),即「閉公式」(closed formula),但這區分在本文過於技術性,為免引起不必要的混亂,均使用「命題」。
  3. 關於「爆炸原理」可參考《維基百科》相關條目
  4. 數學哲學中的形式主義有很多種,可參考《史丹福哲學百科》相關條目
  5. 關於希爾伯特的計劃,可參考《史丹福哲學百科》相關條目,留意其中一節談論到哥德爾不完備性定理對此計劃的影響。
  6. 此處「算術」指關於自然數(0, 1, 2, ...)及其加法、乘法及指數運算的系統。
  7. 這個故事來自數學家道森(John W. Dawson, Jr)撰寫的哥德爾傳記《Logical Dilemmas: The Life and Work of Kurt Gödel》。
  8. 當然也可以從可計算性理論(computability theory)等角度去理解。
  9. 史密夫寫了一本書去介紹不完備性定理,他的網站上有關於該定理的書單和筆記。

核稿編輯︰王陽翎

或許你會想看
更多『評論』文章 更多『科學』文章 更多『Kayue』文章
Loader