哥德尔不完备性定理共72张课件.ppt

1、哥德爾不完備性定理Gdels Incompleteness Theorems序希爾伯特的23個數學問題The Hilbert Challenge目標:不完備性定理的內容與歷史緣由The Hilbert Challenge1.連續統假設2.算術公理之完備性算術公理之完備性3.歐氏體積之定義4.直線與最短距離5.李群6.物理之公理化7.某些數的超越姓8.黎曼猜想與哥德巴赫猜想9.一般形式的互反律10.丟番圖方程11.任意二次形式12.克羅內克的青春之夢13.圖算法14.不變量的有限性15.舒伯特的計數演算16.曲線的拓樸;邊界圈的個數17.平方和的函數18.多面體的全等,基本域與裝球問題19.偏微

2、分方程的正則性20.變分法與邊界條件21.黎曼 希爾伯特問題22.單值化定理23.變分法中的新方法就最初淺的意義而言，公理是指一些“我們我們先先決接受為真決接受為真”的東西，用以作為我們討論一門科學的起點對於物理學而言，“能量守恆”是一條公理對於歐氏幾何而言，“平行線永不相交”是一條公理何謂公理由於公理可以說是一系列存而不證的假設，所以我們希望公理是越少越好越少越好而若是有一條公理，它能夠由其他的公理所推出來，那這條公理就是多餘的多餘的因此，公理之間應該是互相獨立的互相獨立的，也就是說，你不能由其中若干條推出另一條出來公理應該要是互相獨立的作為一門科學的基礎，一套公理應該要容許我們能夠對這門科

3、學下的每條命題加以判別為真或為假因此，一個公理系統應該是完備的完備的，應該能夠對系統下的每條命題加以證明或否證也就是說，不應該容許不可判定命題不可判定命題的出現，例如：“本命題不可被證明”公理系統應該要是完備的請注意以下兩者的差別：“本命題是假的”是既不真也不假，“沒有真假值沒有真假值”的句子“本命題不可被證明”是不能被證明證明為真也不能被證明證明為假它可能還是有真假值它可能還是有真假值希爾伯特想知道說，我們的數學體系究竟是不是完備的？是否在數學中，存在有不可判定命題？他認為數學體系是完備的，並嘗試去證明他的想法是，幾何可以用座標體系一一對應到數域上，而整個數域又以算術：整數和加減乘除為基礎，

4、因此，只要證明算術系統是完備的，就能證明整個數學體系是完備的第二問題算術公理的完備性證明皮亞諾算術公理系統是完備的，進而證明整個數學系統是完備的就算是完備的又如何？在自然數集合大小與實數集合大小之間，沒有其他的集合大小如果是完備的，希爾伯特想要用它來證明像是第一問題之類的東西第一問題連續統假設自然數和偶數是一樣多的，什麼是集合的大小？當我們說兩個集合一樣大時，是指說兩個集合的元素之間，存在一種一一對應一一對應正有理數和自然數是一樣多的111221132231(0,1)實數和自然數是不一樣多的0.2471260.1732810.6665190.3119230.2188260.391830.276

5、92如果第二問題成立，則當我們要證明在自然數集合大小與實數集合大小之間，沒有其他的集合大小時，只要先在公理中多假設有第假設有第三種大小的存在三種大小的存在，然後推出一個不可判定命推出一個不可判定命題題便能證明哥德爾第一不完備性定理皮亞諾公理系統是不完備的皮亞諾公理系統是不完備的，也就是說，在算術系統中，我們總是能夠找到一個不可判定命題證明思路1.為了限制符號的數量，將算術系統算術系統轉換為量量化邏輯化邏輯的公理系統2.討論在這樣的系統中，什麼樣的命題是可以可以確實被寫出來的確實被寫出來的（可表達性定理）3.將所有可以被寫出來的命題與證明編號，並藉此提供一個判別某證明是否為一個命題判別某證明是否

6、為一個命題的一個證明的一個證明的方法4.藉由2,3,實際寫出句子：“本命題不可被證明本命題不可被證明”藉此證明不完全性定理介紹流程1.淺介量化邏輯2.將算術系統表成量化邏輯3.介紹可表達性定理的數個特例4.將系統下的所有證明編號並給出一個判別證明的方法5.利用3,4 寫出“這個命題不可被證明這個命題不可被證明”這一個句子，藉此證明哥德爾第一不完備性定理壹量化邏輯Quantificational Logic目標:淺介量化邏輯名詞命題：可以判別真假的句子是非負整數這句話是假的定理：可以被證明為真的命題公理：先決被認定為真的命題是非負整數1.非2.且3.或4.蘊含5.對於所有 6.存在7.邏輯符號)

7、()(xPx)()(xPx真值表 命題：命題的真假簡化符號,)()(xAxBA 等價於BA)(BA 等價於)(BA 等價於)()(xAxAx)!(等價於)()()()(2121AxxxAx所以我們事實上只需要三種符號：量化邏輯下的論證原論證：若是整數且不可被整除，則是奇數前提是整數前提不可被整除結論是奇數因此原論證可表為：量化邏輯下的證明，將數學證明轉為邏輯證明的例子原證明引入定理一：“若是整數，則是奇數或是偶數”由前提一知“是奇數或是偶數”再引入定理二：“若是偶數，則可被整除”由前提二知“不是偶數”因此“是奇數”若是整數且不可被整除，則是奇數（是整數）（不可被整除）令是偶數（）定理一，定理二

8、，請注意，證明是一組“無矛盾的命題序列無矛盾的命題序列”量化邏輯下的公理系1.邏輯符號如，2.語句符號如，3.個體常元如，4.個體變元如，5.函數符號如（）6.關係符號如（，）表7.公理如（）（）貳算術系統與皮亞諾公理EA and Peano Axioms目標:將算術系統表成量化邏輯皮亞諾的五條算術公理1.是一個非負整數2.每個非負整數，都有不同於的後繼元素3.不存在非負整數，使得為4.對於任意非負整數和，如果，那麼5.對於任何含有的非負整數集合，如果對任意的屬於，都有屬於，那麼含有所有的非負整數6.上述五條公理確立了非負整數集.關係符號：“”這個符號蘊含著兩個公理：nn（，）（，）其中是任意

9、函數或關係以上兩條相等公理確立了的性質是一個非負整數個體常元每個自然數，都有不同於的後繼函數不存在非負整數，使得為公理：)0()(xx將皮亞諾公設表成量化邏輯對於任意非負整數和，如果，那麼對於任何含有的非負整數集合，如果對任意的屬於，都有屬於，那麼含有所有的非負整數)()()(212121xxxxxx)()()1()()()0(xSxxSxSxS函數符號：和)0)(.(1xxx)()()(.(2212121xxxxxx)00*)(.(3xx)*()*)()(.(41212121xxxxxxx“”的性質由以下兩條性質確立：“”的性質由以下兩條性質確立：一階算術系統運算符號（），語句字母個體常元個

10、體變元函數符號關係符號公理相等公理二條皮亞諾公理三條加法公理二條乘法公理二條備註嚴謹的一階算術系統運算符號（），語句字母個體常元個體變元函數符號n(x)a(x,y)m(x,y)關係符號e(x,y)公理相等公理二條皮亞諾公理三條加法公理二條乘法公理二條參可表達性定理目標:了解什麼樣的句子是可以被寫出來的何謂可表達?一個元關係（，）可表達若且唯若有一個元命題（，）使得（，）成立若且唯若（，）為真“21”可以用下列命題表示：“（）”可表為：)(2313xxxx)()()(22121xAxxxxA“”這個關係可以表為：“是質數”這個關係可以表為：)*)(2313xxxx)|()1()()(1111px

11、xxpx可表達性定理可表達性定理保證：若關係“（，）”與關係“（，）”都可表達，而遞迴函數遞迴函數滿足1.（，）（，）2.（，）3.（，（，）4.則關係：5.“（，）”可表達可表達函數（，）可以用函數：（）（，）表成遞迴：（，）（）（，）（，（，）又關係“”及“”顯然都可表達，故由可表達性定理知：可表達可表達可表達性定理的簡略證明引理一若（，）表示除除的餘數的餘數，則“（，）”可用：引理二若：（，）（，（）則由引理一知可表達，記它的表達式為（，）)()*)(:2334214xxxxxxxR引理三 對於任何一個序列，存在適合的，使得：（，）證明：令max（，）！考察數列（），顯然它們兩兩互質（反

12、證法）既然如此，由於：根據中國剩餘定理，存在一個數使得：（，）即（，）現在，可以直接驗證，如果：由（）與（，）遞迴而成而可用（，）可用（，）表示則（，）可以用：),.(),(),()()()(),(),.(),0,()()()(11211zywxxHzwvuBywvuBzyxwwxxvuBwxxGwvuBwvunnnnn備註完整的可表達性定理所有由：1.零函數（）2.後繼函數（）3.射影函數（，）經由有限次：1.遞迴2.合成 f(x),g(x)f(g(x)3.最小數 f(x)=min“g(x)=0“4.所得到的函數必定是可表達的肆哥德爾數Gdel Numbers目標:將所有可以被寫出來的命題與

13、證明編號，並藉此提 供一個判別某證明是否為一個命題的一個證明 的方法為了寫出“這句話不可被證明”這樣一個句子，我們必須能夠掌握公理系統下所有的證明在此，我們引入哥德爾數這個方法，來為一個公理系統中的所有命題與證明編號一將符號編號運算符號（），個體變元（）個體常元（）函數符號（在此只有關係符號（在此只有）注意到這種表示法是一對一的二將命題編號假定一個命題中的符號的哥德爾數依序為，則我們定義這個命題的哥德爾數為：注意到這種表示法是一對一的ntntttP.532321 命題中的各符號之歌德爾數依序為：，因此這個命題的哥德爾數為：1721172715117532三將證明編號假定一個證明中的命題的哥德爾

14、數依序為，則我們定義這個證明的哥德爾數為：注意到這種表示法是一對一的ntntttP.532321注意，當我們說“命題序列是命題的一證明時，並不保證它是一個“正確的證明”，而只保證它的最後一項推得，並且證明序列中的各命題不會自相矛盾也就是說，的哥德爾數質因數分解後，最最後一項的指數是命題的哥德爾數後一項的指數是命題的哥德爾數四證明的判別所以，如果一個哥德爾數為的命題的一個證明，它的哥德爾數為，就表示最後一項的指數換言之：由可表達性定理的討論知，上句是可表達的)|()|()|max(1npnpnqqqpmm是質數伍證明Proof目標:實際構造“本命題不可被證明”考慮一個關係：（，）成立，當且僅當：

15、是系統中一個命題（）的哥德爾數且是系統中（）的一個證明的哥德爾數我們現在想知道它是否是可表達的對於（，）的後半部：是系統中（）的一個證明的哥德爾數由哥德爾數的討論，我們已知它是可表達的因此現在只需證明：是（）的哥德爾數其中的哥德爾數是可表達即可我們先考慮操作性的問題：要如何由（）得出（）的哥德爾數？注意到（）是由（）中挑出所有的，以代入，而的位置可以藉由中所有指數為的質數的位置指數為的質數的位置而唯一確定，因此操作上是沒有問題的（）：的哥德爾數為1721172715117532 則（）的哥德爾數為1721172715117532172117271175321175321721172715所以，

16、要從（）的哥德爾數，推出（）的哥德爾數，我們只要將質因數分解，然後，對於其中的每個質數：n若該質數的指數是，則把指數該做n若該質數的指數不是，則保留原指數我們把這樣的操作模式語句化，便會得到：是（）的哥德爾數，的哥德爾數是可用以下式子表達：)|()|()|()|()|()|()|()|()15)()(1161511kpkpmpmpkpkpmpmpssppmmssss是質數因此（，）是可表達的我們假定它的表達式為（，）現在考慮命題：必然有對應的哥德爾數再構造命題：),()(:212xxWxA),()(:22xpWxU我們來看代表什麼它顯然可以翻譯為：“對於每個自然數，（，）都不成立”又由於是的哥

17、德爾數，以及的定義，我們又可譯為：“當是某個公式（）的哥德爾數時，對於每個自然數，都不會是（）的一個證明的哥德爾數”但是，（）就是（）就是！),()(22xpWx所以：這個命題其實就是：),()(:22xpWxU“本命題不可被證明”後記不完備性定理告訴我們什麼？對於數學：一種全新的思路以往大多數的數學家（特別是希爾伯特）都認為，“真的東西，終究會被證明”“假的東西，終究會被否證“正如同希爾伯特的名言：Wir mssen wissen,wir werden wissen.年不完備性定理被提出後，數學家開思考慮另外的兩種情況：一個命題“不能被證明為真”一個命題“不能被證明為假”例如先前提過的連續統

18、假設，便被證明：在現行的集合論公設下，連續統假設不能被證明為真1936，亦不能被證明為假1963對於電腦：不存在萬靈丹如果一個掃毒軟體要排除某個病毒，那它顯然必須先“偵測”，或是“判別”某個程式是病毒但是不完備性定理告訴我們，不管你給掃毒軟體多少條判別規則，我總是能夠設計一種病毒，它不能被判別因此：“不存在可以應付所有病毒的掃毒軟體”相對的：“不存在可以應付所有掃毒軟體的病毒“參考書目n哥德爾不完全性定理 朱水林九章出版社n希爾伯特的23個數學問題Jeremy J.Gray胡守仁譯天下文化nIntroduction of MetamathematicsStephen Cole Kleenen邏輯學入門林照田 蔡承志雙葉書局