博文

古德斯坦定理（Goodstein’s theorem）（3）- 九头蛇游戏

已有 3115 次阅读 2021-12-28 03:36 |个人分类:解读哥德尔不完全性定理|系统分类:科研笔记

古德斯坦定理（Goodstein’s theorem）的证明基于序数[1]，为了形象阐释这个证明的意义，科比（Kirby）和帕里斯（Paris）在他们的论文《皮阿诺算术的可访独立性结果》中给出一个古德斯坦定理的变体: “九头蛇游戏”，重塑了希腊神话中的半神英雄赫拉克勒斯（Hercule）与勒拿九头蛇（Lerne）的神话故事 [2][3][4]。

九头蛇游戏如下：一个有许多头和脖子的怪物，作为他十二项任务中的第二项，赫拉克勒斯必须迎击九头蛇，砍下它的所有的头。问题是，当九头蛇被斩首后，头又长出来了，赫拉克勒斯能战胜九头蛇吗？

将九头蛇表达为一棵有限的树，可以被看作是一个有限的线段的集合，每个线段连接两个节点，这样每个节点都由一条唯一的路径连接到一个被称为根的固定节点，九头蛇的头部节点只有一个线段连接。比如：

赫拉克勒斯与一个给定的九头蛇之间的战斗进行如下：在阶段n（n>=1），赫拉克勒斯从九头蛇上砍下一个头，然后，九头蛇按以下方式长出n个“新头”：

当一个头被砍掉时，叶子和相应的边被从图中删除。九头蛇将从被删除的边下方的节点开始再生，生成该节点上方的树的部分的n个副本。因此，九头蛇在第一次再生时只生出一个副本，然后在第二次再生时两个副本，以此类推。然而，应该注意的是，当赫拉克勒斯砍掉与九头蛇的根直接相连的头时，它将无法再生。

令人惊讶的是，无论九头蛇的初始规模如何，都有一些策略战胜九头蛇。更令人惊奇的是，有一个策略始终有效，那就是随机地砍掉九头蛇的头，直到九头蛇完全灭绝。但更令人吃惊的是，这个结果是真实的，但不可能用递归证明等算术工具来证明它，这使得这个结果成为算术中的一个不可判定的问题。幸运的是，它可以在集合理论中得到证明，我们现在就来做这件事!

让我们定义九头蛇的权重，这种度量将不使用整数或实数，而是使用序数（nombres ordinaux）。我们将通过给每个头、每个脖子和每个节点定义一个权重来定义一个九头蛇的权重：首先给每个头分配数字0，给每个通向头的颈部分配数字1。然后，对于这些颈部中的一个或多个节点，我们关联颈部的数量。

这种权重的定义使我们能够将一个序数与每一个可想象的九头蛇联系起来。例如，给定一个九头蛇，其权重表达为，ω^(ω ^2+1)+ω^3+2。

现在赫拉克勒斯入场，砍下了其中一个头，例如，最右边树枝上的一个头，那么九头蛇的权重将变成ω^(ω ^2+1)+ω^2x2+2，这是一个严格意义上较小的权重，因为ω^2x2是一个比ω^3严格意义上的小序数。

随着这些攻击持续不减，九头蛇的力量将继续减少。由于它是一个严格递减的序数，在经过有限次的攻击后，九头蛇的力量将不可避免地降至零，也就是说，赫拉克勒斯能够打败这只狰狞的九头蛇。

人们会问：为什么以这种方式定义九头蛇的权重，而不是以另一种方式？一个直观的解释是：因为如果你以任何其他方式定义它，有可能你就无法得出“赫拉克勒斯的战斗结束”的结论。更确切地说，通过这样定义九头蛇的权重，我们确保“砍头”的操作对应一个严格递减的序数，对此我们可以应用定理“任何严格递减的序数都是有限的”。例如，如果我们将权重定义为“头数”，我们将得到一个有时增加、有时减少的序列，对于这个序列，我们将无法说出很多有意义的东西。