数学联邦政治世界观
超小超大

勒布定理

假设算术公理系统 S ,称 P 是 S 的可证性谓词,当且仅当 P 满足以下三个条件:

1. 如果 S⊢ψ ,那么 S⊢P(⌈ψ⌉) ,其中 ⌈ψ⌉ 是 ψ 的哥德尔编码。下文中我们直接用 Pψ 表示 P(⌈ψ⌉) 。

2. S⊢P(ψ→φ)→(Pψ→Pϕ) 。

3. S⊢Pψ→PPψ

可以证明“存在 x 编码了公式 ϕ 的证明”是算术系统 PA 的一个可证性谓词。下文中我们直接令 PA=S ,令 P(x) 为“存在 x 编码了公式 ϕ 的证明”。

在哥德尔第一不完全性定理中,罗瑟(Rosser)定义了一个语句 G ,使得 PA⊬G 且 PA⊬¬G ,进而证明了 PA 不是完全的。这个语句 G 可以简单理解为“ G 不可证”,类似于说谎者悖论。那么如果一个语句陈述自己可以被证呢?即语句 ϕ 满足 ϕ↔Pϕ 。如果这样的语句存在,那么它会有什么样的性质呢?

勒布定理:如果 Pψ→ψ 是 PA 的定理,那么 ψ 是 PA 的定理。

证明: P(x)→ψ 是含有一个自由变元的公式,根据不动点引理,存在公式 φ 满足 φ↔(Pφ→ψ) 。根据条件 3 可得 Pφ→(PPφ→Pψ) ,根据条件 2 可得 Pφ→Pψ ;由于 Pψ→ψ 是 PA 的定理,因此 Pφ→ψ 是 PA 定理,进一步得 φ 是 PA 定理,根据条件 1 可得 Pφ 是 PA 定理,则 ψ 是 PA 定理。因此勒布定理成立。 ⊣

由勒布定理可以轻松推出第二不完全性定理(Kreisel):如果 PA 一致,令 ⊥ 为矛盾式 0=1 ,那么 ⊢P⊥→⊥ 蕴含 ⊢⊥ ,即 ⊢¬P⊥ 蕴含 ⊢⊥ ,由于假设 PA 一致,因此 ⊬⊥ ,则有 ⊬¬P⊥ ,而 ¬P⊥ 就是“ PA 是一致的”,第二不完全性定理成立。 ⊣

数学联邦政治世界观提示您:看后求收藏(同人小说网http://tongren.me),接着再看更方便。

相关小说

我在修仙游戏里磕cp 连载中
我在修仙游戏里磕cp
锦鲤_43827340896276126
自娱自乐
0.1万字6个月前
边缘角色 连载中
边缘角色
River_L
如果能为自己定价你会为自己定价多少呢?或许你会觉得这个问题很侮辱人,但在云城里面这个问题也说明了你的价值。没有人可以让顶层的那个人亲自去问他......
1.5万字6个月前
快穿之反派boss的白月光 连载中
快穿之反派boss的白月光
云中月皎皎
第一个世界(完):把温柔哥哥撩到手了第二个世界(完):那个将军在替我守墓第三个世界(完):在末世我抱紧了大腿第四个世界(完):我是被偷换的真......
28.9万字6个月前
烟雨潇潇,十世情长 连载中
烟雨潇潇,十世情长
叶瑾笙🍃
你相信缘分吗?你愿意追随一个人十世吗?陪他看尽人间繁华,同他一直到天荒地老……一生知己难求,一世安宁难得。生死轮回不息,鬼门关中徘徊。孟婆赐......
14.9万字6个月前
幻劫三生,错步诛心 连载中
幻劫三生,错步诛心
依梦橙
一个是九重天尊主北烊,一块没有烟缘的火石。  一个是八玄天的未来的战主,一只四海八荒修练者羡慕不来的九尾猫妖。  但是……
8.9万字6个月前
封梦难寻 连载中
封梦难寻
骨希蝶子
生活在一个利益至上又危险的世界,因为每天一直会做一个相同的梦,于是决定去找梦,最后弃梦……
5.8万字6个月前