哥德尔 β 函数

在今天的递归论导论课上，我了解到了哥德尔的 函数，它可以将一个有限序列编码成一个自然数。

定义

在定义 函数之前，我们需要定义一些辅助函数。

首先我们定义商和余函数。对于所有的 ，如果 ，那么 和 分别是 除以 的商和余数，否则它们都是 。

然后是（向下取整的）平方根和超出函数。对于所有的 ， 是满足 的最大的 ，而 。

接下来是 和 函数，它们的名字来源于哥德尔本人的命名。令 ， 。这些定义可能一开始看起来很奇怪，但它们很快就会展示出它们的神奇之处。它们有很好的性质：对于所有的 ， 和 。证明如下。

对于 和 的这一性质，我们只需要证明 ，这可以通过以下事实得到：

和 的这一性质也可以通过类似的方法得到。这两个性质意味着 的参数可以从它的结果中提取出来，这说明 是一个双射。

最后，哥德尔的 函数定义为 。 （这里 的定义是一个简化版的二元函数，而不是原始的三元函数。） 这个定义看起来也有点复杂，但下面的引理会告诉我们它的神奇之处。

哥德尔 函数引理

对于所有的 ，存在一个 ，使得对于所有的 ，

这一证明还包含了一个计算这样的 的算法。

在证明之前，我们需要证明两个初步命题。

裴蜀引理

（这里展现的引理是原定理的一个弱版本。）

引理：如果 且它们互质，那么存在整数 和 使得 。

证明：令 ，即所有 和 的正（整数）线性组合的集合。因此对于这个非空集合（非空性是显然的），必然存在一个最小值 。我们想要证明 ，通过反证法来证明。假设 。取 ，令 ，我们有 。由于 和 都是 和 的（整数）线性组合，所以 ，因为 最小，所以 必须是 。那么我们得知 整除 中的所有 。注意到 和 ，所以 是 和 的公约数，这与 和 互质的事实矛盾。因此，如果 ，就会导致矛盾。所以 。

中国剩余定理

引理：对于所有的 ，如果 两两互质且对于所有的 都有 ，那么存在一个 使得对于所有的 ， 。

证明：对于每一个 ，令 。由于 两两互质， 和 互质。根据裴蜀引理，存在整数 和 使得 。这里的关键是对于每一个 ，我们构造一个数，使得它除以 的余数是 ，并以一种不会相互影响的方式组合这些构造出的数。注意到 不能被 整除，但可以被任意 且 的 整除，而且在裴蜀引理的等式右边有一个 。很容易看出，现在我们只需要取

其中 是任意自然数，使得 。

哥德尔 函数引理的证明

最后我们来证明哥德尔 函数引理。从 和 的定义中，我们可以看到我们只需要找到一个合适的 的值，使得每一个 的数 两两互质，然后通过中国剩余定理构造 的值，最后计算 。为了方便，对于每一个 ，我们将 记为 。

的值应该满足什么条件？首先，它必须使得 ，这是中国剩余定理要求的条件之一。其次，它使得这些 两两互质。使用反证法来证明如“不存在素数 使得 同时整除不同的 的 和 ”这样的命题。让我们来考虑这样的情况：存在某个素数 使得 同时整除不同的 的 和 ，即 同时整除 和 。不失一般性地假设 ，我们有 整除 。如果我们有 整除 ，那么就会导致矛盾，因为 整除 。所以事情变得明显：找到一个构造 的方法，使得 整除 。这可以通过使 可以被所有可能的 的乘积整除来实现，这个乘积的范围是 到 。也就是说，使 整除 是一个好主意。由于 应该满足的第一个条件，我们只需要取 ，其中 。在这里取 而不是 只是为了显得更优雅，二者的效果是一样的。

上面的内容并不是一个严格陈述的证明，但很容易将其重写成一个严格版。

题外话（再次）

我写这篇文章的原因并不是哥德尔的 函数将一个有限序列编码成一个数的能力很神奇（有很多其他技术可以实现这一点，例如将序列编码到素数的一个初始段的指数中），也不是证明很优雅（尽管它确实如此）。只是因为我回忆起了那两个初步命题给我带来的困惑，意识到它们现在对我来说似乎很容易，并且可以用来证明这样的引理。这感觉很奇怪，所以我决定写下来。