哥德尔 哥德尔的定理是如何玩坏数学的！

原作者，俄勒冈大学数学博士Dilts博士。

译者，冯武明，多多数学网翻译团队成员。

校对，Math001。

关注微信:数学网每天获得更多有趣的数学文本

哥德尔不完全定理是一个可以敲昏你脑子的定理。

在上一个博客中，我们讨论了定理本身及其影响。简单来说，它们显示了数学本身固有的局限性。

哥德尔第一定理与一致性和可证性的概念有关。一个数学系统如果两者之间不存在矛盾，就说是一致的。换句话说，你不能证明一个既真实又虚假的陈述。

任何一个逻辑系统，都有很多语句，也就是你能说的那些东西。比如我这样说“所有素数都小于十亿”。这是一个错误的说法，但我仍然可以说出来。

但我能说一句话，不代表我能证明它的真假。大多数情况下，那个说法很难证明，所以你不知道怎么证明。但也有可能存在既不能证明真假的说法。这种说法叫无法证实的说法。任何带有不可证明语句的逻辑系统都是不完整的。

哥德尔第一不完全定理说:如果你有一个一致的数学体系，并且你能做算术运算，那么肯定有用那些公理无法证明的语句。

换句话说，数学是不完整的。不可能证明一切。

哥德尔第一个不完全定理最基本的思想就是这句话:“这句话无法证明”。

如果你能证明这句话是正确的，从定义上来说，是可以证明的。但这句话本身就说明，无法证明；同时，因为是真的，所以无法证明。但不能既可证又不可证。所以这句话只能是无法证明的。

虽然这是我们以后会采用的基本思路，但问题是，在数学中，没有明显的形式化方法来说“这句话是无法证明的”。你说的可证明是什么意思？“这句话”是什么意思？用什么公理？

哥德尔的证明必须使所有这些都完美而严格。

第一步是证明任何严格的数学表述都可以转化为数字，反之亦然。

这一步很微妙，但并不复杂。从某种意义上说，它就像一段代码，把每个字母都转换成一个数字。比如我们可以这样做:A转换为1，B转换为2，以此类推。“数学”这个词会转换成“13-1-20-8”。计算机也使用类似的模式将文本存储为0和1。

为了给严格的数学陈述分配数字，哥德尔使用了类似的方法进行编码。实现这种编码的方式并不是唯一的，但我会讲一个接近哥德尔最初方法的方法。

第一步是给你的一个数学系统的每个数学符号一个数字。比如可能“0”存储为1，“=”存储为2，“+”存储为3。

数学陈述是这些符号的列表。通过用数字编码单个符号，可以等价地说一个语句是一个数字列表。例如，0=0相当于。

为了将一个陈述编码为唯一数，我们使其哥德尔数等于一部分素数的幂的乘积，幂的个数就是数学符号在列表中的位置。所以0=0的哥德尔数是2 1 3 2 5 1 = 90。

对于一个语句S，比如“0= 0”，我们用符号G来指代它的哥德尔数。因此，G = 90。

正如你所意识到的，即使是中等长度的句子，哥德尔数也会很快变得非常大。但是，大小不是问题，我们不需要写下来，你只需要知道这样的数字是存在的。

关键问题是，对于任何一个数，我们都可以返回得到一个数学表述。

每个数都可以唯一分解成素数的乘积。例如，145530 = 2 1 3 5 1 7 2 11 1，所以145530表示0+0 = 0。

任何严格的数学表述都可以用这种方法翻译成数字。就算是证明也不过是一堆说法。。这意味着，我们已经表明，所有的数学都可以只用数字来写。

同样，还有一种算术方法，用来检验哥德尔数表示的一串语句是否是哥德尔数表示的另一串语句的证明。

把数学语句翻译成数字似乎是一种有趣的技巧，这是证明哥德尔不完全定理的关键。

它如此重要的原因是它允许我们把任何关于证明和可证明性的问题变成关于数字的算术问题。因此，为了证明任何语句，只能用数字及其性质。

例如，考虑这个我称之为“未证明的”的陈述。这个说法是:“Y是一个说法的哥德尔数，没有X数所以X是那个说法的证明的哥德尔数”。

所以，不可证明本质上是在说“y所代表的语句是不可证明的”。然而，这不仅仅是一个关于证明和陈述的问题，也是一个关于数字及其算术关系的问题。

这种精确的算术关系非常复杂，但可以精确定义。同样，素数，一个简单得多的说法“y是素数”，有一个算术关系“不可证明”。所以Prime断言一个数是怎样的，这个断言可以通过一些比较简单的算术来判断。

现在，我们将带着未来漫长旅程的最后一部分。

哥德尔证明的最初想法是这句话:“这句话是无法证明的”。使用精确的数学陈述“不可证明的”，我们可以使这个不精确的陈述完全准确。

为了得到“此句不可证”的准确版本，我们将使用“对角引理”。引理只是你用来证明其他定理的定理。对角引理表明，就我们正在使用的数学系统而言，有一个陈述满足当且仅当不可证明)为真时，S为真。的输入是一个语句的哥德尔数。在这个例子中，这个语句是s)

明确一点，对角引理并不证明S或unappable)为真，只证明它们都是真或假。动动脑筋，想想这意味着什么。

对角引理还表明，一个未知且可能很长的数学陈述S为真，当且仅当不可证明)为真。但不可证明)为真，的定义)意味着S是不可证明的。

所以，如果能证明陈述S为真，对角引理说明我也能证明不可证明)为真。然而，不可证明)说“S是不可证明的”！所以s既是可证的又是不可证的，这是一个矛盾。

因此，s必须是不可证明的。

语句S就是我们要找的“这句话是无法证明的”这句话的确切版本。所以，不是每一个说法都可以证明的。

数学不好，数学打得不好...

关于数学系统还有很多更技术性的假设，比如必须“有效”，也叫“递归可枚举”。这些假设对哥德尔的证明至关重要。就我想向外行读者介绍的这篇文章的主要部分而言，我认为它们太技术性了。我将在下面的脚注中解释为什么系统需要有效。

算术的公理化是钢琴算术。钢琴没有直接提到所有自然数。其实只提到了0。它有一个可以计算下一个数字的“后继函数”。所以S是1的定义，S)是2的定义。因此，当把数学语句翻译成哥德尔数时，我们的编码只需要给0和S赋值，而不是单独给每个数赋值。这意味着我们的编码只需要考虑有限数量的符号。

这里指的是从我们的公理和选定的符号中诞生的任何数学。

在上一篇文章中，我们忽略了很多重要的技术假设。其中一个，在这里说。也就是你的数学体系是有效的。本质上，这意味着有一个计算机程序可以在理论上列出你的数学系统的所有定理，而不列出任何不是定理的陈述。钢琴算术就是这样，不完全定理考察的基本数学体系。标准集合论也是如此。也有一些无效的系统，往往是无用的或无聊的。比如有一种体系，把算术中所有的真语句都看作公理。所以，凡是真实的都是公理化的，从而证明是平凡的。为了使算术证明的检查工作和你的数学系统有效，这个假设是非常重要的。

哥德尔找到了直接说这句话的方法。我们将采取稍微不同的、更容易理解的方法，但哥德尔的主要动机是相同的。

引理一般相对容易证明，对角引理也是如此。然后，它的证明是技术性的，不是很有启发性。

关注微信:数学网每天获得更多有趣的数学文本