董世平

背景 敘述與證明 對數學的影響 對電腦的影響 對哲學的影響

戈德爾 (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 ，因為他將無法回應布饒兒的挑戰了，但在真理面前，人人都須低頭。