個人資料
LinMu (熱門博主)
  • 博客訪問:
歸檔
正文

哥德爾 G?del 不完備定理

(2022-01-18 14:15:03) 下一個

什麽是公理體係?讀過高中的人,應該都知道公理體係。公理是無需證明而被認定為成立的命題。公理體係是指一組公理的集合。通過這些公理和基本的邏輯關係,可以推導出更多成立的命題,稱為定理。最常見的,莫過於在歐幾裏德五條公理的基礎上構建的整個歐式幾何公理係統。從這五條公理出發,可以推出歐式幾何的所有定理。

什麽樣的公理係統具有一致性?永遠不允許“矛盾”出現的係統就是一致的。矛盾就是,比如在某算術係統中,如果不同時允許1 > 2 和 1<=2,就說明該算術係統是“一致”的。

為什麽需要一致性,或無矛盾的公理體係?設想一個公理體係,一會兒說“1+1=2”,一會兒又說“1+1不等2”,就不會有人把這個公理體係當回事。有矛盾的公理體係是無意義的。

什麽樣的公理係統具有完備性?如果一個係統中所有可以表達的命題,他們的真值都能被決定,要麽真,要麽假,那麽我們就說這個係統是完備的。這裏的完備,指的是“對於任何可在這個公理體係內描述的命題,都可以在這個公理體係內得到判定,要麽是正確的,要麽是錯誤的”。比如,在算術係統中,命題1>2 是假的,命題3>2是真的,命題1>3是假的。如果這樣使用二階邏輯,所有數字,和其比較符號構成的命題都能被決定真假,那麽算術係統就是完備的。

在現代科學形成的過程中,通過定義一組公理再加上合理的邏輯推演,可以證明很多命題或結論。公理體係是當今數學研究和科學研究的基礎,數學研究成果就是依賴於一組公理體係的推演,而其它科學研究除了依賴公理體係進行推演外,還需要通過係統的實驗來進行驗證。

以前數學家一直認為一個公理體係既是一致的,也是完備的。

哥德爾年僅25歲時發表的“哥德爾不完備定理”是針對公理體係的一項結論,它撼動了公理體係。這個定理說的是:一個足夠複雜的公理體係,如果它是一致的,那麽它就是不完備的。也就是說不可能同時具有“一致性”和“完備性”的公理係統。

通俗點說,一個沒有矛盾的公理體係內,存在一些說不清楚對錯的命題(這是指在這個體係內說不清楚,不是說永遠都說不清楚)或者說命題是不可判定的。

什麽命題具有如此神奇的性質呢?說白了就是悖論。我們可以輕易用自然語言構造出一個悖論,比如:“我說的話是假的。”如果這句話為真,那麽它的內容又說它是假,互相矛盾。如果這句話為假,那麽它的內容說明它不是假的,又互相矛盾。因此這句話既不真又不假,它是個悖論。這個著名的說謊者悖論其實已經觸碰到了哥德尓不完備定理。

哥德爾定理的言外之意,有些命題是真的,但無法證明。這些無法證明的真的命題,可以作為公理。於是我們永遠需要憑借直覺尋找新的公理。

隻要一個係統表達力強到可以自指,那麽就不可能是完備的,這對後來的人工智能領域產生了深遠影響。

在計算理論裏,哥德爾的發現啟發了圖靈證明停機問題:如果有一個程序P,P輸入一個會終止的程序代碼就無限循環,輸入一個會無限循環的程序代碼就終止;那麽把P的代碼輸入給P,會發生什麽?停機問題在圖靈機上是不可判定問題。這是智能領域最早提出的決定性問題之一。

 

[ 打印 ]
閱讀 ()評論 (2)
評論
LinMu 回複 悄悄話 回複 'dhyang_wxc' 的評論 : 謝謝讀評,問好!
dhyang_wxc 回複 悄悄話 「道可道,非常道」,可道是一致的,就一定是「用天下為不足」,不完備的。
登錄後才可評論.