戈德爾 (Kurt Gödel) 於1931年發表了他的「不完備定理」(Incompleteness Theorem)，至今正好六十年。為此，在戈德爾的求學地維也納，特別召開了一個會議，討論戈德爾這個定理所帶來的影響。的確，這六十年來，常在不同的 領域內，發現到這個定理的影響，而這個定理在不同領域中的應用，甚至引起了相當的爭議。

哈佛大學於1952年授與戈德爾榮譽科學博士學位，稱他為「本世紀最重要數學真理的發現者」 ^註1， 這裡所指的數學真理即為「不完備定理」。雖然當時是1952年，但已宣稱此定理是本世紀最重要的數學真理，可見此定理的重要性，不僅可說是空前，亦可稱為 絕後了。「不完備定理」到底是一個什麼樣的定理？本文將簡介此定理的背景、證明及它對數學、計算機和哲學的影響，盼望大家對這個定理能有較深入的認識與體會。

自第十九世紀後期，「集合」的觀念被提出後，數學家們逐漸的感到， 各個不同的數學領域，似乎皆可建立在同一個根基上，就是「集合論」，但是不幸的，過不久邏輯學家們即發現以「集合」這麼簡單，而且直覺上認為「真」的概念，卻會產生「反論」(antinomy)，即「集合」的概念會產生矛盾， 這使得數學家們重新思考數學的基礎到底是什麼？數學會不會出錯？ 如何面對一個直覺上為真，卻會導致矛盾的概念？是放棄「集合」的概念呢？ 或是如當時頂尖的數學家希伯特 (Hilbert) 所宣稱的： 「沒有人能將我們逐出集合論的樂園！」。若是如此，又將如何面對矛盾呢？

以總共不到17頁的三篇論文，一個年輕的荷蘭數學家布饒兒 (Brouwer) 對以往古典邏輯的確實性提出挑戰，特別是對所謂的排中律 (Law of the excluded middle)，即對任一命題「A」，A或A之否定命題必有一為真， 他認為我們不可無條件的接受，布饒兒堅持有其他的可能性， 因此也就有了數學哲學中的直觀主義 (Intuitionism) 學派，若接受了此一說法，連帶的，數學中許多的證明將不再被接受，特別是所謂存在性的證明。例如，要證明某一微分方程式有解，則必須給出一個方法，把這個解找出來， 而不可僅證明「若無解會導致矛盾」，而這卻是一般數學家們所常用的方法。 希伯特不讚成布饒兒的看法，他認為若是如此數學的犧牲實在太大了， 那麼要如何使數學能立在一個堅固的基礎上呢？ 為此他提出所謂的「希伯特計劃」(Hilbert program)， 即以有限性 (finitary)、組合式 (combinatorial) 的方法，由簡單的理論開始， 先證明「數論」有一致性 (consistency)，即「數論」中不包含矛盾， 再以「數論」為基礎證明「分析」有一致性，再一步步往前推， 至終證明數學中不包含矛盾，只要能證明即使使用排中律也不會產生矛盾， 那麼儘可放心大膽的去使用排中律，不必像布饒兒那樣束手束腳。

「希伯特計劃」是一個很好的計劃-如果能成功的話。在討論此計劃的成敗之前， 我們先介紹另一個觀念，上文我們說明了一致性。的確，一致性可說是對任一公設系統，最基本的要求，若一個系統內包含矛盾，其他的也就不用再談了， 對公設系統我們另一個希望有的性質就是完備性 (Completeness)。 我們用自然數 1,2,3,……來說明這個觀念。我們要證明有關自然數的定理， 如「質數有無窮多個」，我們若要將證明整個一步步寫下來，我們必須從某一個公設系統出發，其實任一個證明，都必須從某一個公設系統出發。對於自然數我們最常用的公設系統就是皮亞諾公設 (Peano Axioms)， 這些公設中最複雜而且困難的，（不僅對一般的高中，大學生如此，對邏輯學家亦如此），就是大名鼎鼎的「數學歸納法」。藉著數學歸納法及其他的公設， 我們可證明「質數有無窮多個」，問題是「是否所有有關自然數的敘述，只要是對的，就可由皮亞諾公設出發，而得到證明呢？」也就是「皮亞諾公設是否完備?」 若皮亞諾公設具有完備性，那麼所有有關自然數的敘述，若是對的， 就可由皮亞諾公設證明。

由戈德爾不完備定理而得的一個結論，就是「皮亞諾公設是不完備的！」有些關於自然數的敘述是對的，但皮亞諾公設無法證明它，戈德爾的證明也 的確告訴我們如何找到這個敘述。事實上，由戈德爾的證明，我們可得一個算則，給我們一個公設系統，我們就可按此算則，而得到一個算術句型，再經過適當的編 譯 (compile)，即可成為此系統內的一個句型，而此句型在此系統內為真，卻無法在此系統內被證明，所以也許我們會覺得皮亞諾公設不具有完備性，這是它 的缺點，我們應當找另一個具有完備性的公設系統來代替它，但不完備定理告訴我們，「任何一個具有一致性的公設化系統皆是不完備的！」這也就是為什麼雖然大 家明知皮亞諾公設是不完備的，但這個公設系統仍是被普遍的使用，因為任何其他系統，也都是不完備的。也許我們再退一步，皮亞諾公設固然不具有完備性，我們 至少可要求它具有一致性吧！也就是皮亞諾公設所證明的，一定是真的，可惜，這一點也做不到，由不完備定理可得另一個結論就是「在皮亞諾公設系統內將無法證 明它的一致性！」從某一方面來說，你須要假設比「皮亞諾公設是一致的」更強或相等的假設，你才能證明皮亞諾公設的一致性，當然我們若須要更強的假設，也就 須要更大的信心去相信它是對的。同樣的，皮亞諾公設也沒那麼特殊，就像不完備性的結果一樣，由戈德爾不完備定理，任一個足夠強的公設系統，皆無法證明它本 身的一致性，所以要證明數學具有一致性，即數學中不會產生矛盾，你將無法由數學中得到，你必須靠數學以外的東西，也許是你個人的哲學或神學，來相信數學是 有意義的，這可說是粉碎了「希伯特計劃」，難怪當希伯特由他的學生伯內 (P. Bernay) 處聽到戈德爾的這個定理時，他對這一個定理感到生氣 ^註2 ，因為他將無法回應布饒兒的挑戰了，但在真理面前，人人都須低頭。

敘述與證明

以上簡述了不完備定理的背景，現在我們來敘述不完備定理，一般所謂的不完備定理，分為兩個部份：

第一不完備定理
任何一個足夠強的一致公設系統，必定是不完備的。

即除非這個系統很簡單，(所以能敘述的不多)，或是包含矛盾的， 否則必有一真的敘述不能被證明。

第二不完備定理
任何一個足夠強的一致公設系統，必無法證明本身的一致性。

所以除非這個系統很簡單，否則你若在此系統性，證明了本身的一致性，反而已顯出它是不一致的。

戈德爾的證明過程相當複雜，而其中最核心的概念，是古典希臘哲學中一個有名的詭論 (paradox)：說謊者詭論。紀元前6世紀希臘時代的一個詩人哲學家 Epimenides 說了一句很有名的話：「所有的克里特島人都是說謊的。」這句話有名倒不是因為它是真理，正好相反，因為它一定是錯的，為什麼是錯的呢？因為說這句話的人 Epimenides 就是克里特島人，同樣一句話，別人說也可能是對的，（希望不致冒犯了克里特島人），但是由克里特島人來說，就一定是錯的，為什麼呢？若這句話是真的，則 Epimenides 沒有說謊，和這句話矛盾，所以這句話是假的。 我們再舉一個例子來說明這個詭論。

A：B這句話是真的。
B：A這句話是假的。

我們可能會認為A(或B)這句話非真即假，且讓我們來看看是否如此，假設A這句話是真的，即表示B這句話是真的，故「A這句話是假的」是真 的，故A這句話是假的，和假設矛盾。我們現在假設A這句話是假的，則「B這句話是真的」是假的，故B這句話是假的，所以「A這句話是假的」是假的，即A這 句話是真的，這又和我們的假設矛盾，結論是，A不論是真是假都得到矛盾，大家若有興趣，不妨從B句開始，亦得到相同的結果，這就是它之所以被稱為詭論的緣 由。

戈德爾是如何利用這個概念呢？若說：「這句話是假的。」 那麼利用前面的論證，這句話是矛盾的，所以任何一個一致的公設系統都無法說出這句話來，而戈德爾將上面的這句話改為「這句話不能被證明。」

注意，「真」和「能被證明」並不相等，同樣「假」和「不能被證明」亦不相等。 戈德爾證明了在皮亞諾公設內，（其實不需要用到這麼強的公設）可以說出「這句話不能被證明」，若願意接受這件事，我們即可證明不完備定理了，為證明方便， 我們稱「這句話不能被證明」為A，若在此系統內A被證明了，則由A的意義，即A不能被證明，知道「A」是假的，而在此系統內證明了一個假的敘述，表示此系 統是不一致的，故若此系統是一致的，則A不能被證明，則由A的意義得知A是真的，因它說它不能被證明，因此我們也就找到了一個敘述，即為A，它是真的，卻 無法被證明。任何一個公設系統若能說出「這句話不能被證明」則此系統若非不一致，就是不完備。為了確知是否清楚了這個概念，讀者不妨作一個測驗，「沒有真 理！」是真的嗎？

對數學的影響

何謂數學?對這個問題，不同的人會有很不同的答案，但是每一個數學家所努力的， 都是要找到「證明」，從大家所接受的公理或公設出發，找出對某一個題目的證明。 從希臘時代，就留下了許多的問題，有許多的問題，經過了數學家們的努力， 我們已知道了答案，也就是我們找到了「證明」，如所謂的幾何三大難題， 而有些至今尚未解決，如「雙生質數是否無限多？」任何一個問題， 我們總是盼望找到「證明」，不論是證明它是真的，或是證明它是假的都可以， 不論是證明「雙生質數是無限多」，或是證明「雙生質數是有限的」， 都將是一個非常轟動的結果。若是找不到證明，則認為也許是自己才智不夠， 或是時間尚末成熟，真的是如此嗎？

1930年希伯特接受 Konigsberg 贈予榮譽市民時，發表了一個著名的演說， 演說辭的最後兩句話為

「我們必須知道，我們將會知道」(Wir mussen wissen. Wir werden wissen.)

當年希伯特的演講所灌製的唱片，現在仍然保存著，我們若仔細聽， 仍依悉可聽到希伯特講完這句話時，得意的笑聲 ^註3 。對著數學抱著如此的信心， 相信是極大部份的數學家所共有的，希伯特清楚且有力的表達出來， 只可惜這個信心是沒有根據的，而且沒有多久，就被證明如此樂觀的信心是錯的， 因為1930年11月17日， 《Monatshefte fur Mathematik und Physik》這個期刊接受了當年25歲的戈德爾所投的稿，證明了不完備定理，有些命題是真的，但無法被證明， 數學家也許有信心（事實上由不完備定理可知這個信心是無法證實的）說： 「被證明的就是真的」，但再也無法說：「真的一定會被證明。」

自戈德爾證明了不完備定理之後，許多數理邏輯學家們即努力去找一個數論中為真， 但無法用皮亞諾公設證明的敘述，花了將近半個世紀都沒有找到， 因此也就有人說戈德爾所指的「為真但無法證明」的命題，可能和真正的數學無關， 即一個真正研究數學，而非研究邏輯的數學家，將永遠不會遇到這樣的命題， 不完備定理是邏輯上的一個有趣的定理，但對數學沒有影響，所有的數學問題， 如「雙生質數是否無限多？」，我們仍遲早會知道答案。 1978年 Paris 和 Harrington 終於找到了組合學 Ramsey 理論中的一個命題，它是真的，但無法用皮亞諾公設證明，後來其他的學者又陸續發現了許多這樣的命題，（有興趣的讀者可參閱筆者〈數學歸納法〉 一文）。 對任何一個數學命題，我們當然要想法子證明它是真的，或找反例證明它是錯的， 若是都不成功的話，也許該聽聽不完備定理所給的建議，嘗試去證明「此命題無法被證為真」，或「此命題無法被證明為假」，以往數學家只有兩條路可走，證明是 真的，或證明是假的，如今又多了兩條路，不能被證明是真的，和不能被證明是假的。要提醒大家注意的，就是第三條和第四條路彼此並不相斥，集合論中有名的 「連續統假說」(Continuum Hypothesis)，即被證明以現有的集合論公設，無法證明它為假（戈德爾1936年的結果），亦無法證明它為真（Paul Cohen 1963年的結果）。

對電腦的影響

戈德爾於193l年發表了不完備定理時，還沒有現今所謂的電腦，對於電腦如何發明的，至今仍眾說紛紜，我們引用普林斯頓高等研究院1978-1979年度 報告中所摘錄曾任美國國家科學院副院長的 Mac Lane 的一段話：「戈德爾偉大而抽像的邏輯工作，有個令人驚異的結果。在分析戈德爾所描述的何者可被一步步程序所得的正式方法中， 年輕而聰明的英國邏輯家圖林 (Alan Turing) 定出了這程序所得的結果，即一般遞歸函數 (general recursive functions)，這也正是一台機器所可能計算的，藉著這個分析，及其在 John Von Neumann 等人身上的作用，以致現代計算機的理論觀念及分析得以開展，直至今日，對於何者可被計算的理論描述，及至更深入的分析，我們可正確的說，仍然根植於戈德爾 於1931年所發表的數理邏輯論文中。」 ^註4

我們再舉兩個較近的例子：電腦病毒與人工智慧。對於電腦病毒，幾乎所有使用電腦的人都遇到過，人人聞之色變，因為感覺防不勝防，事實上，的 確如此。我們不時看到警告，又有某種新的病毒出現了，然後解毒專家們再設計一個新的解毒程式來破解它，在廣告中常看到說某種解毒程式如何如何有效，可解多 少多少種病毒，腦筋動的快的人，也許會想，為什麼不設計一種萬靈丹？可解所有已知及未知的毒，別的不說，錢肯定是可賺得不少，當然也可能有些人會想設計出 一種病毒是殺不死的， 戈德爾不完備定理告訴我們的是，「沒有萬靈丹」，也「沒有殺不死的病毒」， 對任何解毒程式，我們皆可設計出一種病毒，使得這個解毒程式殺不死它， 同樣對任何病毒，我們都可設計出一個解毒程式，把這個病毒殺死。總之， 不論是放毒或解毒的人，都不會沒事幹，我想這是個壞消息，也是個好消息 ^註5 。

電腦能不能跟人腦一樣？電腦和人腦的差別在那裡？這是常被提出的問題。使電腦跟人腦一樣，這是人工智慧學家努力的目標。英國劍橋大學的數學 物理學家，亦為皇家學會的院士 Roger Penrose 對這個問題，寫了一本出乎他自己意料之外暢銷的書《皇帝新腦》（The Emperor's New Mind）。1990年7月2日的時代雜誌也報導了這本書， 而時代雜誌用了一個唯恐天下不亂的標題〈那些電腦都是笨蛋！〉 (Those computers are dummies)。的確，此書一出又引起了正反雙方的論戰， Penrose 當然提出許多論證來支持他的論點，即人工智慧是有其限度， 他最重要的論證即根據戈德爾不完備定理，事實上，這個論證早就被提出過， 另外一本使戈德爾較為人所知的書，即為得1979年普立茲獎 (Pulitzer Prize) 的書 《戈德爾，艾叟，巴哈》(Godel, Escher, Bach)，作者 Hofstadter 分別以艾叟的畫，巴哈的音樂來闡述戈德爾的定理，就像 Penrose 的書，這本書也是介紹人工智慧， 夾議科學哲學的書，Hofstadter 同樣以不完備定理說明人工智慧所會受到的限制， 但 Hofstadter 對人工智慧的發展是樂觀的。

對哲學的影響

現今人類發現似乎有太多的問題無法解決，有各式各樣的「危機」，如能源危機、道德危機、人口爆炸危機等等，而常有「無力感」，但在本世紀初期，人類展望二 十世紀是充滿了盼望與信心，當然當時也有許多問題有待解決，但面對未來大家都是樂觀的，特別是對「理智」的信心非常強，相信憑著理智所有的問題都可解決， 數學不就是個明顯的例子嗎？十八、十九世紀數學的成就是驚人的，如從希臘時代就留下來的所謂「幾何三大難題」，竟然一次就都被解決了，也難怪希伯特對科學 說：「我們必須知道，我們將會知道」，自然須交出它所有的問題，而人類必將所有的問題一一克服，所以當不完備定理一出來，對許多人來說彷如晴天霹靂， Kline 寫了一本書，書名為《數學：確定性的失落》(Mathematics: The Loss of Cerntainty) 很能描繪出這個心情，人們認為找到了數學的基礎，卻發現這個基礎是海市蜃樓，而且不完備定理似乎告訴人們，我們將永遠無法找到這個基礎，連數學這號稱最精 確的科學尚且如此，其他所有的知識又如何立足呢?不完備定理告訴我們，有些事情是真的，但我們無法證明它，若是如此，人要如何面對沒有被證明的事？既無法 全部接受，亦不該全部否決，如何決定取捨呢？這似乎是人人都可以也應當思考的問題， 而不僅僅是哲學家所必須面對的問題。

不完備定理的發現至今已超過六十年了，這個定理的重要性，不僅未隨時間、歷史背景的改變而減退，人們在不同的領域中，正逐漸發現它的意義與 影響，只可惜由於國內對邏輯的研究者不多，至今尚沒有一本合適的中文書證明或闡明此定理，對此定理證明有興趣的讀者可參考 H.B. Enderton 所著的《A Mathematical Introduction to Logic》。