數理邏輯3 -- 形式數論16

哥德爾第一不完備定理要求理論K具有 ω− 一緻性，數學家Rosser把這個條件變弱了。他說，K不需要 ω− 一緻性，而是滿足兩個小小條件，一樣可以構造出如下一個不可判定句子：

H(x1):  (∀x2)(PF(x2,x1)⇒(∀x3)(NEG(x1,x3)⇒(∃x4)(x4≤x2∧PF(x4,x3))))

。其中 H(x1) 裡面的 NEG 是前面哥德爾那些遞歸關系和函數裡面的 y=Neg(x) （即若 x 是某個好式子B的哥德爾數，則 y 是¬B的哥德爾數）。是以 H(x1) 的“意思”就是：如果 x1 可證，且證明的哥德爾數為 x2 ，那麼存在一個比 x2 還小的整數，它能證明 x1 的否。是以它就會違反K的一緻性。

根據不動點定理，Rosser構造了以下不可判定句子，

⊢KR⇔H(┌R┌)

。這個 R 也是不可判定的，其證明稱為Rosser’s Trick。

命題3.38（Godel-Rosser Theorem）：假設K滿足哥德爾第一不完備定理中的條件1，2，3，并且額外滿足以下兩個條件，

4. ⊢Kx≤n¯⇒x=0∨x=1¯∨...∨x=n¯，對所有自然數 n 成立

5. ⊢Kx≤n¯∨n¯≥x，對所有自然數 n 成立

那麼，若K是一緻的，則Rosser句子R不可判定，即 ⊢KR 不成立， ⊢K¬R 也不成立。

證明：a. 假設有 ⊢KR ，記 R 的哥德爾數為p， ¬R 的哥德爾數為 q ，R的證明的哥德爾數為 m 。因為⊢KR，是以有 ⊢KH(┌R┐) ，是以應用兩次A4和MP，可得

(∇1)  ⊢K(∃x4)(x4≤m¯∧PF(x4,q¯))

。接下來，因為K是一緻的，是以 ⊢K¬R 不成立，是以對所有自然數 n ，Pf(n,q)都為假，是以 ⊢K¬PF(n¯,q¯) 對所有自然數 n 成立，再根據條件4可得⊢Kx4≤m⇒¬PF(x4,q¯)（應用 x4=n¯⇒¬PF(x4,q¯) ，因為K是含等式理論），是以 ⊢K¬(x4≤m¯∧PF(x4,q¯) （注意 A⇒B 和 ¬A∨B 等價），是以再應用Gen就有 (∀x4)¬(x4≤m¯∧PF(x4,q¯)) ，這就與 (∇1) 産生了沖突。是以， ⊢KR 不成立。

b. 假設有 ⊢K¬R ，記 ¬R 的哥德爾數為 q ，它的證明的哥德爾數為t，而 R 的哥德爾數為p，那麼

1. PF(x2,p¯) ，假設

2. NEG(p¯,x3) ，假設

3. PF(t¯,q¯) ，由 ⊢K¬R 得知

4. t¯≤x2⊢Kt¯≤x2∧PF(t¯,q¯) ，由3、顯然

5. ⊢Kt¯≤x2⇒(∃x4)(x4≤x2∧PF(x4,q¯)) ，由4，對 t¯ 應用規則E4，再用演繹定理

6. ⊢K¬PF(t¯,p¯) ，由K的一緻性得出

7. ⊢Kx2=t¯⇒¬PF(x2,p¯) ，由6和A7代入法則，K是含等式的理論

8. ⊢Kx2≤t¯⇒¬PF(x2,p¯) ，由7和條件4

9. t¯≤x2∨x2≤t¯ ，條件5

10. ¬PF(x2,p¯)∨(∃x4)(x4≤x2∧PF(x4,q¯)) ，由5、8、9和搗鼓幾次規則

11. (∃x4)(x4≤x2∧PF(x4,q¯)) ，由1、10和析取消除

12. PF(x2,p¯),NEG(p¯,x3)⊢K(∃x4)(x4≤x2∧PF(x4,q¯)) ，由1-11

13. ⊢KR ，由12、演繹定理+A4、再來一次演繹定理+A4，即可的得到 H(p¯) ，也即得到了

是以，上述步驟13和 ⊢K¬R 違反了K的一緻性。是以， ⊢K¬R 也不成立。證畢。

系統RR：一個有限公理集的形式數論

後面很多性質都和這個被稱為RR的系統有關，是以這裡不得不拿出來讨論。

RR系統也是基于算術語言 LA 的一階理論，它有以下14條适當公理（Proper Axiom）

1. x1=x1

2. x1=x2⇒x2=x1

3. x1=x2⇒(x2=x3⇒x1=x3)

4. x1=x2⇒x′1=x′2

5. x1=x2⇒(x1+x3=x2+x3∧x3+x1=x3+x2)

6. x1=x2⇒(x1⋅x3=x2⋅x3∧x3⋅x1=x3⋅x2)

7. x′1=x′2⇒x1=x2

8. 0≠x′1

9. x1≠0⇒(∃x2)(x1=x′2)

10. x1+0=x1

11. x1+x′2=(x1+x2)′

12. x1⋅0=0

13. x1⋅x′2=(x1⋅x2)+x1

14. (x2=x1⋅x3+x4∧x4<x1∧x2=x1⋅x5+x6∧x6<x1)⇒x4=x6 （餘數唯一性）

RR系統比S弱，它隻包含有限個适當公理。但它很性質都和S一樣，它也是不完備的。

引理3.32：以下好式子都是RR中的定理。

a. n¯+m¯=n+m¯¯¯¯¯¯¯¯¯ ，對任意 n,m 成立

b. n¯⋅m¯=n⋅m¯¯¯¯¯¯¯ ，對任意 n,m 成立

c. n¯≠m¯ ，對任意 n,m 且 n≠m

d. n¯<m¯ ，對任意 n,m 且 n<m

e. x≮0

f. x≤n¯⇒x=0∨x=1¯∨...∨x=n¯ ，對任意自然數 n 成立

g. x≤n¯∨n¯≤x，對任意自然數 n 成立

命題3.33：所有遞歸函數都在RR中可表達。

哥德爾第二不完備定理

哥德爾第二不完備定理通俗的解釋是，一個蘊涵PA的形式系統，它的一緻性無法在自己内部推導得出。這裡需要對“一緻性”形式化成某個好式子，然後再運用一緻性的性質，證明這個無法推導得出這個好式子。這個好式子是這樣的：K是算術語言LA的一階理論S的任意擴充（即S的所有定理都是K的定理），并且K包含遞歸公理集，那麼構造以下好式子

(CONK)：  (∀x1)(∀x2)(∀x3)(∀x4)¬(PF(x1,x3)∧PF(x2,x4)∧NEG(x3,x4))

CONK 的意思就是，不可能同時證明一個好式子和它的否定，也即K是一緻的。哥德爾證明了 ⊢KCONK⇒G ，其中G是第一不完備定理中的哥德爾句子。既然 G 不可證，是以⊢KCONK也不成立。

教材裡給了另外一種證明，結合了希爾伯特、Bernays、Lob三人的工作。

首先，我們記 BEW(x1) 為 (∃x2)PF(x2,x1) ，也即 x1 可證（BEW是德語中“證明”一詞的頭三個字母）。應用不動點定理，可知存在一個好式子G，滿足 ⊢SG⇔¬BEW(┌G┐) 。（注意， ¬BEW 也隻包含一個自由變量符号。在這裡，我們隻讨論理論S）。

然後，希爾伯特和Bernays給出了理論S中的三個“推導條件”，實際上是三條引理。為了讨論友善，我們記 □B 為 BEW(┌B┐) ，其中 B 是任一好式子。希爾伯特和Bernays的三個條件是：

(HB1)  ⊢SB⇒□B

(HB2)  ⊢S□(B⇒D)⇒(□B⇒□D)

(HB3)  ⊢S□B⇒□□B

這三個條件中前兩個都不難證，最後一個就複雜多了，教材裡也沒有直接給出，而是給了一些參考讀物。

接着，構造兩個句子：一個是哥德爾句子，滿足 ⊢SG⇔¬□G ；另一個稱為Henkin句子，滿足 ⊢SH⇔□H 。這個Henkin句子說的是，“我等價于我能被證明”。這個句子一眼看上去不知道對不對（在标準模型中是否為真），也不知道是否真的在S中可證，邏輯學家Lob解決了這個問題，進而證明了“S一緻性的不可證”。

命題3.40（Lob’s Theorem）： B 是S中的一個好式子，若⊢S□B⇒B，則 ⊢SB 。

證明：考慮好式子 BEW(x1)⇒B ，它隻有一個自由變量符号，是以對其應用不動點定理，存在一個好式子 L ，滿足⊢SL⇔(BEW(┌L┐)⇒B)，換種寫法就是 ⊢SL⇔(□L⇒B) 。

1. L⇔(□L⇒B) ，已證

2. L⇒(□L⇒B) ，由1

3. □(L⇒(□L⇒B)) ，由2和HB1

4. □L⇒□(□L⇒B) ，由3和HB2

5. □(□L⇒B)⇒□□L⇒□B ，HB2

6. □L⇒(□□L⇒B) ，由4、5和傳遞規則

7. □L⇒□□L ，HB3

8. □L⇒□B ，由6和搗鼓幾次規則（ A⇒(B⇒C),A⇒B⊢A⇒C ）

9. □B⇒B ，條件

10. □L⇒B ，由8、9和傳遞規則

11. L ，由1、10和MP

12. L⇒□L，HB1

13. B ，由11、12、10和MP

證畢。

推論3.41：H是S中的Henkin句子，即 ⊢SH⇔□H 。那麼，我們有 ⊢SH ，并且 H 在标準模型中為真。

證明：因為⊢SH⇔□H，是以 ⊢S□H⇒H ，根據命題3.40可知 ⊢SH 。是以， H 在S中可證，是以□H在标準模型中為真（即對任意 x ，都能滿足□H）。是以， H 在标準模型中也為真。

命題3.42（哥德爾第二不完備定理）：如果S是一緻的，則 ⊢SCONS 不成立。

證明：若 S 是一緻的，因為⊢S0≠1¯，是以 ⊢S0=1¯ 不成立。根據Lob引理， ⊢S□(0=1¯)⇒(0=1¯) 也不成立（否則 ⊢S0=1¯ 就成立了）。是以，根據 ¬A⇒(A⇒B) ，可知

(∇)  ⊢S¬□(0=1¯)也不成立

。

另一方面，因為 ⊢S0≠1¯ ，是以根據HB1可得 ⊢S□(0≠1¯) 。接着，不難證明 ⊢SCONS⇒¬(0≠1¯) （取 0=1¯ 和 0≠1¯ 的哥德爾數，然後應用A4規則代入 CONS 即可）。是以， ⊢SCONS 也不成立，否則會和 (∇) 一起違反一緻性。證畢。