哥德爾不完備定理
最近找了不完備定理來看，一是作為挑戰，亦是吃飽沒事做。比起找哥德爾的論文來看，我更喜歡找一些簡化了的文章，尤其是中文的，容易理解。
網上找了些文章看，有些有用，有些沒用，幾篇摻合下自己算是理出了一點思維，茲嘗記下。自問對數理邏輯的知識薄弱，一些專業用詞未必符合正統用法，就請湊合着。
一・基要概念
不完備定理與自我推翻的謬誤有相同之此，二者皆有自我牽涉；[1]自我推翻較易理解，不妨先拿來熱身。
- 有人說了一句，我們會怎樣做？用問題的形式來表達，我們大概會問：這句子是什麼意思？這句子是否正確？
通過理解句子的意思，進而判斷其為正確與否，謂二基本進路。
設句子能分真假，一句子若為真，則有真值。不妨將一句子想像成一個體，其有兩部分：其意義、其真假值。 - 「此句不是中文」
將此句想作兩部分：其意義，其真假值。
我們嘗試理解此句之意義，再看這句子，卻知其確是用中文寫成，則判斷此句為錯，假。 - 這種句子注定是必錯／假的，在於其有自我推翻之性質，與有人在說「我沒有說話」一樣滑稽。
他的行為使他的話變假。 - 「此句不是中文」使自己句子的構成牽涉自己的真假，這就是上說的自我牽涉。
在說「我沒有說話」的時候，他這說話的嘴巴就出賣了他的腦袋。 - 「所有句子都是錯的」
若這句為真，則所有句子都是錯的，但所有自應包括它自己。既然構成自相矛盾的局面，這句只能必然為假。
二・機器比喻
有一個簡化的比喻，就設想有一部懂得真理機器。
- 假設有一機器，此機器只會列印真理。輸入一句說話，若他列印此句出來，則此句為真；若他拒絕列印此句，則此句為假。
那機器如何判斷一公理為真為假？此機器實無須要說服我們其判準何來。 - 為了挑戰這機器，我輸入「我無法被列印」。此時機器就陷入兩難狀態。
- 若此句從未被列印，機器判斷這句為真。既然此句為真，則機器雖列印這句子以告知其為真。但機器在列印的過程，卻使此句變為假。[2]
若機器知道其列印過程使此句變為錯誤，而不作列印，則此句為真，而他無法透過列印來告知此句為真。 - 則此機器無法透過列印此行動告知他人所有真理。
而機器無法告知的真理有一特性，牽涉機器告知正確之動作。
三・核心比喻
- 「我不能被證明」。
- 若我們證明此句為真，則此真句表示它無法被證明，導致一自相矛盾局面。自相矛盾句為必假，則此系統證明了假的句子，不一致也。
若我們無法證明此句之真假，則此句為真。為真卻無法被證明，不完備也。 - 有人問，那若我們能證明此句為假則沒問題了？證明此句為假，則此假句亦在說其可被證明，不就皆大歡喜？
問題在於，哥德爾證明了一個數學系統內可說出這句，而數學家皆明白這句是真的，只是此數學系統無法證明此句為真。
四・放入數學系統
此處只粗略列出一些我認為重要的細節，沒興趣者可略過。
- 從不能至不存在
- 准確點寫，放入數學系統的句子是「我不能在此系統內被證明」。
- 如何將不能放進一個數學系統，寫作函數？
能不能涉及能力，我不能做一件事，我能做一件事。
我做一件事可證明我能做一件事；但如何證明我不能做一件事？
我不做一件事？不做並不等同不能。想也頭痛吧？原來證明自己無能也是如此困難。 - 哥德爾的神來之筆來了，人會隨着時間變化，死後如何是不可知的，所以未來的可能性總是開放的。你說你不能做一件事，但你將來總有機會為自己證偽，即使機率如何少。
- 人做了一件事，這事件就會存於這個宇宙。或許名流青史，或可能只有天知道。
數學系統的證明事件更明顯，其自身由定義的公設構成；我們或許不知道這證明的樣子，卻可用代號來指名。 - 能做一件事；做了一件事；做事留痕。
「我不能被證明」看上去難以放進一個數學系統。哥德爾將其轉為「不存在證明我之證明」。有點拗口？不妨改作「不存在推論我為真假之證明」。（英文可用prove, proof 來替換）
這時，能不能，就轉變成存不存在的問題。若一數學系統能推出一證明，則此證明必然存在。若不能，則證明不存在。
人能做一事而選擇不做一事。數學系統並不存在此問題，能則有，不能則無。 - 當哥德爾在系統內寫出「不存在推論我為真假之證明」之時，則成功瞄準了一個不存在的證明，他終於能證明有一命題是無法被證明了；能證明其命題為真的系統是內藏矛盾。
數學系統的存在太清晰了，不像人類的潛能般隱隱，亦不存在未來被證偽的開放性，只能承認自己不是萬能的。 - 數學系統多瀟灑，認栽就算了，人在死前卻總有籍口去辯解，凡邏輯可能之事總有可能，即使其可能機微。這還未算上人有永生、重生之未來開放可能。
- 分身
- 在書寫「不存在推論我為真假之證明」時，哥德爾須要預備一遞歸函數。[3]
「F(x) = x 不能被證明」 - x 須指涉回 F() 自身，所以 x 實為 F() 一分身。那如何弄一分身？哥德爾弄了點手腳。
- 推論 F() 的證明，是一連串步驟。這些步驟可改用數字編碼來表示。x = 12, -> = 64, y = 13⋯⋯
則 x -> y 可用一編碼表改寫為 12 64 13。
如此則可將 推論 F() 之證明以數字表示。[4]若此系統能表達數字，那他亦能以數字表達所有邏輯可能存在之證明，包括 推論 F() 之證明。
G(F)，就是 推論 F() 的證明之數碼表達，這或許是很長的數字串。 - 從不能變作不存在時，哥德爾加入了量的概念，從能不能變成存不存在。數字串雖然是無限多，卻總算可將不能轉變為不存在。
哥德爾無法將無限的數字列出來去說這證明不存在，卻可以借用自我牽涉導致的詭境來說這證明不存在。
「F(x) = 不存在推論我為真假之證明」
變作：
「F( G(F) ) = 不存在一數字串與 G(F) 相同」 - 若 F( G(F)) 為真，能證明 F( G(F)) 則能推出 F( G(F))，自相矛盾也。
若 F( G(F)) 為真，不能證明 F( G(F)) 則符合 F( G(F)) 的意思：他不能被證明。如此則數學系統不是萬能，不能證明所有真理。 - 為啥數學家覺得這樣的命題 在一數學系統裡出現為正常？天曉得。有興趣的人儘管去最後找文章爬，別問我。
五・極限
「不能被證明」至「不存在此一證明」至「不存在此一證明編譯之數字串」。好吧，面對如此智力的壓制，凡人只能敬佩不已萬分自嘆自愚吧？
但「我不能被證明」似乎有一缺陷？
- 「機器無法透過打印告訴你我是對」
「數學系統無法透過證明告訴你我是對」 - 機器和數學系統的分別在於，我們可懷疑機器的判定理據何在，但數學系統的證明卻是合符理性，足以自證。
兩者相同在於，從「我無法被証明」至「我無法被此系統証明」，至「此系統無法告訴尋問者，我之對錯」。 - 告訴我們對錯之告訴，乃一行動，若我們將機器與數學系統合體，則可得出一數學系統機器，能透過列印或證明來告知對錯。
如是，此一合體機器遇到「我無法被列印」時，可透過另一方法邏輯證明來告知對錯；遇到「我無法被證明」，可用列印來告知對錯。 - 不過，此一合體機器遇到「我不能被列印或證明」，就沒徹了。
那再合併多一組件如何？遇到「此系統無法告知我之對錯」還是無能，因為你所有的告知方法都被封截了。你已經死了…… - 但我們還是幸運的，數學系統即使無法證明 有關 自我牽涉 之真理，也能證明很多東西。
至於潛能、事件、無限事件對應潛能、數學系統與人的關係，當中或有奇妙，待妙想大開之時再贅。
能否將「我無法被人類告知／得知／理解為真」一句改成真句？若其為真，則無法被人類告知他物為真；無法被人類得知為真；無法被人類理解其為真（或者外星人或電腦能告知其為真，不過人類還是無法理解）。不過果真存在此一真理，我亦不能告知他人／得知／理解此為真理。面對如此真理，大概也只能沉默不語了。
[1]：對於自我指涉之用法不敢肯定，不如自立一詞方便說明。
[2]：假設機器只能在瞬間，列印此句，不存在時滯。
[3]：對數理邏輯實學所知極少，或有誤。
[4]：一個比較「強」的數學系統都能用遞歸／set 來表達自然數？
諸有用之參考文章：
較為詳盡之證明，但需用心緊貼其推論
http://en.wikipedia.org/wiki/Proof_sketch_for_G%C3%B6del%27s_first_incompleteness_theorem#Self-referential_formula
寫的簡明，但沒論述如何將「我無法被證明」置入系統裡之細節
http://episte.math.ntu.edu.tw/articles/mm/mm_15_4_11/
懂編程的人大概能明白停機問題，對角線也寫的一般，不完備定理則感到不到肉
http://mindhacks.cn/2006/10/15/cantor-godel-turing-an-eternal-golden-diagonal/
機器比喻取材自此
http://rationalwiki.org/wiki/Essay:G%C3%B6del's_incompleteness_theorem_simply_explained
留言
發佈留言