來源：http://episte.math.ntu.edu.tw/articles/mm/mm_15_4_11/#top 戈德爾不完備定理 董世平 1.背景 2.敘述與證明 3.對數學的影響 4.對電腦的影響 5.對哲學的影響 戈德爾 (Kurt Godel) 於1931年發表了他的「不完備定理」(Incompleteness Theorem)， 至今正好六十年。為此，在戈德爾的求學地維也納，特別召開了一個會議，討論戈德爾這 個定理所帶來的影響。的確，這六十年來，常在不同的領域內，發現到這個定理的影響， 而這個定理在不同領域中的應用，甚至引起了相當的爭議。 哈佛大學於1952年授與戈德爾榮譽科學博士學位，稱他為「本世紀最重要數學真理的發現 者」 [註1] ，這裡所指的數學真理即為「不完備定理」。雖然當時是1952年，但已宣稱 此定理是本世紀最重要的數學真理，可見此定理的重要性，不僅可說是空前，亦可稱為絕 後了。「不完備定理」到底是一個什麼樣的定理？本文將簡介此定理的背景、證明及它對 數學、計算機和哲學的影響，盼望大家對這個定理能有較深入的認識與體會。 1.背景 自第十九世紀後期，「集合」的觀念被提出後，數學家們逐漸的感到，各個不同的數學領 域，似乎皆可建立在同一個根基上，就是「集合論」，但是不幸的，過不久邏輯學家們即 發現以「集合」這麼簡單，而且直覺上認為「真」的概念，卻會產生「反論」(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] ，因為他將無法回應布饒兒的挑戰了，但在真理面前，人人都須低頭。 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，它是真的，卻無法被證明。任何一個公設系統若能說出「這句話不能 被證明」則此系統若非不一致，就是不完備。為了確知是否清楚了這個概念，讀者不妨作 一個測驗，「沒有真理！」是真的嗎？ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.5.64 ※ 編輯: popandy 來自: 140.112.5.64 (04/20 21:17)