[轉錄]戈德爾不完備定理

[popandy (pop)]

來源：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)

> -------------------------------------------------------------------------- <

作者: popandy (pop) 看板: W-Philosophy
標題: [轉錄]戈德爾不完備定理(2)
時間: Tue Apr 20 21:29:15 2004


3.對數學的影響

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


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年的結果）。

4.對電腦的影響

戈德爾於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 對人工智慧的發展是樂觀的。

5.對哲學的影響

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


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


今年亦為國內的數理邏輯的前輩劉世超博士的七十歲生日，謹以此文敬賀劉教授七十歲，
亦盼望邏輯此一領域在大家繼續的努力下，在國內能生根，開花，結果。

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.5.64

> -------------------------------------------------------------------------- <

作者: popandy (pop) 看板: W-Philosophy
標題: [轉錄]Godel簡介
時間: Tue Apr 20 21:36:23 2004

來源：http://episte.math.ntu.edu.tw/people/p_godel/index.html

                          Kurt Godel（戈德爾）
                           翁秉仁∕台大數學系


Godel（1906～1978）生於現捷克之 Brno，卒於普林斯頓。Godel 是廿世紀最偉大之數理
邏輯學家，其不完備定理是廿世紀最具啟發性的思想發現之一。

Godel 自小便很好奇，青少年時即對數學、哲學、語言與歷史產生極大的研究熱誠。他在
維也納大學原主修理論物理，後轉回數學，並參與 Schlick（石里克）領導的「維也納學
圈」，對數學與科學作本質的哲學探索，1928年因聽了 Brouwer 的演講，乃致力於數理
邏輯的研究。

自19世紀中，由於非歐幾何的確立、分析嚴格化的要求與羅素悖論的出現，數學基礎的問
題吸引許多一流數學家的眼光，當時數學∕哲學家熱切地想將數學確定性的大廈奠基於某
種不可懷疑的基礎上，雖然多數人都很樂觀，但是從 Hilbert 與 Ackermann 在1928年提
出下列的未解問題：「一階邏輯是否完備(complete)或可決定(decidable)？」，顯示整
個基礎化計畫的進度十分緩慢。

1929/30年 Godel 初試啼聲，漂亮地在他的博士論文中證明一階邏輯的完備性，給
Hilbert 的計畫打下一劑強心針，但是不久後(1931)，Godel 卻證明了他最知名的「不完
備定理」：

設S為一包含算術系統的公理系統，若 S 相容（consistent，即不自我矛盾），則 S 不完
備（即在 S 中有些敘述為真，卻無法由 S 的公理推導出來）。

徹底崩毀了基礎化計畫。這一前一後兩個關於完備性的定理，使數學界（尤其是 Hilbert
學派）戲劇性地經歷烈火寒冰般的巨變。Godel 也因此聲名如日中天。1933年他應邀訪美
講學演說，此行他結識日後的摯友愛因斯坦。

30年代的歐洲瀰漫著法西斯的氣氛，Godel 亦師亦友的 Schlick 也因此被刺殺，這個噩耗
使他陷入精神沮喪，終其一生困擾著他的研究生活。大戰前夕，他完成另一個重要的工作
─證明選擇公理與連續統假設皆與ZF集合論相容。1940年他經由俄羅斯、日本到達美國，
從此定居於普林斯頓。

Godel 在美國的研究重心，逐漸轉移到其他方面。由於與愛因斯坦時相往來，40年代末，
Godel 致力於探討廣義相對論與時間的意義，證明循環時間與愛因斯坦方程並無矛盾（他
還因此在1950年的國際數學家會議提出報告）。另外，Godel 一直從事於哲學的深度思考
，專心研讀 Leibniz、康德、Husserl（胡賽爾）等的著作，留下的哲學思考筆記無數，
還沒有充分地編註印行。Godel 晚年（1971年起）時常與華裔邏輯∕哲學家王浩討論，並
因而促成王浩撰寫《Reflection on Kurt Godel》的佳話。

Godel 個人包辦了數理邏輯幾個經典定理，並為整個領域帶來革命性的風貌，堪稱是廿世
紀最偉大的數理邏輯學家。尤其是他的「不完備定理」，由於暗示了一個理性系統不可能
是全知的想法，經常被引申（或過度引申）到其他領域。例如：自然是無法被人類瞭解；
語言是沒有界限的；心靈無法認識自己等。非科學家最常引用的數學定理，竟然如此晦澀
，也該算是廿世紀的數學奇談了。

本文參考資料：（1）王浩，《Reflection on Kurt Godel》（2）大英百科全書 。
（3）MacTutor 數學史檔案網站：Godel。



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.5.64
※ 編輯: popandy         來自: 140.112.5.64         (04/20 21:37)
※ 編輯: popandy         來自: 140.112.5.64         (04/21 20:22)
→ aletheia:在《柏拉圖的天空》也有對Godel的介紹