不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

哥德尔不完备性定理的原始陈述与现代陈述

已有 163 次阅读 2024-7-11 18:41 |个人分类:解读哥德尔不完全性定理|系统分类:科研笔记

当人们谈论哥德尔不完备性定理时,一般指哥德尔第一不完备性定理和哥德尔第二不完备性定理。

哥德尔1931年的论文("On Formally Undecidable Propositions of Principia Mathematica and Related Systems I »)由4组成:

在第1章,哥德尔概述基于对角线法构造说自己是不可证明的命题的主要思想;

第一不完备性定理出现在第2Proposition VI

第二不完备性定理出现在第4章的Proposition XI

一,第一不完备性定理

1原始陈述 [1]

Proposition VI: For every ω-consistent recursive class c of formulae there correspond recursive class-signs r, such that neither v Gen r nor Neg (v Gen r) belongs to Flg(c) (where v is the free variable of r).

VI对于每个 ω-consistent递归公式类 c,都存在对应的递归类符号 r,使得 v Gen r Neg (v Gen r) 都不属于 Flg(c)(其中 v r 的自由变量)。

 

2现代陈述 [1]

First Incompleteness Theorem: "Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e. there are statements of the language of F which can neither be proved nor disproved in F." (Raatikainen 2020)

第一不完备性定理:任何一致的形式系统F,在其中可以进行一定量的基本算术运算,都是不完备的;也就是说,F语言存在着既不能证明也不能证伪的语句。(Raatikainen 2020

二,第二不完备性定理

1原始陈述 [1]

Proposition XI: If c be a given recursive, consistent class of formulae, then the propositional formula which states that c is consistent is not c-provable; in particular, the consistency of P is unprovable in P, it being assumed that P is consistent (if not, of course, every statement is provable).

XI:如果 c 给定的递归一致公式类,则陈述 c 是一致的命题公式是不可证明的;特别地,在假设 P 是一致的情况下,P 的一致性在 P 中是无法证明的(如果不是,当然,每个陈述都是可证明的)。

2现代陈述 [2]

For each formal system F containing basic arithmetic, it is possible to canonically define a formula Cons(F) expressing the consistency of F

对于每个包含基本算术的形式系统 F,可以规范地定义一个公式 Cons(F) 来表 F 的一致性。

Gödel's second incompleteness theorem shows that, under general assumptions, this canonical consistency statement Cons(F) will not be provable in F.

哥德尔第二不完备定理表明,在一般假设下,这个规范一致性陈述 Cons(F) F 中是无法证明的。

参考文献:

1https://monoskop.org/images/9/93/Kurt_Gödel_On_Formally_Undecidable_Propositions_of_Principia_Mathematica_and_Related_Systems_1992.pdf

2https://en.wikipedia.org/wiki/Gödel%27s_incompleteness_theorems



https://blog.sciencenet.cn/blog-2322490-1441925.html

上一篇:图灵是站在哥德尔的肩膀上吗?- B. Jack Copeland & Zhao Fan
收藏 IP: 194.57.109.*| 热度|

2 郑永军 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (2 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-7-11 22:15

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部