~hanwen >_

哥德尔 β 函数

#数学

English

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

定义

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

首先我们定义商和余函数。对于所有的 𝑚,𝑛∈𝜔，如果 𝑛≠0，那么 quo(𝑚,𝑛) 和 rem(𝑚,𝑛) 分别是 𝑚 除以 𝑛 的商和余数，否则它们都是 0。

然后是（向下取整的）平方根和超出函数。对于所有的 𝑛∈𝜔，[√𝑛] 是满足 𝑘2≤𝑛 的最大的 𝑘，而 K(𝑛)=𝑛−[√𝑛]2。

接下来是 J 和 L 函数，它们的名字来源于哥德尔本人的命名。令 J(𝑚,𝑛)=((𝑚+𝑛)2+𝑛)2+𝑚，L(𝑛)=K([√𝑛])。这些定义可能一开始看起来很奇怪，但它们很快就会展示出它们的神奇之处。它们有很好的性质：对于所有的 𝑚,𝑛∈𝜔，K(J(𝑚,𝑛))=𝑚 和 L(J(𝑚,𝑛))=𝑛。证明如下。

对于 K 和 J 的这一性质，我们只需要证明 [√J(𝑚,𝑛)]=(𝑚+𝑛)2+𝑛，这可以通过以下事实得到：

((𝑚+𝑛)2+𝑛+1)2=((𝑚+𝑛)2+𝑛)2+2((𝑚+𝑛)2+𝑛+1)+12>((𝑚+𝑛)2+𝑛)2+𝑚.

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

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

哥德尔 𝛽 函数引理

对于所有的 𝑚0,…,𝑚𝑛−1∈𝜔，存在一个 𝑚∈𝜔，使得对于所有的 𝑖<𝑛，

𝛽(𝑚,𝑖)=𝑚𝑖.

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

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

裴蜀引理

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

引理：如果 𝑚,𝑛∈𝜔 且它们互质，那么存在整数 𝑎 和 𝑏 使得 𝑎𝑚+𝑏𝑛=1。

证明：令 𝑆={𝑎𝑚+𝑏𝑛∣𝑎𝑚+𝑏𝑛∈𝜔}，即所有 𝑚 和 𝑛 的正（整数）线性组合的集合。因此对于这个非空集合（非空性是显然的），必然存在一个最小值 𝑝∈𝑆。我们想要证明 𝑝=1，通过反证法来证明。假设 𝑝≠1。取 𝑞∈𝑆，令 𝑟=rem(𝑞,𝑝)，我们有 0≤𝑟<𝑝。由于 𝑝 和 𝑞 都是 𝑚 和 𝑛 的（整数）线性组合，所以 rem(𝑞,𝑝)∈𝑆，因为 𝑝 最小，所以 rem(𝑞,𝑝) 必须是 0。那么我们得知 𝑝 整除 𝑆 中的所有 𝑞。注意到 𝑚∈𝑆 和 𝑛∈𝑆，所以 𝑝 是 𝑚 和 𝑛 的公约数，这与 𝑚 和 𝑛 互质的事实矛盾。因此，如果 𝑝≠1，就会导致矛盾。所以 𝑝=1。

中国剩余定理

引理：对于所有的 𝑘0,…,𝑘𝑛−1∈𝜔，如果 𝑑0,…,𝑑𝑛−1∈𝜔 两两互质且对于所有的 𝑖<𝑛 都有 𝑘𝑖<𝑑𝑖，那么存在一个 𝑘∈𝜔 使得对于所有的 𝑖<𝑛，rem(𝑘,𝑑𝑖)=𝑘𝑖。

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

𝑘=∑𝑖<𝑛𝑘𝑖𝑎𝑖𝑚𝑖+𝑙𝑑0⋯𝑑𝑛−1,

其中 𝑙 是任意自然数，使得 𝑘≥0。

哥德尔 𝛽 函数引理的证明

最后我们来证明哥德尔 𝛽 函数引理。从 J 和 𝛽 的定义中，我们可以看到我们只需要找到一个合适的 L(𝑚) 的值，使得每一个 𝑖<𝑛 的数 1+(𝑖+1)·L(𝑚) 两两互质，然后通过中国剩余定理构造 K(𝑚) 的值，最后计算 𝑚=J(K(𝑚),L(𝑚))。为了方便，对于每一个 𝑖<𝑛，我们将 1+(𝑖+1)·L(𝑚) 记为 𝑑𝑖。

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

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

题外话（再次）

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