談談哥德爾不完備定理

來源: chenm 2022-08-12 16:49:41 [] [博客] [舊帖] [給我悄悄話] 本文已被閱讀: 次 (19121 bytes)

首先,哥德爾需要用一組符號來表達一個強的算術係統。哥德爾用了12個常量,9個變量。因為符號少了,表達就必然複雜。比如說,常量中的數字隻有一個0,如何表達自然數?辦法是常量中還有一個表示“直接後繼”的符號s,意義一看就懂:s0表達0的直接後繼數1。以此類推,ss0為2, sss0為3,等等。可以想象,如果數字大到成千上萬,那該有多長。因此請不要考慮“可操作性”問題。數學證明隻考慮原則上是否可行。

其次,哥德爾需要一套方法來將一個算術係統中所有的公式編碼。請注意,不僅是總共21個常量和變量,而且要將所有由這些量組成的公式全部編碼。這裏,就表現出哥德爾的天才。

他為每個常量或變量指定一個數,稱為“哥德爾數”(Godel Number),12個常量的哥德爾數就是1-12,9個變量的哥德爾數分別是13,17,19以及它們的平方、立方。

然後就可以編碼了。他的編碼方法被稱為“哥德爾編碼(Godel Numbering)”。每個符號都有了哥德爾數,比如0的哥德爾數是6,=是5,那麽公式0=0是不是就編碼為656?不是,下麵要解釋為什麽這樣編碼不行。

哥德爾編碼是,用素數2,3,5,7,9,11……來表示符號的在公式中的順序,而用符號的哥德爾數作為其指數。因此,0=0,第一個位置上是0,0 的哥德爾數是6,因此在這個位置上的0就是2的6次方,根據同樣原則=是3的5次方,第二個0 是5的6次方,這個公式的哥德爾編碼就是它們的乘積: 2的6次方乘3的5次方乘5的6次方,這個數是243,000,000。這就是這條公式的哥德爾數。

這麽簡單的一條公式就得用這麽大的數字來編碼,那麽複雜的公式用上了13次方,17次方甚至19次方,不是大到一個編碼要寫上幾十頁紙?

沒有錯,是這樣。再提醒一下,不要考慮可操作性,沒有人真的去做這樣複雜的編碼,這隻是原則上可行的方法。

不難想象,隻要知道0的哥德爾數是6,= 是5,從243,000,000可以唯一恢複為64乘以243乘以15625,進一步恢複為2的6次方、3的5次方、5的6次方,最後恢複為0=0。顯然,單純以哥德爾數來代替哥德爾編碼,比如以656來編碼0=0,就不具有唯一可恢複性。

這樣,有了一套可以表征一個算術係統的符號、有了一種編碼方法,可以將那個係統每一個的公式都編碼成一個整數,而且這個整數可以唯一地恢複為原有的公式。哥德爾又定義了一係列規則。下麵是他的少部分定義,對下文必不可少:

(1) 定義1 : 替代(x, v, y)

其中v是一個變量。意思是用y替代公式x中的v。大家已經明白,這裏的x,v和y, 都是哥德爾數。當然,替代之後仍然得到一個哥德爾數。

所以下麵的替代(y, 17, y)表示 “ 用 y 來替代公式y 中的哥德爾數是17 的變量 ” ;替代(n, 17, n)表示 “ 用 n 來替代公式n 中的哥德爾數是17 的變量 ” 。替代(n, 17, n) 是一種有意思的替代,稱為 “自替代 ” 。

為什麽要用 替代(x, v, y) ?

因為在算術係統  , 證明的過程經常是替代過程 ,如

(a) ~(sa= 0)        公理

(b) ~(s1= 0)        將1替代(a) 式中的 a 

~ 是邏輯否定詞 ,s 是 “直接後繼”符號 ,a 是變量,是自然數(正整數)

  1. 和 (b) 構成一公式 組合 ,它由兩個哥德爾數 k, l 係列組成,記為 B (w) , w 是指k或 l 。 

替代(x, v, y)時,替代後公式x 不再包括v ,替代之後結果稱為封閉公式。

(2) 定義2: 證明(u, B)

意思是公式u是公式B的一個證明。再提醒一下,u和B也都是哥德爾數。

(3) 定義3: 可證(B):(存在一u) 證明(u, B)

意思是“存在一哥德爾數u,u是哥德爾數B的證明”。更簡單的陳述是“哥德爾數B可證。”

所謂證明(u, B) 就是在B的一係列公式中找出最後的公式,這裏是 B(l) 。

現有一對數 p(x, y) 是真的,如果 x 是公式 B 的變量的哥德爾數 和 y 是公式 B 的證明的哥德爾數。

考慮公式:

 

        對所有的 y  ~ p(x, y)

 

設上述公式的哥德爾數是 m , 考慮封閉公式:

 

       G = 對所有的 y  ~ p(m, y) , (此式是在上述公式中用 m 自替代 x 後得到)

 

上述公式表明 G 是一個真公式,因為它是由封閉公式得到。封閉公式的意思是 G 或~G 是一組公式邏輯推導的結果。

但是 G 又不是 m 的任何證明。

所以,G 是一個真公式,但它不能被證明。

 

本文是在吳道平先生CND原文上改寫而成,在此致謝。

 



更多我的博客文章>>>

加跟帖:

  • 標題:
  • 內容(可選項): [所見即所得|預覽模式] [HTML源代碼] [如何上傳圖片] [怎樣發視頻] [如何貼音樂]