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

博文

哥德尔不完备性定理的接纳过程(译文) - John W. Dawson Jr.

已有 1037 次阅读 2022-11-14 05:19 |个人分类:解读哥德尔不完全性定理|系统分类:科研笔记

哥德尔不完备性定理的接纳过程(译文 - John W. Dawson Jr.


1. 1930:  KÖNIGSBERG宣布 

2. 1931: 出版和对抗

3. 认可和对优先权的挑战 

4. 同化与后期批判

5. 挥之不去的疑虑

6. 结论 



关于形式上不可判定的命题的工作,人们感到像地震一样;对Carnap尤其如此(Die Arbeit über formal unentscheidbare Sätze wurde wie ein Erdbeben empfunden; insbesondere auch von CarnapPopper1980)。库尔特-哥德尔在现代逻辑学方面的成就……是一个在时空上将保持可见的地标(约翰--诺伊曼)。事实上,如何更好地表达这些结果的影响它们对希尔伯特计划的影响是如此之大,其哲学上的回响至今仍未平息而不是谈论震荡和冲击波?不可避免会想到地震,然而采用这样的意象是在暗示,智力动荡的后果与地质大灾难的后果相当:一个缓慢重建的时期,最初是广泛的混乱和绝望,或者是坚定的抵抗;尽管我们可能期望哥德尔的发现恰恰引起这样的反应,但根据大多数评论家的说法,并非如此。因此,van Heijenoort说,尽管[哥德尔的论文]引起了一些短暂的惊讶,但其结果很快就被广泛接受了van Heijenoort, 1967, p. 594)。同样地,Kreisel断言预期的反对意见从未出现Kreisel, 1979, p. 13),而Kleene在谈到第二个不完备性定理(其证明在哥德尔(1931)的论文中仅被勾勒出来)时,甚至声称似乎没有人怀疑它Kleene 1976, p. 767)。


如果这些说法是正确的,那么逻辑学和数学史上最深刻的发现之一被哥德尔的同时代人迅速吸收,而且几乎没有反对意见这种情况如此显著,需要加以解释。公认的解释似乎是,哥德尔对哲学界的舆论氛围很敏感,并预见到了对他的工作的反对意见,他以如此清晰和严谨的方式展示了他的成果,使其无可争议,即使在一个数学哲学竞争激烈的时代。哥德尔逻辑的纯粹力量有效地扫除了反对意见,以至于哥德尔放弃了他所说的出版第二条定理的详细证明的意图(1931年,第198页)。关于最后一点,不可能有任何争议,因为哥德尔对van Heijenoort 明确表示,他的结果被迅速接受是使他改变计划的原因之一van Heijenoort, 1967, footnote 68a, p. 616)。


然而,我们可能会质疑,哥德尔的主观印象在多大程度上反映了客观事实。我们还必须认识到,从我们自己的角度评估哥德尔论证是有风险的。可以肯定的是,在(Gödel, 1931)中的论述现在看来是清晰而有说服力的;证明给我们的印象详细但并不复杂。但在当时看来是这样吗?毕竟,语法的算术化在当时是一种新的手段,而且逻辑学家们还不太习惯于对对象语言和元语言进行精确区分的必要性。事实上,J. Barkley Rosser(他本人对哥德尔结果的改进做出了贡献)观察到,只有在哥德尔的论文出现之后,逻辑学家才意识到他们必须十分小心(参见Grattan-Guinness, 1981, footnote 3, p. 499);正是因为哥德尔的结果,我们不再分享形式主义者的天真乐观,所以我们可能更容易接受哥德尔的想法。我们对逻辑作为克服知识阻力的工具的效力的信心,也应该通过考虑给予其他悖论结果的接受程度而得到缓和。例如, Löwenheim-Skolem定理,由Löwenheim1915年首次提出,并由Skolem1920年至1929年的一系列论文中以更高的精度和更广泛的通用性确立,当然没有哥德尔的发现那么深刻(然而,它有时仍然被混淆),但它却引起了广泛的误解和困惑,甚至直到193812特别是见Gonseth, 1941, pp.47-52的讨论)。


在下文中,我将比较详细地考察对哥德尔定理的反应,目的是表明有怀疑者和批评者,也有捍卫者和竞争优先权的对手当然,也有一些人在没有完全理解哥德尔的结果的情况下接受了这些结果)。


1. 1930: KÖNIGSBERG宣布 


在其他地方(Dawson, 1984),我已经详细描述了围绕哥德尔首次公开宣布其不完备性发现的情况。总之,这一事件发生在193097日在Königsberg举行的关于数学基础的讨论中,是由Gesellschaft für empirische Philosophic组织的第二届精确科学认识论会议的最后一次会议。当时,哥德尔在维也纳以外的地方几乎无人知晓;他来参加会议是为了就他的论文成果发表20分钟的演讲,该论文在一年前完成,当时刚要付印。在那篇论文中,哥德尔建立了一个对推进希尔伯特计划至关重要的结果:一阶逻辑的完备性(或者按当时的叫法,限制性函数计算);所以很难预料到,在他演讲的第二天,哥德尔会突然断言存在形式上不可判定的命题,从而破坏这一计划。正如Quine所评论的,“[尽管]完备性是可预期的,但完备性的实际证明却不那么可预期,而且是一个显著的成就。它的出现是一个值得欢迎的保证….。另一方面,初级数论的不完备性数论是对坚定的先入之见的破坏Quine, 1978, p. 81).


从发表在ErkenntnisHahn等人,1931年)上的讨论的(编辑过的)记录稿来看, Königsberg的其他与会者没有一个人对哥德尔将要说的话有丝毫的了解,而且宣布本身是如此的随意,以至于我们怀疑其中一些人可能没有意识到他到底说了什么。特别是,会议记录没有显示出对哥德尔言论的任何讨论,而且在Reichenbach对会议的会后调查中也根本没有提到哥德尔(发表在Die Naturwissenschaften 181093-4)。然而,在场的人中至少有两个人应该对哥德尔的结果有所了解,Hans HahnRudolf CarnapHans Hahn是哥德尔的论文指导老师,他主持了Königsberg的讨论,估计也是他邀请哥德尔参加的。当然,哥德尔可能没有把他的新发现告诉他事实上,王浩说, “哥德尔在给Hahn看之前就完成了他的论文Wang, 1981, footnote 2, p. 654但在论文的介绍性发言中,哥德尔明确提出了不完备性的可能性(但没有声称已经证明了它),这些发言被从出版版本中删除(我们不知道谁要求的),也许Hans Hahn只是没有认真对待这种可能性。


无论如何,哥德尔在 Königsberg的讨论之前确实向 Carnap透露了他的发现,我们从CarnapNachlass中的Aufzeichnungen得知。具体来说,1930826日,哥德尔在维也纳的Reichsrat咖啡馆会见了CarnapFeiglWaismann,他们在那里讨论了前往Königsberg的计划。之后,根据Carnap 在该日的记录,讨论转向了“Gödels Entdeckung”


Unvollständigkeit des Systems der PM; Schwierigkeit des Widerspruchsfreiheitbeweises。在那个场合, Carnap 指出Zuerst(在FeiglWaismann到来之前)erzählt mir Gödel von seiner Entdeckungen。那么,为什么在 Königsberg Carnap坚持主张把一致性作为形式理论充分性的标准?他这样做可能只是为了给哥德尔提供一个机会,这似乎很难令人信服。似乎更有可能的是,他只是没有理解哥德尔的想法。(碰巧的是,在哥德尔的论文出现后, Carnap随后于193127日所作的说明提供了证实:在哥德尔的论文出现之后,提供了确认:哥德尔在这里。关于他的作品,我说,它毕竟难以理解( Gödel hier. über seine Arbeit, ich sage, dass sie doch schwer verständlich)。当然,后来Carnap也是帮助宣传哥德尔的工作的人之一;但本文开头引用的Popper的话似乎是对Carnap最初反应的准确描述。

约翰--诺伊曼(John von Neumann)是立即意识到哥德尔言论的重要性的讨论参与者之一:会议结束后,他把哥德尔拉到一边,追问他进一步的细节。此后不久,他回到了柏林,并于1120日写信给哥德尔,宣布他发现了哥德尔结果的一个显著[bemerkenswert]推论:一致性的不可证明性。然而,在此期间,哥德尔自己也发现了他的第二个定理,并将其纳入了他的论文中;1117日,《月刊》的编辑们收到了完成的文章。


2. 1931: 出版和对抗


19311月,哥德尔的论文被发表。但甚至在那之前,其内容的消息已经开始传播。例如,19301224日,Paul Bernays写信给哥德尔,要求得到一份(1931年)的样书,CourantSchur告诉他,这篇文章包含了重要的和超乎寻常的内容。哥德尔立即作出回应,1931118日,Bernays在一封长达16页的信中承认他收到了这些小册子,他在信中把哥德尔的成果描述为在基础问题研究中的一个重要的突破


Gödel-Bernays的通信因其对希尔伯特反应的揭示而具有特殊的意义(在没有更直接证据的情况下)。在118日的同一封信中,Bernays讨论了希尔伯特最近对数论通常领域的扩展”—他引入了ω规则--以及冯-诺伊曼的信念,即每一种统一的证明方法都可以在哥德尔的系统P中得到形式化。 Bernays本人认为哥德尔定理建立了一个二元对立关系:要么冯-诺伊曼是对的,哥德尔考虑的系统不可能有有限一致性证明,要么某些有限证明方法在P中无法形式化哥德尔在他的论文中明确指出了这种可能性。Bernays认为,无论如何,人们不得不[hingedrängt]削弱哥德尔的假设,即公理类和推理规则是(原始的)可递归的定义。他提出,通过连接ω规则得到的系统将摆脱不完备性,但也可能通过有限性手段证明一致性。但是(根据Carnap1931521日的Aufzeichnung)哥德尔认为希尔伯特的计划会因为接受ω-规则而受到损害。


稍后,哥德尔给Bernays 寄去了一份不完备性论文的印刷本,同时也给希尔伯特附了一份。在420日的回执中, Bernays 承认他无法理解为什么真谓词不能在数论中被形式定义,他甚至提出了这样一个定义的候选者,以及为什么阿克曼的一致性证明(他已经接受为正确)不能在那里被形式化。到了53日,当他再次给哥德尔写信时, Bernays已经认识到了自己的错误,但这封书信仍然很有意义,不仅因为它暴露了Bernays在吸收哥德尔定理的结果方面的困难,而且因为它提供了哥德尔意识到真理概念的形式上不可定义的独立证据在(1931)中没有提到这一事实。


因此,哥德尔在(1931)中采用的形式化方法似乎达到了目的,确保了他的结果被三个主要形式主义者所接受。但同时,即使在那些欣赏形式化价值的人中,哥德尔对系统P的精确说明也使人对其结论的普遍性产生了怀疑。


部分是为了避免这样的反对意见,哥德尔很快将他的结果扩展到更广泛的系统类别(在(1930/31)和(1934)中),在(1931)的前言中,他还基于基础公理系统的健全性而不是其形式上的一致性属性,给出了他的结果的非形式证明。毫无疑问,他希望这种非形式的简述能够帮助他的读者应付接下来的形式化细节;但是很多人都没有进一步阅读。具有讽刺意味的是,由于后来产生的误解,(1931)前言被称为该论文的一个错误Helmer, 1937)。


1931年期间,哥德尔至少在三个场合谈到了他的不完备性结果:在 Schlick circle的会议上(115日),在Karl Menger的数学座谈会上(122日),以及最重要的,在Bad Elster的德国数学协会的年会上(915日),在那里,他遇到了他最严厉的批评者之一,Ernst Zermelo


两人之间的问题是哲学和方法论上的深刻分歧。Zermelo自己在Bad Elster的演讲中(摘录于Zermelo, 1932),抨击了“kolemism,即每个数学理论,甚至集合理论,都可以在一个可数模型中实现的学说”—Zermelo认为这一学说是理查德的二律背反的体现。


Zermelo来说,量词是无穷的合取或者无限势(unrestricted cardinality)析取,由于复合语句的真值因此是在分配给Grundrelationen的真值的基础上通过无限归纳来确定的,Zermelo认为这种确定本身构成了每个命题的证明或伪。没有不可判定的命题,只是因为Zermelo的无限逻辑没有句法成分。因此,Zermelo否定了哥德尔证明不可判定命题的企图,说哥德尔只将有限性限制应用于他的系统中的可证明'语句',而不是属于它的所有语句,因此,哥德尔的结果,就像LöwenheimSkolem 定理一样,取决于(不正当的)势的限制,与'数学中绝对无法解决的问题'的存在无关。


在他发表的评论中, Zermelo并没有指责哥德尔论证的正确性;他只是把它当作有限性限制站不住脚的证据。但在921日,紧接着会议之后, Zermelo 私下写信给哥德尔,告知他在他的论证中存在一个“essential gap”[eine wesentliche Lücke](这封信的全文见Dawson1985))。事实上, Zermelo认为,只要从哥德尔的结构中省略证明谓词,就会得到一个否定自身的形式句子,从而产生类似于罗素[1]的二律背反的矛盾 Zermelo的信促使两人进一步交换信件(发表在Grattan-Guinness(1979)中),哥德尔耐心地解释了他的证明的工作原理,指出在他的系统中不可能对真理进行组合定义,并强调他的论文的前言( Zermelo 提到的)并不是像后来的详细考虑一样要精确。在回信中, Zermelo 感谢哥德尔的回复,他说,他从信中更好地理解了哥德尔的意思;但在他发表的报告中,他仍然完全没有理解哥德尔在语法和语义之间的区别。


3. 认可和对优先权的挑战 


尽管(也许是因为)Zermelo作为论战者而闻名,他对斯科莱姆主义(Skolemism的讨伐很少赢得追随者,他对哥德尔工作的批评似乎也被忽视了。1932年春天,Karl Menger在他的演讲Die neue Logik(由Franz Deuticke1933年作为 "fünf Wiener Vorträge "之一发表在小册子Krise und Neuaufbau in den exakten Wissenschaften中;英文译本见Menger1978))中,成为第一个向大众阐述不完备性定理的人。次年6月,哥德尔向维也纳大学提交了(1931年)他的Habilitationsschrift19331月,他接受邀请,在普林斯顿新成立的高级研究所度过1933-34学年。


1933311日,哥德尔的Dozentur被批准。同一天,苏黎世的Paul Finsler给哥德尔写了一封信,要求提供(1931)的副本。他说,他对哥德尔的工作感兴趣,因为它似乎与他自己的早期工作密切相关(Finsler, 1926),他已经稍稍瞥了一眼哥德尔的论文,承认哥德尔采用了一个更狭窄的、因此更尖锐的形式主义。他承认, “当然有价值 “实际上在一个特定的形式主义中执行[这种]想法,但他没有这样做,因为他觉得他已经以一种进一步应用于希尔伯特方案的方式建立了结果。

哥德尔认识到这是一个挑战,在325日的回复中,他将Finsler的系统定性为根本没有真正定义”[überhaupt nicht definiert],宣称Finsler的想法不可能在一个真正的形式系统中进行,因为Finsler定义的对角线序列(他的不可判定的命题基于此)永远无法在同一系统中表示。Finsler愤怒地反驳说,一个系统没有必要被尖锐地定义,以便对它进行陈述;只要能够接受它是给定的,并认识到它的一些属性就足够了。他说,他可以更公正地反对哥德尔的证明,理由是哥德尔没有证明他所使用的Peano公理是一致的(尽管有哥德尔的第二个定理!)。他看到哥德尔的不可判定句子的真理只能以元数学的方式建立,因此得出结论,他和哥德尔的例子之间没有原则性的区别


Van Heijenoort详细分析了Finsler的论文,得出结论说,它仍然是一个草图,其“[与哥德尔的论文]的相似性不应该被夸大1967,第438-40页)。实际上,哥德尔把形式系统的概念放在他研究的中心位置,而Finsler则拒绝这种系统,认为它是人为的限制性的(促使 Alonzo Church干脆地说,这种限制性的概念至少有一个优点,就是可以从一个人精确地传达给另一个人)(Church1946)。相反,特别是在他的(1944)中,Finsler试图证明没有绝对不可判定的命题这一论断的一致性。


与此相反,Emil Post将他的努力指向了证明数学中存在绝对无法解决的问题。早在哥德尔之前近十年,Post就意识到他的方法可以应用于产生 Principia 中不可判定的语句,但其真值却可以通过元数学的考虑来确立。因此,Post的结论是, “数学证明在本质上是一种创造性的[活动]”,其正确的阐释需要对人类思维的所有有限过程进行分析;由于这种分析的影响可望远远超出 Principia 的不完备性,Post认为没有理由去追究后者。然而,与FinslerZermelo不同的是,Post对哥德尔的工作表示了最大的钦佩,而且他从未试图贬低哥德尔的成就。事实上,Post向哥德尔承认,他所做的任何事情都无法取代您的证明的精彩事实”,而且毕竟,构成......伟大的不是思想,而是思想的执行Post预期的叙述直到1941年才提交,并且(在被拒绝之后)直到1965年,即Post去世11年之后才最终出现在印刷品中。


至于早期关于数学命题的形式可判定问题的工作,我只知道Finsler的一篇论文….。然而,Finsler恰恰省略了使证明成为可能的要点,即限制在一些定义明确的形式系统中,在这些系统中,命题是不可判定的。因为他的目的是要在绝对意义上证明形式上的不可判定性,这是毫无意义的。这就导致了[][符号系统和其中的形式证明]的无稽定义……并导致了公然的不一致,即他通过论证来判定形式上不可判定的命题……根据他自己的定义......PM 一个形式的证明。如果Finsler把自己限制在某个定义良好的形式系统S中,那么他的证明……可以[用哥德尔自己的方法的后见之明]变得正确并适用于任何形式系统。我自己在写我的论文时并不知道他的论文,其他数学家或逻辑学家可能也不理会它,因为它包含刚才提到的明显的废话(哥德尔致约瑟夫-巴拉斯,1970527日)。


特别是在运用到Finsler后来的工作时,明显的废话(obvious nonsense这一称谓是合适的Finsler1944)尤其是一个几乎病态的例子,说明了由于未能区分使用和提及而可能产生的混乱哥德尔无疑对任何对手声称他最伟大的发现具有优先权很敏感。然而,上面引用的这段话是异常严厉的,就其嘲笑在绝对意义上证明形式上的不可判定性的想法而言,它似乎忽略了哥德尔自己在1946年普林斯顿两百周年纪念会议上的言论,在这些言论中,他建议,尽管有不完备性定理,仔细研究表明,[这些负面]结果并没有使有关绝对概念的定义在所有情况下都不可能。特别是,他指出, “通过一种奇迹,可计算性的概念有一个绝对的定义,尽管它只是一种特殊的可证明性或可判定性;事实上,不完备性定理可以归纳为存在算法上不可解决的问题的推论。


当然,Finsler1933年没有这样的想法,哥德尔也没有。但Post呢?如果他没有受到狂躁抑郁症的阻碍,他可能已经抢先取得了哥德尔的结果?无论如何,哥德尔对递归理论的发展所做的贡献远远小于Post,尽管他给出了一般递归函数概念的第一个定义(1934年,根据Herbrand的建议)。直到图灵的工作(1936/37),哥德尔一直抵制接受丘奇的论文(详见Davis 1982),我们完全可以怀疑哥德尔对具体形式主义的关注是否倾向于蒙蔽他对算法不可判定性这个大问题的眼睛。


哥德尔反复强调他的哲学观对他的数学努力的成功的重要性;也许它也可能对偶尔的疏忽负责。(关于递归函数理论的起源,见Kleene(1981a)(1981b),关于哥德尔作为旁观者的另一种观点,见Feferman(1985))。


4. 同化与后期批判


1934年冬季和春季的IAS讲座之后,哥德尔回到维也纳,将注意力转向集合论。到1935年秋天,当他短暂地回到IAS的时候,他已经成功地证明了选择公理的相对一致性。然而,在此期间,他也曾经不得不进入疗养院治疗抑郁症。回到美国后,他的病情复发,迫使他在到达美国后两个月就回到了奥地利。他再次进入疗养院,直到1937年春天才恢复在维也纳大学的教学。


在这段丧失能力的时期,哥德尔的不完备性结果被Rosser1936)改进(他将ω-一致性的假设弱化为简单的一致性),并且如前所述,通过ChurchKleeneTuring对递归理论的发展而得到扩展。那么,到了1936年,不完全性定理似乎已经在牢固确立的数学事实库中占有一席之地。


然而,在这一年,哥德尔结论的正确性受到了Chaïm Perelman1936)的质疑,他断言哥德尔事实上发现了一个二律背反。根据Perelman的说法,如果假定基础公理系统是健全的(正如哥德尔在他的非形式介绍性前言中所做的那样),哥德尔的方法可以被用来证明两个错误的等价关系,即


Dem(, qFq) = Dem(qFq)

and 

Dem(qFq) = Dem(Fq)


其中’Fq'表示哥德尔的不可判定句子,'Dem'表示哥德尔的可证明性谓词(在哥德尔(1931)中称为'Bew')。第二种说法显然是矛盾的,Perelman提议通过拒绝接受不可证明句子的哥德尔数集的激进权宜之计来驱除它。Perelman的等价关系显示了对象和元语言的相当明显的混淆,而且,正如Kleene 在他对(Perelman, 1936)的评论中所指出的,如果不滥用符号来表达,其中第一个不是假的,第二个也不是可推导的”(Kleene, 1937a)--事实上,正确表述,第一个等价关系只是 "Fq « 在形式上不可判定的声明。因此,很容易把Perelman当作一个怪人,如果不是他的论证显然被数学界的许多人相当认真地对待,以至于两个人,Kurt GrellingOlaf Helmer,觉得有必要来为哥德尔辩护。


Grelling1930年与哥德尔一起前往 Königsberg的人之一。193722日,他写信给哥德尔,告诉他Hempel的报告,布鲁塞尔和巴黎的愤怒的数学家Perelman的论点吸引”[hereingefallen]。如果哥德尔还没有计划发表反驳,Grelling要求允许他这样做。事实上,哥德尔并没有参与这场争论,Grelling的文章(1937/38)与Helmer的文章(1937)差不多同时出现。


Grelling 在回答 Perelman时,首先给出了哥德尔证明的非形式概要,仔细区分了算术陈述和它们的元数学对应物。他解释说,通过算术化的过程,一个元数学陈述Q′与哥德尔的算术陈述Q相关联,这样一来,对Q的任何形式证明都会有一个Q′的元数学证明。但是,他断言,对Q′的元数学证明或反驳将直接导致元数学矛盾("Sowohl ein Beweis von Q′ als auch eine Widerlegung würde unmittelbar auf einen Widerspruch führen" )(Grelling, 1937/38, p. 301),因此Q本身在形式上必须是不可判定的。Grelling接着分析了Perelman的形式论证,特别是他的以下主张


Dem(nFn) .⊃. Dem(Dem(nFq))

(1)

and 

Dem(nFn) .⊃. Dem(Dem(nFn) 

(2)


在哥德尔的系统中是可以证明的。他没有评论所涉及的符号的滥用(据此’Dem'应该对应于哥德尔的元数学谓词'Bew',而不是其算术对应的哥德尔数),他(正确地)接受(1)为可证明的,而拒绝(2)。


另一方面,Helmer强调了Perelman的符号混乱,指出'"Dem "是一个只适用于数字的谓词,'因此,'如果公式(1)是有意义的,表达式 "Fn''必须表示一个数字而不是一个句子'。因此,我们可以把 "Fn "解释为 "对与[通过算术]相关的数字的指称,它是在所有数字谓词的句法列举中,在第n个谓词的论点位置上替换了 "n",但即使如此,Helmer认为,公式(1"[不可能]被合法化"Helmer, 1937)。

RosserKleene在《符号逻辑杂志》上发表的评论中对GrellingHelmer的文章进行了批评(Rosser1938)和Kleene1937b))。Rosser指出,"[Grelling]对哥德尔证明的最后步骤的阐述 "与他自己对它的理解不一致,而且Grelling在上面引用的关于Q′是元数学上不可判定的说法 "无疑是错误的,......因为在前面的一句话中他说Q′是一个元数学定理"。然而,在这里,我们可以争论一下。Grelling并没有说Q′是一个元数学定理,他只是把它称为'ein metamathematischer Satz’,在这里只是指一个陈述或命题;相反,Grelling的陈述必然是假的,正是因为Q′是一个元数学定理(在元数学论证表明Q在其预定的解释中是真的意义上)。至于Helmer Kleene 同意Perelman的错误根源在于他未能区分公式和它们的哥德尔数,但他也注意到Helmer未能像区分……元数学语句和正式数学句子一样一致地区分它们和后者的......句法数。同时,他肯定了Perelman的等价物(1)的基本合法性,“Helmer notwithstanding”


Perelman的论文所引发的争论不仅暴露了早期接受哥德尔结果的脆弱性,而且也暴露了他们的潜在捍卫者对这些结果的误解。因此,GrellingHelmer在批评Perelman在对象语言和元语言之间的混淆时,他们自己对句法的区分并不总是很小心。Grelling在不存在元数学矛盾的地方看到了元数学矛盾,Helmer错误地将Perelman的错误追溯到一个事实上可以证明的公式上(尽管不像Perelman想的那么容易);而罗瑟(Rosser)通过错误地翻译“Satz”,没有认识到Grelling误解的真正来源。只有 Kleene 在辩论中没有受到损害(干净)。


关于Perelman的主张及其反驳的更详细的说明,读者可以参考Ladrière的书(1957)的第三章第五节。该资料还包括对Marcel Barzin1940年)和Jerzy Kuczyński1938年)对哥德尔工作的另外两个、也是后来的反对意见的讨论。他们的挑战在当时似乎都没有得到太多的关注,所以我在这里将很少关注他们,只是注意到他们的批评,与Perelman的不同,是基于哥德尔详细的形式证明,而不是他的非形式的介绍性论证;然而,与Perelman一样,BarzinKuczyński都认为哥德尔发现了一个二律背反(实质上,Barzin混淆了形式表达式和它们的哥德尔数,而Kuczyński,从Mostowski的评论(1938)来看,忽略了哥德尔第二定理中的形式前项“Wid(κ)”)。


5. 挥之不去的疑虑


1939年,希尔伯特和Bernays的《数学基础》第二卷出版,其中首次给出了哥德尔第二不完全性定理的完整证明。不管是由于它对句法细节的细致处理,还是由于希尔伯特的隐含印记,这本书似乎终于平息了对哥德尔工作的严重反对,至少在逻辑学家的圈子里是这样。


在这个社区之外,很难评估哥德尔的成果在多大程度上被人所知,更不用说被接受或理解了。似乎许多在职数学家要么只是模糊地意识到它们,要么认为它们与他们自己的工作没有什么关系。事实上,直到20世纪70年代,随着Matijasevic 以及后来的ParisHarrington的工作,数论家们可以(而且经常)继续将不可判定的算术语句视为只有那些关心基础的人才会感兴趣的人为设计。


在当时的著作中,少数非逻辑学家(至少据我所知)认识到哥德尔的工作的是Garrett Birkhoff,在他的《 Lattice Theory》(1940年)第一版中,他指出(第128页), »’不可判定的命题的存在......似乎已经被Skolem[]和哥德尔所确立"。然而,在一个脚注中,他甚至对这种暂时性的接受进行了限定,指出'这样的结论当然取决于对所有可接受的证明方法的规定......[因此]......应该以深深的怀疑态度看待。特别是,他认为'Carnap[已经]陈述了被哥德尔排除的可信的证明方法'。在修订版(1948年)中,相应的脚注(第194页)被弱化为'问题是,是否不存在被[哥德尔的]特定逻辑系统排除的完全有效的证明方法';但正文中保留了对Skolem的提及,并且增加了一句话(第195页),宣布不可判定命题存在的证明'然而是非结构性的,取决于承认存在不可枚举的'命题',但只有可数的'证明'。显然, Birkhoff实际上并没有读过哥德尔的论文。他的陈述与Zermelo的陈述相呼应,但他并没有引用Zermelo的报告。


更令人感兴趣的是两位有地位的哲学家的反应。 Ludwig WittgensteinBertrand Russell。维特根斯坦对哥德尔定理的著名评论出现在他去世后出版的《数学基础评论》的附录一中(英译本摘录于BenacerrafPutnam1964)的第431-435页)。在该卷的序言中,它们的日期是1938年,它们从未打算出版,也许也不应该出版--当然,这与目前的调查无关。一些评论家详细讨论了维特根斯坦的言论(例如,见A.R.AndersonMichael DummettPaul Bernays的文章,BenacerrafPutnam1964)的第481-528页),几乎所有的人都认为它们是对一位伟大哲学家的工作的尴尬。当然,是很难认真对待这样的反对意见,如 "为什么不应该命题......物理学......写在罗素的符号?"; "的矛盾,产生时,有人说 "我在说谎"......是有意义的,只是因为它已经折磨人";或命题 "P是无法证明 « 有一个不同的意义后[]之前它被证明 »BenacerrafPutnam1964年,第432434)。这种看似轻率的言论背后是否有更深刻的哲学见解,必须留给维特根斯坦的学者去辩论;只需说在哥德尔看来,维特根斯坦对他的结果推进了一个完全微不足道和无趣的误读(哥德尔致Abraham Robinson197372日)。


至于罗素,这里有两段话特别有意思,一段已发表,一段未发表,时间分别为1959年和1963年。前者来自《我的哲学发展》(第114页),是罗素自己对维特根斯坦作品的评论的一部分:

- 在我对Tractatus的介绍中,我提出,尽管在任何给定的语言中都有该语言无法表达的东西[我的强调],但总是有可能构建一种更高阶的语言,在其中可以说这些东西。在新的语言中,仍然会有它不能说的东西[我再次强调],但这些东西可以在下一种语言中说出来,以此类推,无穷无尽。这个建议在当时是新的,现在已经成为逻辑学的一个公认的常识。它解决了维特根斯坦的神秘主义,我认为也解决了哥德尔提出的新的难题。


可能有人会认为,在这段话中,罗素提出了哥德尔本人在他的(1930/31)中强调的同样的观点,即通过传递到连续的更高的类型,我们可以得到一个形式系统的无限序列,这样,在每个系统中构建的不可判定的命题在所有后续系统中都是可判定的。然而,与罗素相反,哥德尔强调,这样构建的每个不可判定命题在最低层次上已经可以表达。第二段话摘自罗素196341日写给莱昂-亨金的信:

我认真研究数理逻辑已经有五十年了,从那时起,我读过的几乎唯一的作品就是哥德尔的。当然,我意识到哥德尔的工作具有根本的重要性,但我对它感到困惑。这让我庆幸自己不再从事数理逻辑研究。如果一组给定的公理导致了矛盾,那么很明显,至少有一个公理必须是假的。这是否适用于小学生的算术,如果是这样,我们能相信年轻时被教导的任何东西吗?难道我们要认为2+2不是4,而是4.001?很明显,这不是我们的本意。

你注意到,我们对试图证明我们的公理不可能导致矛盾的尝试无动于衷。在这一点上,哥德尔表明我们是错误的。但我认为,要证明任何给定的公理集不导致矛盾肯定是不可能的,因此,我对希尔伯特的工作很少关注。此外,除了我一直认为是权宜之计的可还原性公理外,我们的其他公理在我看来都是不言自明的。我看不出有谁能否认,比如说,q意味着pq,或者pq意味着qp

……在本书的后期部分……有很大一部分是由......普通数学组成。这尤其适用于关系运算。如果这里面有任何错误,除了琐碎的错误之外,那也一定是传统的序数算术中的错误,这似乎很难令人信服。

- 如果你能抽出时间,我想知道,在你看来,普通数学或者说,任何演绎系统是如何被哥德尔的工作影响的。


这封信中存在着一种奇怪的模糊性。罗素是在回忆他第一次知道哥德尔定理时的困惑,还是在表达他持续的困惑?他是说,凭直觉,他已经认识到希尔伯特证明算术一致性的方案是徒劳的,但却没有考虑严格证明这种徒劳的可能性?还是他透露了一种信念,即哥德尔事实上已经证明了算术的不一致性?亨金,至少,假设是后者;在回应罗素的最后请求时,他试图解释哥德尔第二定理的重要性,强调不完备性和不一致性之间的区别。最终,罗素的信的副本被送到了哥德尔那里,他说, “罗素显然误解了我的结果;然而,他是以一种非常有趣的方式这样做的……”(哥德尔致亚伯拉罕-罗宾逊,197372日)。


6. 结论 


就其所指的形式主义者对哥德尔结果的接受程度而言,公认的观点似乎是正确的。哥德尔的证明破灭了形式主义的希望,但同时它们对那些致力于形式主义理想的人又是最有说服力的。在其他方面,不完备性定理绝不是那么容易被接受的;在技术和哲学方面都有人提出反对意见。尤其盛行的观点是,哥德尔的结果是二律背反(antinomial),或者是有限的一般性。尤其是势限制(cardinality restrictions),常常被认为是造成不可判定性现象的原因。哥德尔在其他人失败的地方获得了成功,因为他注意到了句法和语义的区别,他对特定形式系统的限制,以及他对相对而非绝对不可判定性的关注。他预见到了对他的结论的阻力,并努力通过他的论述风格和避免客观数学真理的概念(但这是他自己的数学哲学的核心)来减少反对意见。虽然意识到对他工作的批评,但他回避公开的争论,认为他的结果很容易被那些对他来说意见重要的人所接受;尽管如此,他后来对其结果的扩展显示了他对建立其普遍性的关注。从长远来看,不完备性定理既没有导致对形式系统的拒绝,也没有导致对其局限性的绝望,而是如波斯特所预见的那样,导致了对人类理性创造能力的再次肯定。以哥德尔定理为中心,关于思维与机制的争论有增无减。


1970年对一个研究生询问的答复草稿中,哥德尔表示,正是他对可证明性的形式可定义性和真理的形式不可定义性之间的对比的认识,导致了他对不完全性的发现。他没有在(1931)中提出这一点,也许可以用他的看法来解释(在同一草案中被划掉的一段话):"由于[那些]时代的哲学偏见......客观数学真理的概念......受到最大的怀疑,并被广泛拒绝为毫无意义。关于哥德尔对语义问题的回避的更全面讨论,见Feferman (1985)。关于塔尔斯基的真理不可定义性定理,见塔尔斯基(1956),特别是书目说明,第152页;脚注1,第247-8页;历史说明,第277-8页;以及脚注2,第279页。在这些注释中,塔尔斯基清楚地表明了他对哥德尔方法的亏欠,放弃了对哥德尔自己的结果的任何优先权的要求(除了事先展示了一个一致但ω不一致的形式系统)。





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

上一篇:Comment on invente les hypothèses - Frédéric Roudaut
下一篇:哥德尔不完全性定理的接纳过程(原文) - John W. Dawson Jr.

4 强涛 刘钢 史晓雷 杨正瓴

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

数据加载中...

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

GMT+8, 2023-2-7 16:59

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部