哥德尔不完备性定理.ppt

,按一下以編輯母片標題樣式,*,按一下以編輯母片,第二層,第三層,第四層,第五層,哥德爾不完備性定理,G,del,s Incompleteness Theorems,序,希爾伯特的23個數學問題,The Hilbert Challenge,目標:不完備性定理的內容與歷史緣由,The Hilbert Challenge,連續統假設,算術公理之完備性,歐氏體積之定義,直線與最短距離,李群,物理之公理化,某些數的超越姓,黎曼猜想與哥德巴赫猜想,一般形式的互反律,丟番圖方程,任意二次形式,克羅內克的青春之夢,圖算法,不變量的有限性,舒伯特的計數演算,曲線的拓樸;邊界圈的個數,平方和的函數,多面體的全等,基本域與裝球問題,偏微分方程的正則性,變分法與邊界條件,黎曼,希,爾伯特問題,單值化定理,變分法中的新方法,就最初淺的意義而言，公理是指一些,“我們先,決接受為真”,的東西，用以作為我們討論一門,科學的起點,對於,物理學,而言，,“能量守恆”,是一條公理,對於,歐氏幾何,而言，,“平行線永不相交”,是,一條公理,何謂公理,由於公理可以說是一系列存而不證的假設，所,以我們希望公理是,越少越好,而若是有一條公理，它能夠由其他的公理所推,出來，那這條公理就是,多餘的,因此，公理之間應該是,互相獨立的,，也就是說，,你不能由其中若干條,推出另一條,出來,公理應該要是互相獨立的,作為一門科學的基礎，一套公理應該要容許我,們能夠對這門科學下的每條命題加以判別為真,或為假,因此，一個公理系統應該是,完備的,，應該能夠,對系統下的每條命題加以證明或否證也就是,說，不應該容許,不可判定命題,的出現，例如：,“本命題不可被證明,”,公理系統應該要是完備的,請注意以下兩者的差別：,“本命題是假的,”,是既不真也不假，,“沒有真假值”,的句子,“本命題不可被證明,”,是不能被,證明,為真也不能被,證明,為假,它可能還是有真假值,希爾伯特想知道說，我們的數學體系究竟是,不是完備的？是否在數學中，存在有不可判,定命題？,他認為數學體系是完備的，並嘗試去證明,他的想法是，幾何可以用座標體系一一對應,到數域上，而整個數域又以算術：整數和加,減乘除為基礎，因此，,只要證明算術系統是,完備的，就能證明整個數學體系是完備的,第二問題算術公理的完備性,證明,皮亞諾算術公理系統,是,完備的,，進,而證明整個數學系統是完備的,就算是完備的又如何？,在,自然數集合大小,與,實數集合大小,之間，,沒有其他的集合大小,如果是完備的，希爾伯特想要用它來證明像,是第一問題之類的東西,第一問題連續統假設,自然數和偶數是一樣多的,，,，,什麼是集合的大小？,當我們說兩個集合一樣大時，是指說兩,個集合的元素之間，存在一種,一一對應,正有理數和自然數是一樣多的,(0,1)實數和自然數是不一樣多的,0.,2,47126,0.1,7,3281,0.66,6,519,0.311,9,23,0.2188,2,6,0.39183,0.27692,如果第二問題成立，則當我們要證明在自然,數集合大小與實數集合大小之間，沒有其他,的集合大小時，只要先在公理中多,假設有第,三種大小的存在,，然後,推出一個不可判定命,題,便能證明,哥德爾第一不完備性定理,皮亞諾公理系統是不完備的,，也就是說，,在算術系統中，我們總是能夠找到一個不,可判定命題,證明思路,為了限制符號的數量，將,算術系統,轉換為,量化邏輯,的公理系統,討論在這樣的系統中，什麼樣的命題是,可以確實被寫出來的,（可表達性定理）,將所有可以被寫出來的命題與證明編號，並藉此提供一個,判別某證明是否為一個命題的一個證明,的方法,藉由2,3,實際寫出句子：,“本命題不可被證明”,藉此證明不完全性定理,介紹流程,淺介量化邏輯,將算術系統表成量化邏輯,介紹可表達性定理的數個特例,將系統下的所有證明編號並給出一個判別證明的方法,利用3,4 寫出,“這個命題不可被證明”,這一個句子，藉此證明哥德爾第一不完備性定理,壹,量化邏輯,Quantificational Logic,目標:淺介量化邏輯,名詞,命題：可以,判別真假,的句子,是非負整數,這句話是假的,定理：可以,被證明為真,的命題,公理：,先決被認定為真,的命題,是非負整數,非,且,或,蘊含,對於所有 ,存在,邏輯符號,真值表,命題：,命題的真假,簡化符號,等價於,等價於,等價於,等價於,所以我們事實上只需要三種符號：,量化邏輯下的論證,原論證：若是整數且不可被整除，則,是奇數,前提是整數,前提不可被整除,結論是奇數,因此原論證可表為：,量化邏輯下的證明,，,，,將數學證明轉為邏輯證明的例子,原證明引入定理一：,“若是整數，則是奇數或是偶數”,由前提一知“是奇數或是偶數”,再引入定理二：,“若是偶數，則可被整除”,由前提二知“不是偶數”,因此“是奇數”,若是整數且不可被整除，則是奇數,（是整數）,（不可被整除）,令是偶數,（）定理一,，,定理二,，,，,請注意，證明是一組“,無矛盾的命題序列,”,量化邏輯下的公理系,邏輯符號如，,語句符號如，,個體常元如，,個體變元如，,函數符號如（）,關係符號如（，）表,公理如（）（）,貳,算術系統與皮亞諾公理,EA and,Peano,Axioms,目標:將算術系統表成量化邏輯,皮亞諾的五條算術公理,是一個非負整數,每個非負整數，都有不同於的後繼元素,不存在非負整數，使得為,對於任意非負整數和，如果，那麼,對於任何含有的非負整數集合，如果對任意的屬於，都有屬於，那麼含有所有的非負整數,上述五條公理確立了非負整數集.,關係符號：,“”這個符號蘊含著兩個公理：,（,，,，,）,（,，,，,）,其中是任意函數或關係,以上兩條相等公理確立了的性質,是一個非負整數,個體常元,每個自然數，都有不同於的後繼,函數,不存在非負整數，使得為,公理：,將皮亞諾公設表成量化邏輯,對於任意非負整數和，如果，那麼,對於任何含有的非負整數集合，如果對任意,的屬於，都有屬於，那麼含有所有,的非負整數,函數符號：和,“”的性質由以下兩條性質確立：,“”的性質由以下兩條性質確立：,一階算術系統,運算符號（），,語句字母,個體常元,個體變元,函數符號,關係符號,公理相等公理二條,皮亞諾公理三條,加法公理二條,乘法公理二條,備註嚴謹的一階算術系統,運算符號（），,語句字母,個體常元,個體變元,函數符號,n(x)a(x,y)m(x,y),關係符號,e(x,y),公理相等公理二條,皮亞諾公理三條,加法公理二條,乘法公理二條,參,可表達性定理,目標:了解什麼樣的句子是可以被寫出來的,何謂可表達?,一個元關係（,，,）可表達,若且唯若有一個元命題（,，,）,使得,（,，,）成立,若且唯若,（,，,）為真,“,2,1,”可以用下列命題表示：,“,（）”可表為：,“,”這個關係可以表為：,“是質數”這個關係可以表為：,可表達性定理,可表達性定理保證：,若關係“,（,，,）”,與關係“,（,，,）”,都可表達，而,遞迴函數,滿足,（,，,，,）,（,，,）,（,，,，,）,（,，,，,，,（,，,，,）,）,則關係：,“,（,，,，,）”,可表達,函數（，）,可以用函數：,（）,（，）,表成遞迴：,（，）（）,（，）（，（，）,又關係“”及“”顯然都可,表達，故由可表達性定理知：,可表達,可表達性定理的簡略證明,引理一若（,，,）表示,除,的餘數,，,則“,（,，,）”可用：,引理二若：（,，,，,）,（,，（,）,）,則由引理一知可表達，記它的表達式為,（,，,，,，,）,引理三 對於任何一個序列,，,存在適合的，使得：（，）,證明：令,max（,，,，,）,！,考察數列,（），,顯然它們兩兩互質,（反證法）,既然如此，由於：,根據中國剩餘定理，存在一個數,使得：（，,）,即,（，）,現在，可以直接驗證，如果：,由（,）與（,，,，,）,遞迴而成而可用（,，,，,）,可用（,，,，,，,）表示,則（,，,，,）可以用：,備註完整的可表達性定理,所有由：,零函數（）,後繼函數（）,射影函數,（,，,）,經由有限次：,遞迴,合成,f(x),g(x)f(g(x),最小數,f(x)=min“g(x)=0“,所得到的函數必定是可表達的,肆,哥德爾數,G,del,Numbers,目標:將所有可以被寫出來的命題與證明編號，並藉此提,供一個判別某證明是否為一個命題的一個證明,的方法,為了寫出“這句話不可被證明”這樣一個句子，,我們必須能夠掌握公理系統下,所有的證明,在此，我們引入,哥德爾數,這個方法，來為一,個公理系統中的所有命題與證明編號,一將符號編號,運算符號（,）,，,個體變元,（,）,個體常元,（）,函數符號,（在此只有,關係符號,（在此只有）,注意到這種表示法是,一對一的,二將命題編號,假定一個命題中的符號的哥德爾數依序為,，,，,則我們定義這個命題的哥德爾數為：,注意到這種表示法是,一對一的,命題中的各符號之歌德爾數依序為：,，,因此這個命題的哥德爾數為：,三將證明編號,假定一個證明中的命題的哥德爾數依序為,，,，,則我們定義這個證明的哥德爾數為：,注意到這種表示法是,一對一的,注意，當我們說“命題序列是命題的一證,明時，並,不保證它是一個“正確的證明”,，而,只保證,它的最後一項推得,，並且,證明序列,中的各命題不會自相矛盾,也就是說，的哥德爾數質因數分解後，,最,後一項的指數是命題的哥德爾數,四證明的判別,所以，如果一個哥德爾數為的命題的一個,證明，它的哥德爾數為，就表示,最後一,項的指數,換言之：,由可表達性定理的討論知，上句是可表達的,伍,證明,Proof,目標:實際構造“本命題不可被證明”,考慮一個關係：,（，）,成立，當且僅當：,是系統中一個命題（,）的哥德爾數,且是系統中（）的一個證明的哥德爾數,我們現在想知道它是否是可表達的,對於（，）的後半部：,是系統中（）的一個證明的哥德爾數,由哥德爾數的討論，我們已知它是可表達的因,此現在只需證明：,是（）的哥德爾數,其中的哥德爾數是,可表達即可,我們先考慮操作性的問題：要如何由（,）,得出（）的哥德爾數？,注意到（）是由（,）中挑出所有的,，以代入，而,的位置可以藉由中所,有,指數為的質數的位置,而唯一確定，因此操,作上是沒有問題的,（,）：,的哥德爾數為,則（）,的哥德爾數為,所以，要從（,）的哥德爾數，推出,（）的哥德爾數，我們只要將質因數分解，,然後，對於其中的每個質數：,若該質數的指數是，則把指數該做,若該質數的指數不是，則保留原指數,我們把這樣的操作模式語句化，便會得到：,是（）的哥德爾數，的哥德爾數是,可用以下式子表達：,因此（，）是可表達的,我們假定它的表達式為,（，）,現在考慮命題：,必然有對應的哥德爾數,再構造命題：,我們來看代表什麼,它顯然可以翻譯為：,“對於每個自然數，（，）都不成立”,又由於是的哥德爾數，以及的定義，,我們又可譯為：,“當是某個公式（,）的哥德爾數時，對於,每個自然數，都不會是（）的一個證明,的哥德爾數”,但是，,（）就是,！,所以：,這個命題其實就是：,“本命題不可被證明”,後記,不完備性定理,告訴我們什麼？,對於數學：一種全新的思路,以往大多數的數學家（特別是希爾伯特）都認為，,“真的東西，終究會被證明”,“假的東西，終究會被否證“,正如同希爾伯特的名言：,Wir m,ssen wissen,wir werden wissen,.,年不完備性定理被提出後，數學家開思考,慮另外的兩種情況：,一個命題“不能被證明為真”,一個命題“不能被證明為假”,例如先前提過的連續統假設，便被證明：,在現行的集合論公設下，連續統假設不能被證明為,真,1936,，亦不能被證明為假,1963,對於電腦：不存在萬靈丹,如果一個掃毒軟體要排除某個病毒，那它顯然必須,先“偵測”，或是“判別”某個程式是病毒但是不完,備性定理告訴我們，不管你給掃毒軟體多少條判別,規則，我總是能夠設計一種病毒，它不能被判別,因此：,“不存在可以應付所有病毒的掃毒軟體”,相對的：,“不存在可以應付所有掃毒軟體的病毒“,參考書目,哥德爾不完全性定理,朱水林九章出版社,希爾伯特的23個數學問題,Jeremy J.Gray,胡守仁譯天下文化,Introduction of,Metamathematics,Stephen Cole,Kleene,邏輯學入門,林照田 蔡承志雙葉書局,