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

博文

哥德尔给策梅洛的回信

已有 2286 次阅读 2022-5-5 17:05 |个人分类:解读哥德尔不完全性定理|系统分类:海外观察

19319月,策梅洛写给哥德尔的信中批评哥德尔的证明有误,哥德尔遂给策梅洛的回信。在Grattan-Guinness的这篇文章中有哥德尔的回信原文,因德文我无法翻译成中文,但通过Grattan-Guinness的转述,我们对哥德尔回信的内容可以略知一二。

格拉坦-吉尼斯(Ivor Grattan-Guinness1941-2014)是英国数学和逻辑学的历史学家。


一,纪念库尔特-哥德尔:他在1931年与策梅洛关于其不完全性定理的通信 - I. GRATTAN-GUINNESS


1931年哥德尔发表了现在著名的不完全性定理后不久,哥德尔和策梅洛就哥德尔的结果的性质和意义进行了通信。在介绍现存信件的文本之前,先解释了通信的情况,并说明了所讨论的要点的历史意义。


简介 

库尔特-哥德尔(Kurt Gcdel19067-1978)在他的一生中成为一个传奇,主要是因为他的定理证明了一个命题的存在,这个命题可以用形式系统的语言来表达,但它和它的否定一样,无法从系统的公理和推理规则中得到证明。这一结果对两种流行的数学哲学(希尔伯特的元数学和罗素的逻辑主义)产生了重大影响,并从那时起影响了逻辑学的许多分支。

哥德尔在1930年证明了他的结果,该年年底发表了摘要[哥德尔1930b],全文[哥德尔1931]1931年初出现。同年915日,他在Bad Elster举行的Deutsche Mathematiker-Vereinigung秋季会议上就其定理发表了演讲,策梅洛也在同一次会议上发言,后来他写了一份关于他和哥德尔的演讲的报告[策梅洛1932a],与哥德尔的通信大概是与这份报告有关的。 

策梅洛应该是在1931921日写给Godel的,因为哥德尔在1012日从维也纳发出的10页回信的开头就承认收到了这封信。策梅洛的信肯定丢失了(注:后来找到了),因为哥德尔在上次战争中丢失了许多他的维也纳文件[van Heijenoort 1967, 619]。但策梅洛1029日从弗莱堡-布赖斯高(Freiburg im Breisgau)寄来的答复的两份碳素副本与哥德尔的信一起保存在该市大学图书馆的策梅洛的档案里。

这两个人之间的主要争论点涉及到他们的证明概念之间的冲突,以及不可判定的命题存在的可能性。在策梅洛1930年的论文中,已经开始在他的公理集合理论中使用规则性公理,该公理的目的是通过防止集合成员的无限后退来保护集合,策梅洛在[1932a]中也用此将集合分层为相互不相干的集合”[Schichten]Qa)。简而言之,这个想法是:Qo是公理系统的原始元素层,而每一层Qa是由不属于前面任何一层的那些集合组成的。该定义通过转折归纳法进行:索引a0开始,贯穿于一系列秩序良好的序数。对于极限序数,该定义需要特殊处理,其细节在此不需要关注。

以类似的方式,策梅洛认为数学理论的基础是由元素的原始范围和它们之间的基础关系组成。然后,命题是通过对这些关系的量化(指逻辑上的结合和分离)和否定来进一步建立的关系。在这个基础上,如果S的每个子集合T至少包含一个不是S的任何成员的结果的命题,那么就结果的概念而言,一个命题集合就是基础良好的。

他表明,S可以被分层为量化层,每一层都有一个序数作为索引。然后他认为(相当含糊!),如果基础关系被任意划分为,那么这种划分就会延续到每一层的命题中,而且如果基础关系是一致的(他肯定是指那些被设计为真的关系,尽管它们的指定不能是任意的),那么衍生关系也是一致的。对他来说,任何真实的命题在属于某个量化水平的意义上也是可证明的。但这种情况自然会被哥德尔定理所抵触。

在对策梅洛921日遗失的信件的回应中,哥德尔仔细解释了他的证明的工作原理。他首先确认他的论文[1931]的第一部分并不是他的定理的约束性证明,而是对证明的正确性的指导,然后根据46个定义在论文中进行了非常详细的说明。然后他提到了他的证明方法和康托尔的对角线论证之间的相似性(他在论文的这个开头部分也是如此):这是以后会出现的一个特点。但首先在第2和第3页,他讨论了策梅洛提出的一类公式,希望在哥德尔的系统中产生一个类似说谎者悖论的悖论。哥德尔在第3-7页详细说明,与他自己的可证明公式类不同,策梅洛的真公式类不能以纯组合的方式在他的系统语言中表达,所以不会产生这种悖论。

在这几页中,哥德尔还强调了论证的元数学特征,就是谈论公式名字等。尽管在20世纪20年代,随着希尔伯特对其证明理论的复兴,人们对理论和元理论之间的区别给予了关注,但逻辑学家仍然倾向于混淆符号和指称;事实上, J. Barkley Rosser 教授曾在回忆中告诉我,只有在哥德尔定理的帮助下,逻辑学家才意识到他们在这个问题上需要多么小心谨慎。

哥德尔接着说(第7-8页),可证明的公式类实际上必须严格包含在真公式类中,因为他的定理展示了一个真但不可证明的公式。他提出了一个有趣的评论,即他的证明并不是没有受到直觉主义者的批评。然后他在第8-9页指出了康托尔对角线论证的意义:与其说人们可以用新的公式扩展到任何形式系统之外(尽管康托尔的论证确实表明了这一点),不如说有些命题可以在一个系统中表达自己,但不能在系统中判定,而且这种系统可以是像他所构建的那种简单类型。他再次借鉴康托尔的对角线论证,表明所有的数学都不能被划入一个单一的系统,但他指出,他的定理表明,即使是他所处理的数学的基本组成部分也不能成为完整的数学。他回顾说,在他的论文中,他说不可判定的命题可以在更高的系统中变得可判定,但他的定理表明,在那里会发现进一步的不可判定的命题,等等。

哥德尔的信在第9-10页以寒暄结束,包括准备对策梅洛1930年的论文进行评论。对我们来说,不幸的是,策梅洛在1029日的回信并没有接受邀请,而是集中在哥德尔的最后一点上,即更高层系统中可判定性的可能性。他强调,这些更高层系统中可能有新的证明方法以及新的命题,并借鉴康托尔的对角线论证,将哥德尔定理的特点描述为将证明有限地限制在一个可证明命题的可数子集上。可能有更普遍的系统毫无疑问,他想到了他自己的方案--在量化水平的索引中使用了无限序数。


尽管策梅洛在[1932b][1935]中重新修改了他的想法,但他的建议过于模糊,对后来试图将证明扩展到无限长的尝试产生了影响。(例如在[Karp 1964]中调查了这种后来的工作)。策梅洛似乎没有完全理解哥德尔结果的含义。我在这里看到了一个我以前多次注意到的历史原则的例子:不仅仅是一个新的结果或方法的同时代人对它有困难,而后来的人很容易掌握,而且特别是那个结果或方法的新来者确实经历了一些与那些同时代人有关的困难。这是一个可以用教育模仿历史的口号来表达的原则,也是我对数学教育的非历史性感到遗憾的原因之一。策梅洛对哥德尔定理的评论,以及哥德尔的回答,非常类似于人们在课堂上与学生进行的对话,他们试图掌握本世纪最杰出的智力发现之一的意义。


二,原文


IN MEMORIAM KURT GODEL: 

HIS 1931 CORRESPONDENCE WITH ZERMELO ON HIS INCOMPLETABILITY THEOREM 

BY I. GRATTAN-GUINNESS 

MIDDLESEX POLYTECHNIC AT ENFIELD, 

ENGLAND SUMMARIES 


Shortly after publishing his now famous incompletability theorem in 1931, Kurt Godel and Ernst Zermelo corresponded about the nature and significance of Ggdel's result. The texts of the surviving letters are presented, preceded by an explanation of the circumstances of the correspondence and an indication of the historical significance of the points discussed. 



INTRODUCTION 

Kurt Gcdel (190671978) became a legend in his own life- time, principally for his theorem demonstrating the existence of a proposition which is expressible in the language of a formal system but which, like its negation, is not provable from the axioms of the system and its rules of inference. The result had major implications for two of the prevailing philosophies of mathematics (Hilbertian metamathematics and Russellian logicism), and has influenced many branches of logic ever since.

Godel proved his result in the year 1930. An abstract [Godel 1930b] was published at the end of the year, and the full paper [Godel 1931] appeared early in 1931. Later that year, on September 15, he gave a lecture on his theorem at the autumn meeting of the Deutsche Mathematiker-Vereinigung at Bad Elster. Zermelo also spoke at the same session, and later he wrote a report [Zermelo 1932a] on both his and Godel’s lectures. It was presumably in connection with this report that the correspondence with Godel occurred.

Zermelo must have written to Godel on September 21, 1931, for Godel acknowledged its receipt at the beginning of his 10-page reply of October 12 from Vienna. Zermelo's letter must be lost, for Godel lost many of his Vienna papers during the last war [see van Heijenoort 1967, 619]. But two carbon copies of Zermelo's answer of October 29 from Freiburg im Breisgau are preserved with Godel’s letter in Zennelo's Nachlass in the city's university library.

The main point of contention between the two men concerned a clash between their conceptions of proof, and the possibility of  the existence of undecidable propositions. In his paper of 1930 Zermelo had begun to use the axiom of regularity in his axiomatic set theory. The purpose of the axiom is to ‘well-foud’ sets by preventing unending descents of membership of sets, and Zermelo used it in [1932a] also to stratify the sets into mutually disjoint ‘layers’ [Schichten] (Qa) of sets. Very briefly, the idea is that Qo is the layer of ‘original elements’ of the axiomatic system, and each layer Qa is made up of those sets which do not belong to any preceding layers. The definition proceeds by transfinite induction : The index a starts at 0 and runs through a well-ordered series of ordinals. For limit ordinals the definition needs special treatment, whose details need not concern us here.

In a similar way Zermelo took a ‘basis’ of a mathematical theory to be composed of an ‘original range » of elements and ‘ground-relations’ between them. Propositions are then further relations built up by ‘quantification’ (meaning logical conjunction and disjonction) and negation of these relations. A collection of propositions is ‘well-founded’ on that basis with respect to the notion of consequence if each subcollection T of S contains at least one proposition which is not a consequent of any member of S. 

He showed that S could be stratified into ‘layers of quantification’, each layer indexed by an ordinal. He then argued (rather vaguely!) that if the ground-relations are divided arbitrarily into ‘true’ and ‘false’, then the division carried over into each layer of propositions, and that if the ground-relations are consistent (surely he means those which are designed as true, although then their designation cannot be arbitrary), then the derived relations are also consistent. For him it then followed that any proposition which is true is also provable in the sense of belonging to some level of quantification. But this situation would, naturally, be contradicted by Godel’s theorem.

In response to Zermelo’s lost letter of September 21, Godel  carefully explains the workings of his proof. He begins by confirming that the first section of his paper  [1931] is not a ‘binding proof’ of his theorem, but a guide to the correctness of the proof which then follows in great detail in the paper, based on the 46 definitions. He then mentions the similarity between his proof-method and Cantor’s diagonal argument (as he does also in this opening part of his paper) : This is a feature which will arise later. But first on pages 2)3 he discusses the class of ‘true’ formulae which Zermelo seems to have proposed in the hope of generating a paradox like the liar paradox in Godel’s system. Godel shows in detail on page 3-7 that, unlike his own class of provable formule, Zermelo’s class of true formulae cannot ne expressed in a ‘purely combinatorial’ way in the language of his system, so that no such paradox will arise.

In these pages Godel also lays emphasis on the metamathematical character of the argument; that is metamathematical we talk about names of formulae and so on Despite the attention given to the distinction between theory and me theory in the 1920s with Hilbert’s revival of his proof theory, logicians still tended to conflate symbol and referent; indeed, Professor J. Barkley Rosser once told me in reminiscence that it was only with Godel’s theorem that logicians realised how carful they needed to be in this matter.

Godel then goes on (pages 7-8) to tree that the class of provable formulae must in fact be strictly contained in the class of true formulae, since his theorem exhibits a true but unprovable formula. He makes the interesting comment that his proof is not free from criticism from intuitionists. He then points out on pages 8-9 the bearing of Cantor’s diagonal argument : not so much that one can extend beyond any formal system with new formulae (though Cantor’s argument does show that), but that there are propositions which can ‘express themselves’ within a system but cannot be decided within it, and that such systems can be of such a simple kind as the one that he constructed. He draws on Cantor’s diagonal argument again to show that all mathematics cannot be drawn into a single system, but points out that his theorem shows that even the fundamental component of mathematics which he has treated cannot be made complete. He recalls that in his paper he stated that undecidable propositions can be made decidable in higher systems, but that his theorem showed that further undecidable propositions would be found there, and so on. 

Godel’s letter finished on pages 9-10 with pleasantries, including a readiness to comment on Zermelo’s paper of 1930. Unfortunately for us, Zermelo’s reply on October 29 did not accept the invitation but concentrated on Godel’s last point, the possibility of decidability in higher system. He stressed that these higher systems may have new proof methods in them as well as new propositions and drew on Cantor’s diagonal argument to characterise Godel’s theorem as confining proof ‘finitistically’ to a denumerable subset of provable propositions. There may be more general systems - and doubtless he had in mind his own scheme - where transfinite ordinals were used in the indexing of the levels of quantifications.

Although Zermelo reworked his ideas in [1932b] and [1935], his proposal is too vague to have been influential on the later attempts to extend proofs to infinitely lengths. (Such later work is surveyed in, for example, [Karp 1964]). Zermelo seems not to have fully understood the implications of Godel’s result. I see here an example of an historical principle which I have noticed in action many times before : not merely that contemporaries of a new result or approach have difficulties with it which later generations master easily, but especially that new comers to that result or approach do go through some of the same difficulties that concerned those contemporaries. It is a principle expressible by the slogan ‘education imitates history,’ and is one of the reasons why I deplore the non historical character of mathematical education. Zermelo’s comments on Godel’s theorem, and Godel’s replies, are very similar to the conversations which one has in the classroom with students trying to grasp the signification of one of the most remarkable intellectual discoveries of this century.

参考文献:

1In memoriam Kurt Godel: His 1931 correspondence with zermelo on his incompletability theoremhttps://www.sciencedirect.com/science/article/pii/0315086079901277




https://wap.sciencenet.cn/blog-2322490-1337173.html

上一篇:策梅洛写给哥德尔的信
下一篇:波利亚猜想(Pólya conjecture)
收藏 IP: 77.201.68.*| 热度|

1 杨正瓴

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

数据加载中...

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

GMT+8, 2023-2-8 08:49

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部