【數理邏輯】
愛與資訊與哥德爾不完備定理
張貼日期:Jun 03, 2020 4:34:22 AM
作者:高竹嵐 副教授(國立陽明交通大學統計研究所)
愛與資訊
故事要從去年底說起。之前我在音樂劇工作坊時的恩師,台大戲劇的吳政翰老師,臉書私訊我。我跪著打開訊息:
『我在翻譯一個劇本,有個名詞想請教你…什麼是哥德爾不完備定理啊?』
『啥鬼,劇本裡有哥德爾不完備定理!?』
這個劇本是Caryl Churchill的劇本『愛與資訊』(2012)。順道說明,Churchill老人家1938年生,到現在她都還在寫劇本(跪)。
然後看完演出後發現,這劇本裡別說有哥德爾了(雖然只有點到為止),還有圖靈測試,還有自由意志的哲學論辯,連因為根號2而被人推下海的故事都進去了...誰說文組就不能涉足各種科學概念?
更何況,不止編劇要懂,演員也得懂,總不能唸一句自己也不知道在講什麼的台詞,這觀眾肯定是看得出來的。在此為辛苦去理解這各種概念的演員們一鞠躬。
再次印證戲劇作為一種跨學科交流平台的可能性,我們透過同一個空間,討論各種可能。
※
只有對與錯的世界
回到最前面的故事,我聽到要解釋哥德爾不完備定理的時候抖了好多下。這玩意有夠難講的啊!(以下高能預備)
讓我們先從對錯開始說吧!是的,對與錯。
首先必須理解到,數學裡一個數學敘述要嘛對,要嘛錯,沒有中間可能。數學中,不存在像這樣的句子:
『這句話是錯的。』
上面這句話不對也不錯。如果它是對的,那這句話就是錯的;而如果它是錯的,這句話就得是對的。所以它不能對也不能錯。
先記得,對於一個數學體系裡,我們不允許存在像上面這樣的句子。每個數學敘述,非對即錯,沒有中間可能。
※
歌德爾不完備定理
所以數學裡凡是非對即錯。那進一步的問題就是,所有對的敘述,我們都能證明它嗎?
這邊要解釋一下證明是什麼意思。每個數學系統都有所謂的公理,例如歐氏幾何的平行公理(兩平行線永不相交),皮亞諾公理中的後繼元素(每個自然數都會接一個自然數),總之是一些我們先決假設為真的敘述。
我們說一個敘述能被證明,表示我們可以從這些公理開始,透過一系列的邏輯運算,推出這個敘述是對的。
而如果一個數學系統裡面所有的敘述都能被證明,我們便說這個數學系統是完備的。所以問題就是:
我們的數學系統,是完備的嗎?
會不會根本有些東西,我們就是證明不了?
這問題重大到被列進希爾伯特問題裡,而當然,大家都希望,我們的數學系統是完備的,所有問題,只要給我們夠多時間,我們一定證的出來。
然後,哥德爾出現了。『抱歉,它不完備。』
哥德爾論證的『大概念』其實很簡單。記得之前那個這句話是錯的嗎?我們考慮一個類似的敘述:
『這句話不能被證明。』
這句話是對還是錯啊?
如果它是錯的,這句話就能被證明。既然它能被證明,那它就必須要是對的。但這樣一來,它就不能被證明。矛盾!
所以它必須是對的(因為數學系統裡非對即錯),但既然它是對的,那...這句話就不能被證明...
是的,你於是得到了一句對的敘述,但任何人無法證明它。換言之,你的數學系統,不是完備的。
以上是哥德爾證明的『大概念』,但此處有一個大問題:
『這句話不能被證明』不算是一句數學敘述!
所以哥德爾做的事情基本上如下:
如果你的數學系統裡包含自然數跟加減乘除,
我就能寫出一條數學敘述,它等價於『這句話不能被證明』!
講簡單一點,哥德爾用1234跟加減乘除,寫出『這句話不能被證明』這句話。
※
好,所以你告訴我,有些問題不能被證明…但如果這些不能被證明的,都是一些奇奇怪怪的,我們八輩子不會去碰的問題,那應該就…還好吧?
偏偏事情就不是這樣。舉例來說,數論中的Goodstein’s Theorem, 以及我們之前提過的連續統假設,都被證明出『不可被證明』,而這些都是真實有人在研究的問題。換言之,我們在討論的,可不是那些奇奇怪怪的罕見問題,很可能就是你眼前正在研究的問題啊!
一時之間,研究黎曼猜想的人要抖一下,研究哥德巴赫猜想的人要抖一下,研究各種未解問題的人都要抖一下,每天上工之前記得燒香拜佛,祈禱自己不會窮盡畢生精力,研究一個其實不可能被證明的題目…
以上是對哥德爾不完備定理的簡介。有興趣的人,這裡有更詳盡的兩部影片: