|
|
哥德爾不完全性定理
哥德爾不完全性定理 哥德爾是德國著名數學家,不完備性定理是他在1931年提出來的.這一理論使數學基礎研究發生了劃時代的變化,更是現代邏輯史上很重要的一座里程碑.該定理與塔斯基的形式語言的真理論,圖靈機和判定問題,被贊譽為現代邏輯科學在哲學方面的三大成果.
哥德爾證明了任何一個形式體係,衹要包括了簡單的初等數論描述,而且是一致的,它必定包含某些體係內所允許的方法既不能證明也不能正偽的命題.
歌德爾第一不完全定理:設係統s包含有一階謂詞邏輯與初等數論,如果s是一致的,則下文的t與非t在s中均不可證.設下述公式的編碼為q，
歌德爾第二不完全定理:如果係統s含有初等數論，當s無矛盾時，它的無矛盾性不可能在s內證明。
從悖論開始
悖論就是邏輯上的自相矛盾，似是而非，似非而是。註意，必須是邏輯上不同纔是悖論。“先有雞還是先有蛋這”句話就不是悖論，因為這個問題的關鍵在於如何定義雞和蛋，和邏輯和悖論沒一點關係。
最古老的悖論是兩千多年前剋裏特島的“說謊者悖論”，若你說它是假命題的話.就可推出它是真命題，反之亦然。其最簡形式就是：
本句子是假的
這種悖論屬於語義悖論，悖論還有循環悖論等。此處從略。
哥德爾不完全性定理的由來
雖然與悖論打了幾千年交道，可數學家們不覺得他們可怕，因為他們與數學無關。直到20世紀，一小撮聰明人才隱約覺察到，在悖論中有着一些深刻的數學理論。
事情要從崇尚理性的文藝復興時期談起，當時的學者如笛卡兒、萊布尼茨等都想創造一個理論解决一切問題。萊布尼茨甚至設想把邏輯學用數學符號表示，以後每逢爭論，拿支筆一算就見分曉了。事實證明，萊布尼茨的對符號邏輯的建立起了很大作用。
萊布尼茨太超前了，沒能完成他的夙願。又過了200年，著名學者康托爾提出集合論，為統一數學提供了一綫希望。
集合論的出現，標志着數學的誕生。有了集合論，人們就沒必要（也不能）發明更廣層次的理論了。
就在數學家躊躇滿志的時候，集合論中出現了悖論。康托爾自己就發現了一個（包含一切集合的集合是否存在？），更嚴重的是羅素悖論，其中也出現了以自己為元素的集合。兩個悖論攪得數學王國不得安寧，史稱“第三次數學危機”。後來這種定義被公裏排斥掉了，數學王國又恢復了平靜。不過很快，人們就意識到，這不過是“虛假的繁榮”。
不識廬山真面目，衹緣身在此山中。這兩句話深刻地說明，衹有站在更高的層次，才能看到更多的“風景”。那麽，我們有望看到整個數學的風景嗎？
20世紀60年代，在集合論不斷發展的基礎上，大數學家希爾伯特嚮全世界的數學家拋出了個宏偉計劃，其大意是建立一組公理體係，使一切數學命題原則上都可由此勁有限步推定真偽，這叫做公理體係的“完備性”；希爾伯特還要求公理體係保持“獨立性”（即所有公理都是互相獨立的，以保持公理係統最簡潔）和“無矛盾性”（即相容性，公理和公理之間不能是自相矛盾的）。
值得指出的是，希爾伯特所說的公理不是我們通常認為的公裏，而是經過了徹底的形式化。他們存在與一們叫做元數學的分支中。元數學與一般數學理論的關係有點像計算機中應用程序和普通文件的關係。
希爾伯特是個樂觀主義者，他的計劃也確實有一定的進展，幾乎全世界的數學家都樂觀地看着數學大廈即將竣工。正當一切都越來越明朗之際，突然一聲晴天霹靂。1931年，在希爾伯特提出計劃不到3年，年輕的哥德爾就使希爾伯特的夢想變成了令人沮喪的噩夢。哥德爾證明：任何無矛盾的公理體係，衹要包含初等算術的陳述，則必定存在一個不可判定命題，用這組公理不能在有限步內判定其真假。也就是說，“無矛盾”和“完備”是不能同時滿足的！這便是聞名於世的哥德爾不完全性定理。
哥德爾不完全性定理的影響
哥德爾不完全性定理一舉粉碎了數學家兩千年來的信念。他告訴我們，真與可證是兩個概念。可證的一定是真的，但真的不一定可證。某種意義上，悖論的陰影將永遠伴隨着我們。無怪乎大數學家外爾發出這樣的感嘆：“上帝是存在的，因為數學無疑是相容的；魔鬼也是存在的，因為我們不能證明這種相容性。”
但是哥德爾不完全性定理的影響遠遠超出了數學的範圍。它不僅使數學、邏輯學發生革命性的變化，引發了許多富有挑戰性的問題，而且還涉及哲學、語言學和計算機科學，甚至宇宙學。2002年8月17日，著名宇宙學家霍金在北京舉行的國際弦理論會議上發表了題為《哥德爾與m理論》的報告，認為建立一個單一的描述宇宙的大統一理論是不太可能的，這一推測也正是基於哥德爾不完全性定理。
有意思的是，在現在十分熱門的人工智能領域，哥德爾不完全性定理是否適用也成為了人們議論的焦點。1961年，牛津大學的哲學家盧卡斯提出，根據哥德爾不完全性定理，機器不可能具有人的心智。他的觀點激起了很多人反對。他們認為，哥德爾不完全性定理與機器有無心智其實沒有關係，但哥德爾不完全性定理對人的限製，同樣也適用於機器倒是事實。
哥德爾不完全性定理的影響如此之廣泛，難怪哥德爾會被看作當代最有影響力的智慧巨人之一，受到人們的永恆懷念。美國《時代》雜志曾評選出20世紀100個最偉大的人物，在數學家中，排在第一的就是哥德爾。 |
|
悖論就是邏輯上的自相矛盾，似是而非，似非而是。註意，必須是邏輯上不同纔是悖論。“先有雞還是先有蛋”這句話就不是悖論，因為這個問題的關鍵在於如何定義雞和蛋，和邏輯和悖論沒一點關係。
最古老的悖論是兩千多年前剋裏特島的“說謊者悖論”，若你說它是假命題的話.就可推出它是真命題，反之亦然。其最簡形式就是：
本命題是不可證明的。
這種悖論屬於語義悖論，悖論還有循環悖論等。此處從略。 |
|
雖然與悖論打了幾千年交道，可數學家們不覺得他們可怕，因為他們與數學無關。直到20世紀，一小撮聰明人才隱約覺察到，在悖論中有着一些深刻的數學理論。
事情要從崇尚理性的文藝復興時期談起，當時的學者如笛卡兒、萊布尼茨等都想創造一個理論解决一切問題。萊布尼茨甚至設想把邏輯學用數學符號表示，以後每逢爭論，拿支筆一算就見分曉了。事實證明，萊布尼茨的對符號邏輯的建立起了很大作用。
萊布尼茨太超前了，沒能完成他的夙願。又過了200年，著名學者康托爾提出集合論，為統一數學提供了一綫希望。
集合論的出現，標志着數學的誕生。有了集合論，人們就沒必要（也不能）發明更廣層次的理論了。
就在數學家躊躇滿志的時候，集合論中出現了悖論。康托爾自己就發現了一個（包含一切集合的集合是否存在？），更嚴重的是羅素悖論，其中也出現了以自己為元素的集合。兩個悖論攪得數學王國不得安寧，史稱“第三次數學危機”。後來這種定義被公理排斥掉了，數學王國又恢復了平靜。不過很快，人們就意識到，這不過是“虛假的繁榮”。
不識廬山真面目，衹緣身在此山中。這兩句話深刻地說明，衹有站在更高的層次，才能看到更多的“風景”。那麽，我們有望看到整個數學的風景嗎？
20世紀20年代，在集合論不斷發展的基礎上，大數學家希爾伯特嚮全世界的數學家拋出了個宏偉計劃，其大意是建立一組公理體係，使一切數學命題原則上都可由此勁有限步推定真偽，這叫做公理體係的“完備性”；希爾伯特還要求公理體係保持“獨立性”（即所有公理都是互相獨立的，以保持公理係統最簡潔）和“無矛盾性”（即相容性，公理和公理之間不能是自相矛盾的）。
值得指出的是，希爾伯特所說的公理不是我們通常認為的公理，而是經過了徹底的形式化。他們存在於一門叫做元數學的分支中。元數學與一般數學理論的關係有點像計算機中應用程序和普通文件的關係。
希爾伯特是個樂觀主義者，他的計劃也確實有一定的進展，幾乎全世界的數學家都樂觀地看着數學大廈即將竣工。正當一切都越來越明朗之際，突然一聲晴天霹靂。1931年，在希爾伯特提出計劃不到3年，年輕的哥德爾就使希爾伯特的夢想變成了令人沮喪的噩夢。哥德爾證明：任何無矛盾的公理體係，衹要包含初等算術的陳述，則必定存在一個不可判定命題，用這組公理不能在有限步內判定其真假。也就是說，“無矛盾”和“完備”是不能同時滿足的！這便是聞名於世的哥德爾不完全性定理。 |
|
哥德爾不完全性定理一舉粉碎了數學家兩千年來的信念。他告訴我們，真與可證是兩個概念。可證的一定是真的，但真的不一定可證。某種意義上，悖論的陰影將永遠伴隨着我們。無怪乎大數學家外爾發出這樣的感嘆：“上帝是存在的，因為數學無疑是相容的；魔鬼也是存在的，因為我們不能證明這種相容性。”
但是哥德爾不完全性定理的影響遠遠超出了數學的範圍。它不僅使數學、邏輯學發生革命性的變化，引發了許多富有挑戰性的問題，而且還涉及哲學、語言學和計算機科學，甚至宇宙學。2002年8月17日，著名宇宙學家霍金在北京舉行的國際弦理論會議上發表了題為《哥德爾與M理論》的報告，認為建立一個單一的描述宇宙的大統一理論是不太可能的，這一推測也正是基於哥德爾不完全性定理。
有意思的是，在現在十分熱門的人工智能領域，哥德爾不完全性定理是否適用也成為了人們議論的焦點。1961年，牛津大學的哲學家盧卡斯提出，根據哥德爾不完全性定理，機器不可能具有人的心智。他的觀點激起了很多人反對。他們認為，哥德爾不完全性定理與機器有無心智其實沒有關係，但哥德爾不完全性定理對人的限製，同樣也適用於機器倒是事實。
哥德爾不完全性定理的影響如此之廣泛，難怪哥德爾會被看作當代最有影響力的智慧巨人之一，受到人們的永恆懷念。美國《時代》雜志曾評選出20世紀100個最偉大的人物，在數學家中，排在第一的就是哥德爾。 |