First incompleteness theorem:
"In a finitary formal system with arithmetic, there is a proposition is true and unprovable."
這本書談的是一位影響力和知名度完全不成比例的數學家Kurt Godel
他的不完備定理(incompleteness)震憾了數學界..也從此改寫人類對於世界的看法
它與Einstein的相對論(relativity)以及海森堡的測不準原理(uncertainty)
被作者並列20世紀人類三大思想突破
相對論改變了我們對最基本的時間與空間的看法
測不準原理改變了我們對事物本質的認知
而不完備定理改變了我們理解這個世界的想法
這三大突破除了在他們原來的物理和數學領域開啟了新的方向外
在哲學方面卻也常被引用..甚至引用過當
這本書談的是人類邏輯推演最深層的東西
一直以來算數學算的開心的我..也不禁自問..我真的了解自己在算什麼嗎?
又如同Godel年輕以來一直有的質疑一樣..我們真的了解彼此在說什麼嗎?
Godel本身是個很陰暗很少話的人..也一直覺得自己有嚴重的疾病
但他的思考與邏輯能力卻讓知道的人讚嘆不已
他和晚年的Einstein成了忘年之交
而Von Neumann也是他理論的最有力的推廣(銷)者
關於他的生平實在是一個謎團..所以本書主要著重在不完備定理上
從那可以了解這位數學家對世界的想法..同時也挑戰我們自己對這世界的想法
這本書除了中段解釋定理的證明外..大部份都處在哲學等級的討論上
看似有點無趣..但仔細一想卻是個無底洞
書中將人們大致上分為兩種..一種是Positivist..一種是Platonist
我想基本上大部份的人都是介於中間..只是看比較偏向哪種
前者為實證派..覺得任何理論若不能觀察到或被實驗..就是沒有意義的
最激進的推廣就是人類為世界的中心..世界是如何端看人類如何看它
後者為柏拉圖派..覺得在我們看不見的世界幕後..有一定的真理存在
而人類只是一直在對真理做盲人摸象的揣測
從20世紀以後..Positivist的人越來越多..我想大部份現在的人都是這種傾向
然而Einstein和Godel都是徹底的Platonist
也同因自己的理論被拿來支持Positivist而困擾不已
這已無分對錯..這關乎人們自己最內心的世界觀
例如Einstein的想法是..相對論講的是有一個絕對的被扭曲的四維時空
而我們平常認知的時間只是人類自己的幻覺..該四維時空才是絕對的
但很多人用相對論來說..一切都是相對的..所以沒有客觀的科學真相
一切都是以自己為出發點的主觀科學..這些人從測不準原理也能得到一樣的結論
當時的數學圈也是在類似的氛圍下
數學身為最純綷的學科..其實也暗藏了很多暗流
無限大這個概念帶來了微積分..但也帶來了數不盡的爭論
而且還不時會有邏輯上的詭論出現 (ex. 阿基里斯永遠追不到烏龜)
無限大似乎和一般的概念有基本上的差異
最著名的例子就是非歐幾何的出現
其實當歐幾里得在整理<幾何原本>時就覺得第五公設有點怪怪的
第五公設就是一線外的一點..有也僅有一條線會和該線平行..平行即為"永"不相交
這個公設定義必需使用無限遠處這種概念
然而後來的人發現..若假設第五公設是錯的..卻也不會和另四條公設有任何矛盾
反而因此發展出非歐幾何..甚至於微分幾何
在第五公設其實是多餘的隱喻之下..20世紀初的數學家想要找出完美的數學天堂
也就是找出一個(些)數學系統..它們排除掉無限大的概念..同時也是consistent和complete的
(consistent指的是不會有矛盾出現, complete指的是所有系統內的東西都是可以證明的)
該行動由當時歌廷根數學大老Hilbert..在1899年提出的Hilbert Program帶到了最顛峰
該Program包含了他認為新世紀最重要的十個問題
其中第二個問題也是概念上最重要的問題就是
證明能在算術公設系統內證明出自己為consistent&complete的formal數學系統存在
如此的系統只要給定一開始的公設和算術定義..所有事實都可以自動產生..不需人類的介入..此乃天堂也
這裡的formal有其嚴格的數學定義..但概念上指的就是給定所有的公設與語法
該系統只能在有限步驟中推理出能推理的定理
在這裡無限大的概念被去除了..於是也去除了反證法 (proof by contradiction)和歸納法(induction)
因為反證法是假設命題為假..找出矛盾來證時命題為真
但"找"這個動作其實是無法確定在有限步內做完的
而歸納法最後一步是用延伸到無窮盡來完結的
在沒有任何預期之下..23歲的Godel出現了..毀滅了一切
其實除了無限大這個麻煩製造者..還有另一個更如鬼魅般的東西存在
那就是self-referential formula or sentence
最有名的就是liar paradox..也就是"這句話是錯的"
如果它是錯的話..那這句話就是對的..但如果它是對的話..那這句話就是錯的
無論怎麼看它..都會有矛盾..人類的世界裡竟然出現了也不是對也不是錯的東西
這種self-referential structure只要出現就會帶來類似的災難
大部份的人不是裝作沒看見..要不然就是當作騙小孩的小技倆
但Godel卻利用它毀滅了Hilbert的數學天堂
(另一個相關的例子"這句話是對的"..它可以是對也可以是錯..它到底在講什麼?)
1929年..Godel在維也納大學的博士論文..證明了Limpid logic是complete的
Limpid logic是一種純語法的邏輯..不牽涉算術運算
當時他證明了這個大家早就認為是正確的東西
除了讓Hilbert Program更有信心外..其實沒有多少人注意到
然而他在1931年的一個研討會上..提到了自己新證明的一個定理
也就是著名的第一不完備定理 (first incompleteness theorem)
當時幾乎沒有獲得注意..只有Von Neumann發現這是個不得了的東西
和Godel交流後..Von Neumann很快地也得到了第二不完備定理 (Godel回應說那很直接就能得出)
也就是這第二不完備定理拆了Hilbert的台
甚至Von Neumann本來是屬於Hilbert陣營的..但他卻開始大力推銷這個理論
在接下來Godel的生涯中..Von Neumann不斷地在幫他..只能說英雄惜英雄啊
==============================================
接下來也是該是讓數學說話的時候了
First incompleteness theorem講的是
"In a finitary formal system with arithmetic, there is a proposition is true and unprovable."
也就是帶有算術運算的formal system..存在一個命題..其既為真卻又無法證明!
Godel透過將邏輯語法算術化
再神奇地利用一個關於可證明性的self-referential statement完成了這個證明
有東西是對的..但你無法證明它
更猜不透的是..它的對來自於它的不可證明性..真是太神奇了!
接下來既然有命題是無法證明的..代表該system無法自已證明所有命題是真或假
於是有了Second incompleteness theorem:
"In a finitary formal system with arithmetic, the consistency can't be proved."
這終結了許多數學家的夢想
當初Hilbert的夢想是想將數學去除人類直觀的部份..例如無限大和反證法等
若數學系統能在去除人類的因素下..冷漠地自行運作..那就等於找到絕對客觀的事實
Godel的結論並不是說同時consistent和complete的系統不存在 (甚至我們大部份的數學系統都是)
它說的是要證明這個東西 (以及其它很多東西)..你是無法排除人類直觀的部份的
他後來也得出要增加怎樣的東西就能得證
然而incompleteness卻也成為Positivist的最佳範本 (Human matters!)
甚至我們是否可以說..人類創造出來的數學系統..可能也只有人類知道
因為外星人若和我們擁有不同的直觀..創造出來的數學很有可能也會不同
例如可能外星人沒有無限大的觀念..他們的小孩就不用唸微積分了呢!
這個理論最實用的延伸..莫過於Alan Turing的計算機理論了 (Godel本人也非常認可)
Turing將formal system的定義置換成計算機的運作..這也是著名的Turing machine的由來
應用類似於Godel的證明方法..可以得到有演算法是undecidable or uncomputable的
在計算機的世界..undecidable or uncomputable和數學的unprovable是很類似的
簡單來說..計算機無法做到所有的事情
更哲學地推廣的話..有些人類直觀的部份..計算機是無法取代的
這結論也為人工智慧硬生生地畫下了邊界..計算機永遠是無法代替人腦的..只能冷漠地模仿而已
==============================================
最後來談一下Godel這個人
他在小時候就覺得自己比家人都聰明..覺得自己可以獨立完成任何事
8歲時得了一場高燒..造成心臟有些問題..但他也從此自認為自己身體很差
他在維也納大學時一開始唸的是物理..但最後轉為數學中最純的邏輯學
他在那裡也是Vienna Circle的一份子..裡面幾乎都是Positivist的天下
然而他在裡面幾乎不發一語..只是靜靜地聽大家的討論
他的個性不喜歡口語上的爭辯..因為那是沒有意義的
只有邏輯的證明才能讓人百口莫辯..從他對於Hilbert Program的態度就知道
然而在他發表了不完備定理後..學術生涯並不是就一帆風順
雖然Von Neumann在高等研究院一直推廣他的理論..甚至在1933-1934年還邀請他去那裡
也因此Alan Turing在1936-1937於高等研究院的停留才得已吸收Godel的理論
相反地他為了維也維大學講師的職位還得汲汲營營
甚至在1939年..希特勒取得政權開始興風作浪的同時
他還是決定從美國回到維也納..只為了捍衛他"講師"的權益
一個害怕冰箱會釋放毒氣的人..卻有勇氣做這樣的決定..真是匪疑所思
不過很快他就發現那不是他想待的地方..他甚至被歸類為適合從軍的人
這時高等研院的人決定聘請他..用盡了方法
讓他一路經過歐亞大陸, 俄國, 日本, 最後才到美國
之後他再也沒有離開美國..甚至幾乎沒離開過普林斯頓
他在高等研究院也幾乎是自我封閉的狀態
然而他和Einstein的友情也成為一段傳奇
在Einstein晚年的信中甚至寫道..他每天到高等研究院去..就只是為了能和Godel一起走路回家
或許這一大一小擁有相同的Platonist的特質..以及自己理論被外界詮釋得與自己不同有關吧
當然最重要的共同點..應該是幾乎同水平的思考和邏輯能力吧
Godel身後留下了天量的筆記和研究紀錄..大部份都是沒有發表的
因為還沒到達他自己的標準 (和Gauss有類似的情況)
其中他也暗自對相對論做了一番研究..在慶祝Einstein 70歲生日時應編輯的邀稿
他才把他自己對於相對論的數學系統發表..在那之前Einstein根本不知道他有這方面的研究
不過根據Godel數學系統..時間是呈柱狀的..於是回到過去是很有可能的
為了得到實驗結果來證明自己的系統..他做了人生第二次地檢驗實驗數據..甚至操作儀器
雖然結論是否定的..但也讓我們看到這位數學家的能力
只要他想做..他就能建立新的數學系統..甚至設計實驗和檢驗結果
在1955年Einstein過世後..他的封閉狀況越來越嚴重
他開始覺得有人要害他..甚至他老婆(以前是夜店舞孃)想花光他的錢
諷刺的是Von Neumann在1957年就因癌症過世
而他的好友Oskar Morgenstern(Game theory的second author)也在1977年過世
甚至Einstein在過世前還一直對他隱暪自己的病情
換來的是Godel一直在說自己的身體有多糟
但Godel成功地活到了70幾歲
但隨著最後的好友在1977年過世..以及老婆住院的影響
獨居的他幾乎是什麼都不吃
在1978年因為極度缺乏營養下過世了..簡單地來說就是自己把自己餓死了
不尋常的人生也以不尋常的方式結尾
==============================================
Note
1.
人類的思考方式..或說是證明手法主要分為三類: 演繹法, 反證法, 歸納法
但後面兩個是目前機器還是做不到的事
2. In an inconsistent system, any statement can be proved to be true (or false).
因為對於inconsisent system..存在某statement P..其值為true也為false
於是對於任一statement Q來說..(P or Q)必為true..因為P is true
但又因P is false & (P or Q) is true..Q is true
同樣的方式~Q is also true
這裡可以看到inconsistent system是一片災難..根本沒有任何意義
3. 如果可以用反證法的話..簡單版的incompleteness可由以下論述得出
G = "G is not provable"
=> ~G = "G is provable"
Assume G is provable -> ~G is true -> G is false
But G is provable -> G is true (just because you are able to prove G)
In a consisent system, there is no contradiction such that G must be unprovable.
Since G is not provable, G is true.
So G is true and unprovable.
4. 跳過讓過版的First incompleteness theorem的證明 (只包含大意沒有細節..反正細節也不懂)
Step 1: Godel number (證明很別出心裁的地方..也開啟了新的方向)
將所有statement都數字化
方法和寫程式很像 (應該是寫程式的概念是從這裡來的)
也就是將所有的符號都給定一個數字..於是任意statement都可以表示成一個數字串接起來的數字
於是對於statement P..可以得到Godel number GN(P)
Step 2: Unprovability proposition function
既然statement都已數字化..而且這是一個帶有算術運算的系統
這些Godel number也可以有自己的function F
而這function是一個statement (proposition function)..例如F(x) = "x是0"
Godel得出一diagonal lemma..也就是對於任一F..存在一數字n..使得 n = GN(F(n))
接下來重要的function出現..也就是unprovability function ~Pr()
其意義為 ~Pr(GN(P)) if and only if P is not provable
(這裡是證明最戲劇化的地方..將provability從邏輯性質轉變為算術性質..也是Godel最精巧的證明)
Step 3: The proof
由diagonal lemma可知..存在一數字g..使得g = GN(~Pr(g))
Let proposition G = ~Pr(g)..於是g= GN(G)
由~Pr()定義..~Pr(GN(G)) if and only if G is not provable
又因為g=GN(G) and G=~Pr(g)..所以~Pr(GN(G)) = ~Pr(g) = G
最後可得 G if and only if G is not provable!
Step 4: Ending proof outside the system
上面最後的statement是在該system內能得到的最後結論
G is true or false在formal system是無法演繹出來的
但若一跳出該system..由反證法和假設該系統為consistent可輕易得出G is true
於是there is a G true and unprovable for a consistent formal system with arithmetic!
最後一步的證明相當的諷刺..也再一次告訴我們formal system有無法證明的東西
必需跳脫出該system才能證明
完美的數學公設天堂是不可能存在的
==============================================
最後的最後..不禁想問..我們真的知道自己在證明什麼嗎?
我們真的了解別人的想法是什麼嗎?
因為Godel告訴我們最客觀的系統(冷冰冰的機械推演)是無法詮釋人類的知識的
於是人類的溝通和知識..有一大部份是建立在直觀上..但每個人的直觀真的都一樣嗎?
這種想法加深了Positivist的主觀科學論調
但對於Godel..一位Platonist..他認為理論事實是客觀地存在的
它們是不會因為有無人類存在而改變的
他是不會過度延伸自己的理論來改變這個想法
無論他怎麼想..最能代表他想法的就是他的證明..而這的確改變了人類的想法
留言列表
