数理逻辑3 -- 形式数论4

歌德尔不完备定理是命题3.37,还有很长的路要走,慢慢来吧。

命题3.6: m,n是任意自然数,
a. 如果 mn , 则 m¯n¯
b. m+n¯¯¯¯¯¯¯¯¯=m¯+n¯
c. mn¯¯¯¯¯¯¯¯=m¯n¯

证明:
a. 因为 mn ,所以不妨假设 m<n
采用反证法规则,假设 m¯=n¯
1. m¯=n¯
2. 0′′...=0′′′... ,这是1的缩写,左右两边分别有m和n个‘符号
3. 0=0′′... ,对2应用m次S5,右边‘符号个数为n-m
4. 0=t , 因为 nm10 ,所以可以找到一个符号 t ,使得 0=t
5. 0t , 由S3
6. 0=t0t ,由2、5和合取规则
7. m¯=n¯0=t0t ,由1-6
8. m¯n¯ ,由7和反证法规则
证毕

b. 注: m+n¯¯¯¯¯¯¯¯¯ 中的 + 符号是自然数的加法,而 m¯+n¯ + 符号是 LA 语言中定义的函数符号。
我们采用对自然数 n 的归纳法证明(而不是用S9的“归纳法”)。
首先,若 n=0 ,即要证 m+0¯¯¯¯¯¯¯¯¯=m¯+0¯ 。 注意到, m+0¯¯¯¯¯¯¯¯¯ 就是 m¯ ,也即 0 上加了m次‘符号。 0¯ 就是 0 ,即 0 上加0次’符号。 由S5可知, m¯=m¯+0 ,所以 n=0 时成立。

然后,假设命题对 n 成立,
1. m+n¯¯¯¯¯¯¯¯¯=m¯+n¯ ,归纳假设
2. (m+n¯¯¯¯¯¯¯¯¯)=(m¯+n¯) ,由1和S2
3. m+n+1¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=(m¯+n¯) ,左边是2的另一种写法
4. (m¯+n¯)=m¯+(n¯) ,由S6
5. (m¯+n¯)=m¯+n+1¯ ,右边是4的另一种写法
6. m+n+1¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=m¯+n+1¯ ,由3、6和传递规则
所以,命题对 n+1 成立,证毕。

c. 和b一样,用针对自然数 n 的归纳法。
首先,若 n=0 ,则 m0¯¯¯¯¯¯¯ 就是 0¯ ,也就是 0 。另一方面, m¯0¯=m¯0 。由S7,可得 m¯0=0 。所以,由传递规则可得 m0¯¯¯¯¯¯¯=m¯0¯

然后,假设命题对 n 成立,
1. mn¯¯¯¯¯¯¯¯=m¯n¯ ,归纳假设
2. m(n+1)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=mn¯¯¯¯¯¯¯¯+m¯ ,因为 m(n+1)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ 就是 mn+m¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ,再根据命题3.6b即可。
3. m¯(n¯)=m¯n¯+m¯ ,由S8
4. m(n+1)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=m¯(n¯) ,由2、3、命题3.2b和传递规则
5. m(n+1)¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=m¯n+1¯¯¯¯¯¯¯¯ ,右边就是4的右边的另一种写法。
所以命题对 n+1 成立,证毕。

我们继续考察 S 理论的性质。我们可以用 S 中的语言来定义“不等关系”,如下:
定义:
a. t<s , 表示 (w)(w0w+t=s) ,即前者是后者的缩写。
b. ts , 表示 t<st=s
c. t>s ,表示 s<t
d. ts ,表示 st
e. ts ,表示 ¬(t<s)

命题3.7:对于任意项 t,r,s ,以下都是定理。
a. tt
b. t<s(s<rt<r)
c. t<sst
d. t<st+r<s+r
e. tt
f. ts(srtr)
g. tst+rs+r
h. hs(s<rt<r)
i. 0t
j. 0<t
k. t<rtr
l. trt<r
m. t<t
n. 0<1¯,1¯<2¯,2¯<3¯,...
o. tr(t<rr<t)
p. t=rt<rr<t
q. trrt
r. t+rt
s. r0t+r>t
t. r0trt
u. r0r>0
v. r>0(t>0rt>0)
w. r0(t>1tr>r)
x. r0(t<str<sr)
y. r0(tstrsr)
z. t0
z’. trrtt=r

证明:
a. 用反证法规则
1. t<t ,假设
2. (w)(w0w+t=t) ,这是1的另一种写法
3. b0b+t=t ,由2和规则C
4. b0,b+t=t ,由3、合取消除规则
5. t=0+t ,命题3.2f
6. b+t=0+t ,由4、5和传递规则
7. b=0 ,由6、命题3.4d(减法律)
8. b0b=0 ,由4、7和合取引入规则
9. t<tb0b=0 ,由1-8
10. ¬(t<t) ,由9和反证法规则
证毕

b. 不等关系的传递性。注:这些证明反复运用规则C、E4和演绎定理。由于E4的证明无需Gen规则,所以演绎定理放心使用。
1. t<s,s<r ,假设
2. (w)(w0w+t=s) ,对1的展开表示
3. (v)(v0v+s=r) ,对1的展开表示
4. b0b+t=s , 由2和规则C
5. c0c+s=r ,由3和规则C
6. b0,b+t=s ,由4和合取消除
7. c+(b+t)=c+s ,由6、命题3.2i
8. c0,c+s=r ,由5和合取消除
9. c+(b+t)=r ,由6、8和传递规则
10. (c+b)+t=r ,由9和命题3.2j
11. c+b0 , 由6、命题3.5d、合取消除、逆否规则
12. c+b0(c+b)+t=r ,由10、11和合取引入
13. (u)(u0u+t=r) ,由12和规则E4
14. t<r ,这是13的缩写
15. t<s,s<rt<r ,由1-14
再根据演绎定理即可,证毕

c. 看起来像废话,但还是要证一番,这次写得简短一些了。
1. t<s,s<t ,假设
2. b0,b+t=s ,由1、规则C、合取消除
3. c0,c+s=t ,由1、规则C、合取消除
4. c+(b+t)=c+s ,由2、命题3.2i
5. c+b+t=0+t ,同b的证明步骤
6. c+b=0 ,由5和减法律
7. c+b0 ,由2,和b一样的方法
8. t<s,s<tc+b=0c+b0 ,由6、7、合取引入
9. t<s¬(s<t) ,由8和反证法规则
10. t<s(st) ,由9和演绎定理
证毕

d. 先证从左到右
1. t<s ,假设
2. b0,b+t=s ,由1、规则C、合取消除
3. b+t+r=s+r ,由2和命题3.2e
4. b+(t+r)=s+r ,由3、命题3.2j(加法结合律)
5. b0b+(t+r)=s+r ,由2、4和合取引入
6. (w)(w0w+(t+r)=s+r) ,由5、规则E4
7. t<st+r<s+r ,由1-6
所以, t<st+r<s+r

再证从右到左
1. t+r<s+r ,假设
2. b0,b+(t+r)=s+r ,由1、规则C、合取消除
3. b+t=s ,由2、命题3.2j,命题3.2b、命题3.4d(减法律)
4. (w)(w0w+t=s) ,由3、规则E4
5. t+r<s+rt<s ,由1-5
证毕

e. 用 t=t 和析取引入规则即可,证毕

f. 这里要用第一章的一个定理1.21,即 (BD)((¬BD)D)
1. t<st=s ,假设,即 ts
2. s<rs=r ,假设,即 sr
3. ts ,假设
4. sr ,假设
5. t<s ,由1、3和析取消除规则
6. s<r ,由2、4和析取消除规则
7. t<r ,由5、6和命题3.7b(上面那个b)
8. ts,sr,ts,srt<r ,由1-7
9. ts,sr,tssrt<r ,由8和演绎定理
10. s=r ,假设
11. t<r ,由5、10和A7(代入规则)
12. ts,sr,ts,s=rt<r ,由1、2、3、5、11
13. ts,sr,tss=rt<r ,由12和演绎定理
14. ts,sr,tst<r ,由9、12和定理1.21
15. ts,sr,tstr ,由14、析取引入
16. t=s ,假设
17. s=r ,假设
18. ts,sr,t=s,s=rtr ,由1、2、16、17和析取引入
19. sr ,假设
20. s<r ,由2、19和析取消除
21. ts,sr,t=s,srtr ,由1、2、16、20、A7替代规则和析取引入
22. ts,sr,t=str ,由18、21、演绎定理和定理1.21
23. ts,srtr ,由15、23、演绎定理和定理1.21
最后应用演绎定理即可,证毕

g. 采用和e一样的技巧,应用定理1.21
首先,从左往右
1. t<st=s ,假设,即 ts
2. ts ,假设
3. t<s ,由1、2和析取消除
4. t+r<s+r ,由3和命题3.7d
5. t+rs+r ,由4和析取引入
6. ts,tst+rs+r ,由1-5
7. t=s ,假设
8. t+r=s+r ,命题3.2e
9. ts,t=st+rs+r ,由1、8和析取引入
10. tst+rs+r ,由6、8、演绎定理和定理1.21

然后,从右往左
1. t+r<s+rt+r=s+r ,假设
2. t+rs+r ,假设
3. t+r<s+r ,由1、2和析取消除
4. t<s ,由3和命题3.7d
5. t+rs+r,t+rs+rts ,由1-4、析取引入
6. t+r=s+r ,假设
7. t=s ,命题3.4d减法律
8. t+rs+r,t+r=s+rts ,由7和析取引入
9. t+rs+rts ,由5、8、演绎定理和定理1.21
证毕

h. 写简单点了。
1. ts,s<r,t=st<r ,由A7代入规则
2. ts,s<r,tst<r ,由析取消除得 t<s ,再根据命题3.7b即可
3. ts,s<rt<r ,由1、2、演绎定理和定理1.21
证毕

i. 用归纳法,记 B(x) 0x .
首先,根据命题3.7e,可得 00
然后,假设 B(x) 成立,只需证 x<x 即可。
1. 0x ,归纳假设
2. 00 ,由S3、再利用反证法规则
3. 0+x=x ,由命题3.2f、g
4. 000+x=x ,由2、3和合取引入
5. x<x ,由4和规则E4
6. 0<x ,由1、5和命题3.7h
7. 0x ,由6和析取引入
所以 B(x) 成立,证毕

j. 上面i中已经证了 x<x ,所以 t<t ,再利用 0t 和命题3.7h,可得 0<t

k. 水平不够,证明繁琐。
先从左往右,即证 t<rtr 。这里关键要引用命题3.5h,即 t0(y)(t=y)
1. t<r ,假设
2. b0,b+t=r ,由1、规则C和合取消除
3. (w)(b=w) ,由2和命题3.5h
4. b=c ,由3和规则C
5. c+t=r ,由2、4和A7代入规则
6. c+t=r ,由5、命题3.2b、g和S6
7. t<r,c=0tr ,由1、6( t=r ),析取引入
8. c0 ,假设
9. c0c+t=r ,由6、8和合取引入
10. t<r ,由9和规则E4
11. t<r,c0tr ,由8、10和析取引入
12. t<rtr ,由7、11和命题1.21

从右往左很简单,i中已证 t<t ,所以
1. t<t ,已证之定理
2. tr ,假设
3. t<rt=r ,这是2的展开写法
4. t=r ,假设
5. t<r ,由1、4
6. tr,t=rt<r ,由2、4、5
7. tr ,假设
8. t<r ,由3、7和析取消除
9. t<r ,由1、8和命题3.5b
10. tr,trt<r ,由2、7、9
11. trt<r ,由6、10和命题1.21
证毕

l. 这个简单多了。
从左往右,利用 tr(r<rt<r) (命题3.7h)即可。

从右往左,即要证 t<rtr ,采用和k同样的技巧,利用命题3.5h
1. t<r ,假设
2. b0,b+t=r ,由1、规则C、合取消除
3. c=b ,由2、命题3.5h、规则C
4. c+t=r ,由2、3、A7代入规则
5. c+t+0=r+0 ,由4、命题3.2,S1-S9
6. c+t=r
7. t<r,c=0tr ,由1、6、析取引入( t=rtr )
8. c0 ,假设
9. c0c+t=r ,由6、8和合取引入
10. t<r ,由9和规则E4
11. t<r,c0tr ,由1、8、10和析取引入( t<rtr )
12. t<rtr ,由7、11和命题1.21
证毕

m. 这个在i中已证。

n. 利用m,即 0<0 , 0<0′′ ,…,即可

太多了,下节继续

相关文章
相关标签/搜索