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

在本網台灣版讀到一篇文章^[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]