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

博文

关于“哥德尔的不完全性定理”的讨论(12)

已有 1627 次阅读 2022-6-6 04:48 |个人分类:解读哥德尔不完全性定理|系统分类:观点评述

关于哥德尔的不完全性定理的讨论 - 2022/5/7 - 5/9


BasicRabbit:


你为什么不回答我的问题(我是第二次或第三次问你和PJ)?问题是:在你面前的哥德尔的不完备性定理的原始陈述中,是否谈到关于PA1ZF—语法一致性(内部连贯性)、语义一致性(外部一致性即存在一个模型--在哪里?)或一致性而没有说明?

对我来说,如果这是一个语法一致性的问题,那么也许存在一个本质上的差距:我相信这就是PJ所捍卫的观点,当他强调语言必须有两个层面,一个相对于另一个。

PS:虽然我对算术一点都不感兴趣,但我知道有很多 Polya猜想或Collatz的算术猜想。我认为,在这里在这个博客上--我们应该集中讨论哥德尔不完全性定理,以及能够引起认识论者兴趣的东西。我发现你把一些东西混在一起了。

Yu LI:


你能用一个例子来解释:什么是语法一致性(内部一致性),语义一致性(外部一致性)?

BasicRabbit:


如果从理论的公理和演绎规则中不能证明有任何矛盾,那么这个理论就是语法上一致的。如果理论有一个模型,那么它是在语义上一致的。


Yu LI:


哥德尔论文第二章的命题六,就是哥德尔不完备性定理的表述。


我在这里只是根据我目前的理解,对哥德尔的神奇证明做一个简单的描述。首先,哥德尔定义了数学语句:


Q(x,y)  ¬{x Bc[Sb(y 19⁄Z(y))]} 


Q(x, y)表示:'不存在x证明y(y)'


然后,通过基于哥德尔编码和哥德尔建立的递归函数属性的替换技术,哥德尔将“x不能证明y(y)”转换为“Q证明Q(Q)不可证明”


最后,根据ω一致性的定义,哥德尔表明,Q是一个不可判定的命题Q¬Q都是不可证明的。因此,哥德尔将说谎者悖论变成了定理


我引用第二章的命题六和哥德尔的解释:

– We proceed now to the rigorous development of the proof sketched above, and begin by giving an exact description of the formal system P for which we seek to demonstrate the existence of undecidable propositions. P is essentially the system obtained by superimposing on the Peano axioms the logic of PM (numbers as individuals, relation of successor as undefined basic concept).


1. Proposition VI (【1】p.57)


The general result as to the existence of undecidable propositions reads:

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).

2. 哥德尔的解释 (【1】p.62)

In the proof of Proposition VI the only properties of the system P employed were the following:

1. The class of axioms and the rules of inference (i.e. the relation “immediate consequence of”) are recursively definable (as soon as the basic symbols are replaced in any fashion by natural numbers).
2.Every recursive relation is definable in the system P (in the sense of Proposition V).

Hence in every formal system that satisfies assumptions 1 and 2 and is ω-consistent, undecidable propositions exist of the form xF(x), where F is a recursively defined property of natural numbers, and so too in every extension of such a system made by adding a recursively definable ω-consistent class of axioms. As can be easily confirmed, the systems that satisfy assumptions 1 and 2 include the Zermelo-Fraenkel and the v. Neumann axiom systems of set theory, and also the axiom system of number theory which consists of the Peano axioms, the operation of recursive definition [according to schema (2)] and the logical rules. Assumption 1 is in general satisfied by every system whose rules of inference are the usual ones and whose axioms (like those of P) are derived by substitution from a finite number of schemata.

你关于一致性的问题是非常重要的! 哥德尔在他的证明中使用了“ω一致性,这是其证明的关键之一。

在命题6的证明中,哥德尔对ω一致性的解释如下。

- Let c be any class of formulae. We denote by Flg(c) (set of – consequences of c) the smallest set of formulas which contains all the formulae of c and all axioms, and which is closed with respect to the relation “immediate consequence of”. c is termed ω-consistent, if there is no class-sign a such that:

(n)[Sb(a v⁄Z(n)) Flg(c)] & [Neg(v Gen a)] Flg(c)

where v is the free variable of the class-sign a.

Every ω-consistent system is naturally also consistent. The converse, however, is not the case, as will be shown later.

参考文献:【1】https://monoskop.org/images/9/93/Kurt_G%C3%B6del_On_Formally_Undecidable_Propositions_of_Principia_Mathematica_and_Related_Systems_1992.pdf




https://m.sciencenet.cn/blog-2322490-1341710.html

上一篇:漫谈汉字 - “危机”
下一篇:关于“哥德尔的不完全性定理”的讨论(13)

2 刘钢 杨正瓴

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

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

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

GMT+8, 2024-3-28 16:45

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部