哥德尔的证明如何工作

他的不完全性定理击败了对一切事物的数学理论的追求。差不多一百年后，我们仍在努力理解其后果。

1931年，奥地利逻辑学家科特·哥德尔（KurtGödel）提出了有史以来最令人震惊的知识技巧之一。



那个时代的数学家们一直在寻找不可动摇的数学基础：一系列基本事实，将是一致且完整的公理，扮演着所有数学真理的基础。



但是，哥德尔令人震惊的不完全性定理由他25岁时出版的作品打破了这个梦想。他证明了，您可以提出的作为数学基础的任何公理都不可避免地是不完整的。关于数字的总会有真实的陈述，无法使用这些公理来证明。他还表明，不能使用任何公理来证明它们的一致性。



他的不完备性定理意味着，不可能对所有事物都建立数学理论，并且不可能将可证明的陈述与真实的陈述相结合。数学家可以证明的内容取决于最初的假设，而不取决于所有答案都源自的一些基本事实。



自哥德尔发现以来的89年中，数学家偶然发现了类似的未解决问题，他的定理预言了这些问题的存在。例如，哥德尔本人帮助建立了关于无穷基数的连续假设是不确定的-就像停止问题一样，其中需要确定计算机程序的执行是否会因某些输入数据而终止，或者将永远运行。甚至在物理学中也出现了无法解决的问题，这表明哥德尔的不完整性不仅影响数学，而且在某种（并非完全清楚的）意义上影响现实。



接下来是对哥德尔如何证明其定理的简短，简化和非正式的总结。

哥德尔编号

哥德尔的主要举动是将有关公理系统的陈述与在该系统内所作的陈述进行比较-以及关于数字的陈述。这种并置允许公理系统冷静地思考自己。



第一步是将任何可能的数学陈述或陈述序列与称为Gödel数的唯一数字进行匹配。



恩德尔·纳格尔（Ernest Nagel）和詹姆斯·纽曼（James Newman）在1958年出版的《哥德尔证明》一书中介绍了哥德尔编号的略微修改，以12个基本符号开头，这些符号用作表示一组基本公理的字典。例如，关于某物存在的陈述可以用符号expressed表示，加法用符号+表示。代表“下一个元素”的s可以表示数字：例如ss0代表两个。



然后为这12个字符分配Gödel数字1到12。







然后，以x，y和z开头的表示变量的字母与大于12（13、17、19，..）的质数匹配。



然后，这些符号和变量的每种组合-即可以构成的任何算术公式或公式序列-都会获得自己的Gödel编号。



例如，考虑语句0 =0。它的三个符号对应于Gödel的数字6、5和6。Gödel需要用一个唯一的1替换这三个数字的序列-该数字将不会产生其他符号序列。为此，他采用了前三个质数（2、3和5），将每个质数提高到等于序列中相应数的幂，然后乘以它们。所以0 = 0变成2 ⁶ ×3 ⁵ ×5⁶或243,000,000，



因为没有两个公式会给出相同的Gödel编号，所以此标记有效。哥德尔数是整数，数字可以通过一种方式分解为质数。因此，将243,000,000分解为因子的唯一方法是2 ⁶ ×3 ⁵ ×5 ⁶，也就是说，只有一种方法可以解密此Gödel数：通过编写公式0 = 0。



然后，哥德尔走得更远。数学证明由一系列公式组成。因此，哥德尔为每个公式序列分配了自己的哥德尔编号。在这种情况下，他还从素数序列开始-2、3、5等。然后，他将它们中的每一个提高到与该序列中相同序数位置的公式的哥德尔数相对应的幂（例如，如果公式0 = 0首先出现，^{则为2,243,000,000}），并将所有内容相乘。

算术数学

值得注意的是，即使是关于算术公式的陈述，也是如此。可以将超数学陈述转化为公式，并为其分配自己的哥德尔编号。



首先考虑公式〜（0 = 0），这意味着“零不为零”。这显然是错误的。但是，它有一个Gödel数：2等于1的幂（〜字符的Gödel数），再乘以3等于8的幂（左括号的Gödel数），依此类推，最终得到2 ¹ × 3 ⁸ ×5 ⁶ ×7 ⁵ ×11 ⁶ ×13 ⁹。



由于我们可以为所有公式甚至错误的公式生成Gödel数，因此我们可以使用其Gödel数对其进行有意义的推理。



考虑一下语句“公式〜（0 = 0）的第一个字符是波浪号”。关于〜（0 = 0）的真正的元数学陈述变成了关于特定公式的Gödel数的陈述-即，其第一个阶为1，即波浪号的Gödel数。换句话说，我们的陈述说2 ¹ ×3 ⁸ ×5 ⁶ ×7 ⁵ ×11 ⁶ ×13 ^9中只有一个因子“ 2”。如果〜（0 = 0）以波浪号以外的任何其他字符开头，则数中至少会有两个因素，因此，准确地说，2是2 ¹ ×3 ⁸ ×5 ⁶的因数×7 ⁵×11 ⁶ ×13 ⁹，但2 ²不是。



我们可以将最后一个句子转换为精确的数学公式，并使用基本符号将其写下来。该公式自然会有自己的哥德尔数，我们可以通过将其符号与质数的幂进行匹配来计算。



如果您感兴趣，则公式将显示为：有一个整数x使得x乘以2将等于2 ¹ ×3 ⁸ ×5 ⁶ ×7 ⁵ ×11 ⁶ ×13 ⁹，但是没有这样的整数x乘以4得到2 ¹ ×3 ⁸ ×5 ⁶×7 ⁵ ×11 ⁶ ×13 ⁹。相应的公式如下所示：



（∃x）（x×ss0 = sss…sss0）⋅〜（∃x）（x×ssss0 = sss…sss0）



其中sss…sss0表示2 ¹ ×3 ⁸ ×5 ⁶ ×7 ⁵ ×下一个元素s的字符的11 ⁶ ×13 ^9个副本。 ⋅符号代表“ and”，并且是基本词汇的简称：p⋅q表示〜（〜p∨〜q）。



正如Nagel和Newman所写的，该示例说明了哥德尔发现背后的一个普遍而深刻的想法：我们可以非常准确地谈论长字符序列的印刷属性，但不能直接，而是通过大整数分解的属性。



元数学陈述也可以转换为符号。“存在一定顺序的Gödel数为x的公式，证明了Gödel数为k的公式”，或者简而言之，“可以证明Gödel数为k的公式”。正是“算术”这样的陈述的能力奠定了政变的基础。

G本身

此外，哥德尔意识到可以在公式本身中替换表示公式的哥德尔自己的数字-这已经导致了无尽的问题。



要了解此替换的工作原理，请考虑公式（∃x）（x = sy）。这意味着“存在变量x，它是y的下一个元素”，或更简单地说，“ y”表示下一个元素”。像所有公式一样，它也有自己的Gödel数-一些大整数，我们称它为m。



现在，我们将在公式中输入数字m而不是符号y。结果是一个新公式（∃x）（x = sm），表示“ m具有下一个元素”。这个公式的哥德尔数是多少？我们需要传达三个特征：我们从具有哥德尔数m的公式开始。在其中，我们将y符号替换为m符号。并且，根据前面描述的匹配方案，符号y的Gödel数为17。然后让我们表示新公式sub（m，m，17）的Gödel数。



替代构成了哥德尔证明的基础。





维也纳的学生KurtGödel。在获得文凭的一年后，他于1931年发表了不完全性定理。



他考虑了以下数学陈述：“无法证明带有哥德尔数子（y，y，17）的公式。”回顾一下我们刚刚采用的表示法，我们知道我们可以通过使用Gödel数y（某个未知变量）的公式并将该变量y代入符号来获得带有Gödel数sub（y，y，17）的公式。哥德尔的数字17（也就是y出现的位置）。



头部已经开始旋转，但是，尽管如此，我们仍然可以将我们的超数学陈述“将无法证明带有哥德尔数子（y，y，17）的公式”转化为带有唯一哥德尔数的公式。我们称它为n。



最后一个替换阶段：Gödel创建一个新公式，用y代替上一个公式中出现的数字n。他的新公式如下：“无法证明哥德尔数为sub（n，n，17）的公式”。我们将此公式称为G。G



自然有一个Gödel数。这个数字是多少瞧-应该是sub（n，n，17）。根据定义，sub（n，n，17）是公式的Gödel数，它是通过将Gödel数为n的公式替换为在公式中出现等于Gödel数等于17的符号的地方而得到的。有！由于整数以独特的方式分解为素数，因此我们很清楚，公式G仅告诉我们有关公式G本身的信息，而没有其他内容。



G说它本身不能被证明。



但是可以证明G吗？如果可能的话，则意味着存在一些证明Gödel数为sub（n，n，17）的公式的公式序列。但这与公式G相反，后者表示没有这样的证明。在一致的公理系统中，相反的陈述G和〜G不能同时成立。因此，G必须不可证明。



但是，即使无法证明G，也确实是正确的。 G表示“无法证明带有哥德尔数子（n，n，17）的公式”，这正是我们已经建立的！由于G是在我们用来构造它的公理系统中存在的真实但无法证明的陈述，因此该系统是不完整的。



您可能会认为我们可以添加一些额外的公理，使用它来证明G，并解决这个悖论。但这是不可能的。哥德尔表明，公理的扩充系统将有可能根据与以前相同的方案创建一个新的真实公式G'，这在新的扩充系统的框架内无法得到证明。试图建立一个完整的数学系统，您只会追逐自己的尾巴而未成功。

缺乏一致性证明

现在我们知道，如果一组公理是一致的，则它是不完整的。这是哥德尔的第一个不完全性定理。第二个很容易从中得出结论-没有任何公理可以证明其一致性。



如果一组公理可以证明它永远不会引起争议，那意味着什么？这将意味着在这些公理基础上建立了一系列公式，证明了在数学上意味着“这组公理是一致的”的公式。但是，根据第一个定理，这套公理必然是不完整的。



但是，说“公理集不完整”与说“存在无法证明的真实公式”相同。这相当于我们的公式G。并且我们知道公理不能证明G。



因此，哥德尔通过矛盾构造了一个证明：如果一组公理可以证明其自身的一致性，那么我们就可以证明G。但是我们不能。因此，没有一套公理证明其自身的一致性。



哥德尔的证明扼杀了对一致而完整的数学系统的追求。内格尔和纽曼在1958年写道，数学家“未能完全把握不完全的深度”。今天，这种说法仍然成立。

也可以看看：

• “为什么哥德尔的不完备性定理难以证明：这是关于措辞，而不仅仅是本质”
• “ 20分钟内的哥德尔不完备定理”
• “意识和数学的秘密”