哥德爾證明(上)-希爾伯特計劃

2021-01-15 佛系雞血陽爸

Wir müssen wissen, wir werden wissen.

我們必須知道,我們必將知道。——大衛·希爾伯特David Hilbert

希爾伯特

物理學家有一個夢想,將四種基本力整合到一個統一的理論中,它可以解釋一切的力,進而闡釋一切物理現象,是宇宙最深刻的秘密,是上帝造物的終極藍圖;

數學家有個小小的桃花源。兩千多年前,歐幾裡得的《幾何原本》從少量「自明的」定義、公理出發,推演整個幾何體系,並詮釋了一種探究真理的模式。

19世紀,社會上流行一種不可知論,「We do not know, we shall not know.」1930年,希爾伯特退休前,他在演講中激情澎湃的宣稱:「我們必須知道,我們必將知道!」 希爾伯特去世後,這句話就刻在了他的墓碑上。

希爾伯特最廣為人知的是,1900年巴黎國際數學家代表大會上,他發表的著名講演《數學問題》。希爾伯特根據過去數學研究的成果和發展趨勢,提出了23個最重要的數學問題,統稱為希爾伯特問題。希爾伯特問題作為諸多數學家力圖攻克的難關,對現代數學的研究和發展產生了深刻的影響,並起了積極的推動作用。希爾伯特問題中,有些現已得到圓滿解決,有些至今仍未解決。

希爾伯特涉獵多個數學領域,致力於為整個數學尋求一個堅實的基礎。對平面幾何的嚴格公理化只是他的一小步,他的目標是將整個數學體系嚴格公理化,然後再做出嚴謹的證明。1920年,他提出了希爾伯特計劃:

首先,將所有數學形式化,即,將數學陳述用符號表達;然後,證明這個形式化系統是無矛盾的(一致性、自洽性、或者相容性),並且是完全的(完備性),即,所有正確的陳述(就相當於定理了)都可以被證明出來;相關希爾伯特問題:第二問,算術公理系統的無矛盾性。最後,找到一種算法,來判斷一個陳述(命題)是否正確,即可判定性。(判斷機器?呵)相關希爾伯特問題:能求出一個整數係數方程的整數根,稱為丟番圖方程可解。第十問,是能否用一種算法(有限步),判斷一個丟番圖方程的可解性。

1931年,希爾伯特退休之後一年,哥德爾覆滅了希爾伯特計劃。

通俗的說,哥德爾證明了,任何無矛盾的(包含算術的)系統內,總有陳述是真的,可是沒法證明。任意包含了算術系統的數學系統,不可能同時是完備的和一致的。換句話說,總有陳述,我們無法知道真假,即不可判定。

嗯嗯,沒證明的猜想很多,只要我用得到的原理是對的,其他就隨便吧。可是,哥德爾的證明還包括,任意無矛盾的(包含了算術的)數學系統,不能在系統內部證明它的無矛盾性。(只是說在系統內不能證明,採用系統外的辦法,還是有可能的。比如說,自然數的皮亞諾公理的一致性可以在集合論中證明。)

好吧,希爾伯特計劃註定執行不下去了,有些東西根本沒法證明,我們到哪裡去找這樣的算法?

可是,系統其實可以是一致並完備的,例如一些較弱的系統(不包含算術,連自然數都定義不了)一階謂詞演算。在這樣的系統裡,所有正確的,都應該可以被證明。

可是,還是沒有這樣的機械算法。艾倫·圖靈Alan Mathison Turing證明了這樣的算法不存在,(還有其他數學家採用不同的方式,得到同樣的結論。)不過這是另外的故事了。

We do not know, we shall not know?

這樣說,圖靈證明停機問題是不可計算的,那停機問題到底有多「不可計算」?換個說法,到底有多難?設可計算問題的難度為0,有沒有比可計算問題難一點,比停機問題簡單一點的問題?有沒有比停機問題更難的問題?衡量這個「難度」的級別,被定義為「圖靈度」。數學家證明了,圖靈度的個數不可數,所有圖靈度組成了一個複雜但有序的結構。想像一個無窮高的樓梯,這裡只有地面是可計算問題,而這個無窮樓梯甚至是有殘疾人坡道的,就是說,連續的圖靈度。呵呵呵,雖然我自己都不知道我自己說的是什麼,可是,我們是可以研究「不可計算問題」的。

我覺得,假設有人給數學家提供了一個既不能證明、也不能證否的問題(嚴肅問題,不是噴火龍哈),那麼數學家一定是很興奮的。希爾伯特第一問題(稱之為CH)被證明:在現有公理系統「不能證明,也不能證否」,即獨立於現有公理系統。你可以簡單地說它對,或者錯,當然也可以繼續研究:「假設CH成立,那麼…」,當然,這也是建立新的公理系統的契機。

朗蘭茲綱領誕生於跨系統、跨數學分支的研究,它是一組意義深遠的猜想,揭示了數學各分支學科之間深刻的聯繫,橫貫整個數學世界。許多人相信,只要完成了朗蘭茲綱領中的工作,就可以實現數學的大一統。這是數學家的夢想。

套用古老的「知識的圓圈」,知道的越多,未知也越多。無須庸人自擾,我們實實在在的擴展,不是嗎?

回到哥德爾證明,我們將通過三個悖論,趨近哥德爾的思路。第一個,「這句話是假的」,真還是假?

相關焦點

  • 希爾伯特之夢,以及夢的破滅
    圖片來源:wikipedia 可以說,哥德爾粉碎了希爾伯特計劃。 在希爾伯特退休之時,哥德爾才剛剛登上數學舞臺。在某種意義上,正是希爾伯特間接將哥德爾引領到數理邏輯這個領域的。在希爾伯特和他的學生阿克曼合著的《數理邏輯原理》中,他們提到了這樣一個問題:在形式系統中,真的命題是否都是可證明的?這正是哥德爾博士論文的主題。在這篇論文中,哥德爾證明了一階謂詞演算是完備的,這就是不太著名的哥德爾完備性定理。
  • 哥德爾不完備定理
    例如,要證明某一微分方程式有解,則必須給出一個方法,把這個解找出來, 而不可僅證明「若無解會導致矛盾」,而這卻是一般數學家們所常用的方法。 希爾伯特不贊成布勞爾的看法,他認為若是如此數學的犧牲實在太大了, 那麼要如何使數學能立在一個堅固的基礎上呢?
  • 哥德爾:邏輯的邊界,一切都可證偽.
    1928年,希爾伯特和阿克曼合著的《理論邏輯綱要》出版,這是一本論述簡明、清晰,概括性強的好書,對哥德爾的啟發性很大。書中明確提出一個尚未解決的問題——狹義謂詞演算的完全性問題。哥德爾很快解決了這個問題,把結果寫成博士論文,成為他一生事業的開端。1929年秋天,他進行答辯。1930年2月得到批准取得博士學位。1930年夏天,哥德爾開始研究希爾伯特計劃,他想證明分析的無矛盾性。
  • 哥德爾證明 (下)
    這是兩句話,假設前一句的哥德爾數是m,後一句的哥德爾數是n,定義這個字符串序列的哥德爾數為2m×3n,指數是對應字符串的哥德爾數,底數是從2開始的素數(質數),從小往大排,如果有第三句話,就用5做底數,……為方便表示,用k來表示這個數,k=2m×3n。定義3:證明Dem (k,n):字符串序列k,證明了字符串n,表示為Dem (k,n)。
  • 水數學——哥德爾不完備定理
    庫爾特·哥德爾是奧匈帝國的一位邏輯學家、數學家和哲學家。
  • 逃離上帝之路:從羅素悖論、哥德爾不完備性到測不準原理
    於是,數學界提出了雄心勃勃的「希爾伯特計劃」。希爾伯特認為,通過這個簡單的系統,他的計劃是可以解決的。希爾伯特計劃大約在1922年問世後,吸引了許多數學家為實現這一計劃去努力工作,一些簡單的問題先後被證明,這些成績的取得更增強了希爾伯特及其追隨者的信心。「我們必須知道,我們必將知道。」就是希爾伯特在1930年退休演講時發出的豪言壯語。
  • 誰才是百年計算機的數學靈魂:萊布尼茨、圖靈還是希爾伯特?
    大衛希爾伯特希爾伯特是20世紀的數學領袖,1900年他在數學家大會上指出的23個問題,其中第二個便是關於算術一致性的問題。希爾伯特綱領所提出的主要問題就是算術一致性問題。為了解決這個問題,希爾伯特發展出了元數學,一致性證明將在元數學內部完成。
  • 人類認知的大限,哥德爾不完備性定律,令科學家絕望!
    在經歷了幾乎無數堂證明未果的課以後,有一天閔可夫斯基來上課的時候,天上突然打了一個雷,閔可夫斯基對著教室裡的學生說:上帝被我的傲慢激怒了!後來進入計算機時代,地圖4色猜想,被兩個美國數學家用窮舉法證明了!在計算機上用了1000多個小時,相當於數學家們算30多萬年。看來眼高手低是所有人的通病!
  • 哥德爾證明(中)-三個悖論
    哥德爾證明實際就是上述悖論的變種。他構造了一個陳述G,G=「此陳述不可證明」。如果G為真,G就不可證明。(系統不完備)如果G為假,即,此陳述可證,那麼G為真。(系統得出G假且G真,系統有矛盾)即,無矛盾的(包含算術的)系統內,總有陳述是真的,可是沒法證明。
  • 霍金為什麼說哥德爾定理是物理學的終結?
    在哥德爾定理出現之前,數學家認為公理系統中的命題要麼是真命題,要麼是偽命題,而且真命題一定可以被證明——完全從幾條公理出發(或者對公理進行擴展),經過邏輯推理而進行證明。但哥德爾定理指出,包含一階謂詞邏輯和初等算術的一致性公理系統中,必定存在著至少一個命題,這個命題是一個真命題,但是不可能被證明,同樣不可能被證偽!
  • 書評:被愛因斯坦視為知己的哥德爾的邏輯人生
    他的不完全性定理不僅使數學發生革命性的變化,而且改變了整個科學世界和建築於此定理之上的哲學,還波及語言學、計算機科學、宇宙學,甚至包括法律上的「無罪推定」。對於人類來說,不了解哥德爾就不了解人類已達到的智力水平與人類智力奮鬥的歷程,也就無法了解我們這個世界在思想觀念上已經發生或正在發生的深刻變化。 哥德爾被認為是自亞里斯多德以來最偉大的邏輯學家。
  • 希爾伯特和布勞威爾之戰,誰才是「救世主」,拯救數學於衰退
    20世紀的早期,希爾伯特在不變量理論和變分法方面做出了開創性的工作,並出版了一本極具影響的幾何學著作。因此被多國選為科學院院士,並榮獲德國政府的樞密院顧問頭銜,可謂聲名卓著。形式主義的開端希爾伯特受邀在第一屆巴黎國際數學大會上做演講,在演講中他談到當時最富挑戰性的10個問題,開頭三個都是關於數學基礎的。第一個問題,證明康託爾的連續統假設。
  • 數學家們的美好理想,全被哥德爾打破
    哥德爾為啥呢?因為哥德爾不完備定理。20世紀初的時候,以希爾伯特為首的數學家們有一個夢想,就是證明數學是自恰的。什麼叫數學是自恰的呢?就是數學這個體系可以做到,在以一定的公理出發,在數學邏輯的運行下,推論出來的所有的定理,都是相融的,不會出現自相矛盾的地方。但是哥德爾,一個奧地利邏輯學家,卻用他的不完備定理,打破了數學家們的美好理想。
  • 20世紀最重要的數學真理:哥德爾不完備定理
    哥德爾悖論說謊者悖論、卡羅爾悖論、芝諾悖論、希爾伯特悖論,所有這些悖論都與哥德爾的不完全性定理有關,並在歷史上導致了這個定理的誕生。庫爾特·哥德爾是一位邏輯學家,生於 1906 年,卒於 1978 年。他證明了一個關於數學極限性的定理(該成果發表在 1931 年的論文中),這在當時的數學家看來是相當令人震驚的。
  • 搗蛋鬼哥德爾
    錯過的小夥伴可以掃描下圖二維碼進入回看哦~文章節選自《量子大嘮嗑》第一部分 第九章 搗蛋鬼哥德爾自從哥德爾不完備性定理被證明以來,越來越多的數學系統內的問題被證明是不可判定的哥德爾證明在一個邏輯系統中,一定會產生無法證明且無法證偽的命題,而這個邏輯系統的限定條件非常的寬泛,幾乎覆蓋了所有邏輯範疇,它不適用的範圍,反而成了我們現在需要探求的問題。從本質上講,哥德爾不完備性定理否定了兩件我們習以為常的事情:其一,真理的否定。我們建立的邏輯系統裡,推理的根本目的就是澄清這個邏輯系統內部每個命題的真偽,這是理性精神的基本體現。
  • 哥德爾旋轉宇宙新發現
    庫爾特·哥德爾(Kurt Godel)(1906年4月28日—1978年1月14日)是位著名的數學家、是繼亞里斯多德後最重要的邏輯學家,他也是一個善於思考的哲學家。其最傑出的貢獻是哥德爾不完全性定理和連續統假設的相對協調性證明。不完全性定理指出:即使把初等數論形式化之後,在這個形式的演繹系統中也總可以找出一個合理的命題來,在該系統中既無法證明它為真,也無法證明它為假。
  • 「哥德爾綱領與終極L」講座報導
    郝教授的主要研究方向是數學哲學和哥德爾的思想,他把數學定理視為數學世界的事實,可以描述甚至預測數學世界,一如物理定理與物理世界的關係。本場講座主要關注的問題有兩個:一是哥德爾綱領;另一是試圖解決哥德爾綱領的構造類,終極L。
  • 哥德爾邏輯謎題no.1
    哥德爾島上只有君子和小人,君子只說真話,小人只說假話,如果現在有甲乙二人甲:乙是君子乙:或者甲是小人,或者我是小人這可能嗎?世紀天才——庫爾特·哥德爾哥德爾20世紀是人類歷史上一個偉大的世紀,伴隨著眾多偉人的誕生,庫爾特·哥德爾就是其中之一。哥德爾是位邏輯學家,數學家和哲學家。哥德爾發展了馮諾依曼等人的工作,其主要貢獻在邏輯學和數學基礎方面,並以發現了著名的哥德爾不完備性定理而聞名於世。