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

勒布定理

假设算术公理系统 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://www.bjxsw.cc),接着再看更方便。

相关小说

喜美:我在恐怖游戏里当主角 连载中
喜美:我在恐怖游戏里当主角
雾小渺wu
「喜美同人文01」——推推隔壁《喜美:童话镇》/本书开写于2024.9.4【不定时更新】-宋喜星×简喻美【双强】[双强+HE+爽文+幻想]-......
2.2万字4个月前
千秋引岚霜录 连载中
千秋引岚霜录
梦茳行
我的信仰因你而生,所以在我的世界当中,你则是我的神明。————————我不在乎你在别人眼中是谁,我只在乎你是我一人的阿岚,唯一的阿岚
0.6万字3个月前
普朗克尺度 连载中
普朗克尺度
Muriel昭
次要:【双男主】【救赎文】人鱼*机器人卓奈*万西(角色复杂,就这样概括着吧)主要:【未来科幻】【群众*战争】越往后越迷惑,作者属于是已经“疯......
2.5万字3周前
异者…… 连载中
异者……
凌琳灬
在这宇宙中有七位神明,分别是水神,草神,掌管地狱的神明,掌管赤焰的神明,掌管公正的神明,还有那诡计之神,数据的神明。在这宇宙还没创造之前,却......
0.7万字2周前
他呀!万人迷而不自知 连载中
他呀!万人迷而不自知
小鹿叮咚
(原创该书已签约)快穿局萌新言之害怕极了,为什么每个世界的主角都不按套路出牌啊!呜呜呜...
1.3万字2周前
致命的爱啊 连载中
致命的爱啊
whatisyourdream
爱情真的好复杂,不管是兄弟之间的爱情,还是恋人之间的爱情,都是爱情,但他们始终是有区别的,我不可能和弟弟在一起,我爱的人是阿铠,而弟弟应该去......
3.1万字2周前