古德斯坦定理

古德斯坦定理是数理逻辑中的一个关于自然数的叙述，是在 1944 年由鲁本·古德斯坦所证明。其主要是在说明“古德斯坦序列”最终会结束于 0 。柯比和柏丽斯^[1] 证明它在皮亚诺算术中是不可证明的（但它可以在一个更强的系统如二阶算术中被证明）。这是继哥德尔不完备定理构造的命题（${\displaystyle {\mathsf {Cons(PA)}}}$）和 1943 年格哈德·根岑直接证明皮亚诺算术中 ε₀-induction 不可被证明之后，第三个（对自然数为真的）命题被证明在皮亚诺算术中不可证明。之后的例子是柏丽斯–哈灵顿定理。

劳伦斯·柯比和杰夫·柏丽斯介绍了一个图论中的九头蛇游戏，其行为类似古德斯坦序列：“九头蛇”是一棵有根的树，而序列每一步是砍掉它的一颗头（即树的分支），然后九头蛇则对应地会依据某些规则来增加有限数量的头。柯比和柏丽斯则证明，不管赫拉克勒斯使用何种策略来砍头，九头蛇最终会被斩杀（尽管这个过程可能会非常漫长）。如古德斯坦序列，柯比和柏丽斯证明其在皮亚诺算术中是不可证明的^[1]。

以n为基底的瓜瓞式基底表示法

古德斯坦序列是由一种“以n为基底的瓜瓞式表示法”的概念来定义的。这个表示法与平常的 n 进位制表示法很像，但一般的进位表示法无法达到古德斯坦定理的目的。在原本的 n 进位表示法，n 是一个大于 1 的自然数，而任一个自然数 m 则被改写为一些由 n 的幂次的乘积的相加之和：

${\displaystyle m=a_{k}n^{k}+a_{k-1}n^{k-1}+\cdots +a_{0},}$

其中，每个系数 a_i 满足0 ≤ a_i < n，且a_k ≠ 0。如在 2 进位中，

${\displaystyle 35=32+2+1=2^{5}+2^{1}+2^{0}.}$

所以， 35 的二进制是 100011（2⁵ + 2 + 1）。类似地，由 3 进位表示的 100 是 10201:

${\displaystyle 100=81+18+1=3^{4}+2\cdot 3^{2}+3^{0}.}$

然而需注意的是，这些指数仍非是基于 n 的表述法。如上述表示式中的 2⁵ 和 3⁴ 。

将一个 n 进位表示转换为瓜瓞式n基底表示法，首先要将每个指数改为 n 基底表示法。然后改写指数中的指数，持续这个动作直到每个数都被改为以 n 为基底表示法。

譬如， 2 进位的 35 为 100011 ，将它改写成以 n 为基底的瓜瓞式表示法为：

${\displaystyle 35=2^{2^{2}+1}+2+1,}$

(5 = 2² + 1.) 。类似的，以3为基底的瓜瓞式表示法的 100 为

${\displaystyle 100=3^{3+1}+2\cdot 3^{2}+1.}$

古德斯坦序列

古德斯坦序列 G(m) 是一个自然数的序列。第一项为 m 本身。第二项则是先将 m 以 2 为基底得出其的瓜瓞式表示法，再将所有的 2 改为 3，再减去 1。更一般地，第 (n + 1) 项的 G(m)(n + 1) 为：

• 将 G(m)(n) 转为以 n + 1 为基底的瓜瓞式表示法。
• 将所有的 n + 1 改为 n + 2 。
• 减 1。
• 重复这个过程，直到结果为 0 则停止。

前几个古德斯坦序列会很快地终止，如 G(3) 结束于第 6 步：

基底	瓜瓞式表示法	值	注记
2	${\displaystyle 2^{1}+1}$	3	以 2 为基底改写 3。
3	${\displaystyle 3^{1}+1-1=3^{1}}$	3	将 2 改为 3，再减 1。
4	${\displaystyle 4^{1}-1=3}$	3	将 3 改为 4，再减 1。此时已无任何 4 了。
5	${\displaystyle 3-1=2}$	2	没有 4 需要改为 5。单纯减 1。
6	${\displaystyle 2-1=1}$	1	没有 5 需要改为 6。单纯减 1。
7	${\displaystyle 1-1=0}$	0	没有 6 需要改为 7。单纯减 1。

之后的古德斯坦序列则成长到很庞大的数字，如 G(4) A056193 开始如下：

瓜瓞式表示法	值
${\displaystyle 2^{2}}$	4
${\displaystyle 3^{3}-1=2\cdot 3^{2}+2\cdot 3+2}$	26
${\displaystyle 2\cdot 4^{2}+2\cdot 4+1}$	41
${\displaystyle 2\cdot 5^{2}+2\cdot 5}$	60
${\displaystyle 2\cdot 6^{2}+2\cdot 6-1=2\cdot 6^{2}+6+5}$	83
${\displaystyle 2\cdot 7^{2}+7+4}$	109
${\displaystyle \vdots }$	${\displaystyle \vdots }$
${\displaystyle 2\cdot 11^{2}+11}$	253
${\displaystyle 2\cdot 12^{2}+12-1=2\cdot 12^{2}+11}$	299
${\displaystyle \vdots }$	${\displaystyle \vdots }$
${\displaystyle 2\cdot 24^{2}-1=24^{2}+24\cdot 23+23}$	1151

G(4) 会一直递增，直到基底为 ${\displaystyle 3\cdot 2^{402\,653\,209}}$ 时，会达到最大值 ${\displaystyle 3\cdot 2^{402\,653\,210}-1}$ ，并在这里停留 ${\displaystyle 3\cdot 2^{402\,653\,209}}$ 步后，然后开始递减。

这个序列到达 0 时，当时的基底为 ${\displaystyle 3\cdot 2^{402\,653\,211}-1}$。（有趣的是，这是个胡道尔数：${\displaystyle 3\cdot 2^{402\,653\,211}-1=402\,653\,184\cdot 2^{402\,653\,184}-1}$。而且，对于所有起始值大于 4 的数，都是如此。^{[来源请求]}）

不过，G(4) 仍无法很好地展示古德斯坦序列的项数是如何快速地成长。G(19) 成长更迅速，其开头几项如下：

瓜瓞式表示法	值
${\displaystyle 2^{2^{2}}+2+1}$	19
${\displaystyle 3^{3^{3}}+3}$	7012762559748499000♠7625597484990
${\displaystyle 4^{4^{4}}+3}$	${\displaystyle \approx 1.3\times 10^{154}}$
${\displaystyle 5^{5^{5}}+2}$	${\displaystyle \approx 1.8\times 10^{2184}}$
${\displaystyle 6^{6^{6}}+1}$	${\displaystyle \approx 2.6\times 10^{36\,305}}$
${\displaystyle 7^{7^{7}}}$	${\displaystyle \approx 3.8\times 10^{695\,974}}$
${\displaystyle 8^{8^{8}}-1=7\cdot 8^{(7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7)}}$ ${\displaystyle +7\cdot 8^{(7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}+7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+6)}+\cdots }$ ${\displaystyle +7\cdot 8^{(8+2)}+7\cdot 8^{(8+1)}+7\cdot 8^{8}}$ ${\displaystyle +7\cdot 8^{7}+7\cdot 8^{6}+7\cdot 8^{5}+7\cdot 8^{4}}$ ${\displaystyle +7\cdot 8^{3}+7\cdot 8^{2}+7\cdot 8+7}$	${\displaystyle \approx 6\times 10^{15\,151\,335}}$
${\displaystyle 7\cdot 9^{(7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+7)}}$ ${\displaystyle +7\cdot 9^{(7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}+7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+6)}+\cdots }$ ${\displaystyle +7\cdot 9^{(9+2)}+7\cdot 9^{(9+1)}+7\cdot 9^{9}}$ ${\displaystyle +7\cdot 9^{7}+7\cdot 9^{6}+7\cdot 9^{5}+7\cdot 9^{4}}$ ${\displaystyle +7\cdot 9^{3}+7\cdot 9^{2}+7\cdot 9+6}$	${\displaystyle \approx 4.3\times 10^{369\,693\,099}}$
${\displaystyle \vdots }$	${\displaystyle \vdots }$

尽管其成长如此迅速，古德斯坦定理说明了无论起始值为何，每个古德斯坦最终会终止于 0。

证明

古德斯坦定理的证明（需要使用皮亚诺算术以外的技巧）如下： 对于每个给定的古德斯坦序列 G(m) ，我们可以建造一个由序数所组成的平行序列 P(m) ，而且是严格递减和终止。所以G(m) 也必将停止，并且它只在达到 0 时才会终止。

对这个证明的常见的误解在于认 G(m) 达到 0 是“因为”它被 P(m) 所支配。事实是，P(m) 对支配 G(m) 毫无作用。其重点在于： G(m)(k) 存在当且仅当 P(m)(k) 存在。于是，如果 P(m) 终止，则 G(m) 也如此。而 G(m) 只有在到逹 0 时才会终止。

我们可以定义函数 f(x)，将 x 改为以k为基底的表示法，并将每个 k 换成第一个无穷序数 ω。 而序列 P(m) 中的每一项 P(m)(n) 则定义为 f(G(m)(n),n+1)。譬如，G(3)(1) = 3 = 2¹ + 2⁰ 和 P(3)(1) = f(2¹ + 2⁰,2) = ω¹ + ω⁰ = ω + 1 。序数的加法、乘法和指数都是良好定义的。

我们可声明 ${\displaystyle f(G(m)(n),n+1)>f(G(m)(n+1),n+2)}$ 。在古德斯坦序列中，将 G(m)(n) 改换基底后，将其记为 ${\displaystyle G'(m)(n)}$ 。明显的，${\displaystyle f(G(m)(n),n+1)=f(G'(m)(n),n+2)}$ ，现在我们套用 -1 运算后，因为 ${\displaystyle G'(m)(n)=G(m)(n+1)+1}$，所以 ${\displaystyle f(G'(m)(n),n+2)>f(G(m)(n+1),n+2)}$。

譬如， ${\displaystyle G(4)(1)=2^{2}}$ 乃 ${\displaystyle G(4,2)=2\cdot 3^{2}+2\cdot 3+2}$，所以 ${\displaystyle f(2^{2},2)=\omega ^{\omega }}$ 和 ${\displaystyle f(2\cdot 3^{2}+2\cdot 3+2,3)=2\omega ^{2}+2\omega +2}$ 是严格变小。需注意的是，若要计算 f(G(m)(n),n+1) ，我们要先将 G(m)(n) 改为以 n+1 为基底的表示法。所以如 ${\displaystyle \omega ^{\omega }-1}$ 等的表示式，既不会是无意义的也非等同 ${\displaystyle \omega ^{\omega }}$ 。

P(m) 是严格递减的。而标准排序算子 < 在序数上是良基关系，一个无穷的严格递减序列是不可能存在的。换句话说，每个严格递减的序数序列会停止（不可能无限）。但P(m)(n) 是由 G(m)(n) 计算出来的。 G(m)(n) 也必然停止，这意味着它会达到 0 。

虽然这个证明相当简单，但柯比-柏丽斯定理^[1] （证明了在皮亚诺算术中不会有古德斯坦定理）则是非常专门且相当困难。它使用了皮亚诺算术中的可数非标准模型（英语：Non-standard model of arithmetic）。

扩展的古德斯坦定理

假设古德斯坦定理的定义中的“将b改为b+1”的这个动作，将它改为 b+2，那么这个序列会终止吗？ 更一般地，让 b₁, b₂, b₃, … 为任意整数列，然后让第 n+1 项的 G(m)(n+1) 变成： 将 G(m)(n) 改为 b_n 的表示法，将 b_n 改为 b_n+1 再减 1 。 我们仍可断言这个序列仍会终止。 扩展的证明则将 P(m)(n) = f(G(m)(n), n) 定义为如下： 将 G(m)(n) 改为 b_n 表示法，再将所有的 b_n 改为第一个无限序数 ω。 古德斯坦序列中，从G(m)(n)到G(m)(n+1)的换底运算并不会改变 f 的值。 譬如，如果 b_n = 4 且 b_n+1 = 9， 则 ${\displaystyle f(3\cdot 4^{4^{4}}+4,4)=3\omega ^{\omega ^{\omega }}+\omega =f(3\cdot 9^{9^{9}}+9,9)}$。因此，序数 ${\displaystyle f(3\cdot 4^{4^{4}}+4,4)}$ 是 严格大于序数 ${\displaystyle f((3\cdot 9^{9^{9}}+9)-1,9)}$。

起始点为变量的序列长度函数

古德斯坦函数 ${\displaystyle {\mathcal {G}}(n)}$ 定义为由 n 为起始值的古德斯坦序列的长度。因为古德斯坦序列会终止，所以这是一个完全函数。要测定 ${\displaystyle {\mathcal {G}}}$ 的快速成长，可由多种借由标准基于序数体系中的函数，如Hardy hierarchy（英语：Hardy hierarchy） 中的 ${\displaystyle H_{\alpha }}$ 函数，和 Löb and Wainer 的 高成长体系（英语：fast-growing hierarchy） ${\displaystyle f_{\alpha }}$ 函数。

• Kirby and Paris (1982) 证明

${\displaystyle {\mathcal {G}}}$ 有着和 ${\displaystyle H_{\epsilon _{0}}}$ 近似的成长速度（等同于 ${\displaystyle f_{\epsilon _{0}}}$）; 更精确地说，对每个 ${\displaystyle \alpha <\epsilon _{0}}$，${\displaystyle {\mathcal {G}}}$ 控制 ${\displaystyle H_{\alpha }}$，且 ${\displaystyle H_{\epsilon _{0}}}$ 控制 ${\displaystyle {\mathcal {G}}\,\!}$。

(对两个函数 ${\displaystyle f,g:\mathbb {N} \to \mathbb {N} }$，我们说 ${\displaystyle f}$ 控制 ${\displaystyle g}$ 是指，如果对于所有足够大的 ${\displaystyle n}$ ，都有 ${\displaystyle f(n)>g(n)}$。）

• Cichon (1983) 证明

${\displaystyle {\mathcal {G}}(n)=H_{R_{2}^{\omega }(n+1)}(1)-1,}$

其中 ${\displaystyle R_{2}^{\omega }(n)}$ 是将 n 改为以 2 为基底的瓜瓞式表示法，并将所有 2 改为 ω 的结果（即古德斯坦定理的证明中所做的事）。

• Caicedo (2007) 证明如果 ${\displaystyle n=2^{m_{1}}+2^{m_{2}}+\cdots +2^{m_{k}}}$ 且有 ${\displaystyle m_{1}>m_{2}>\cdots >m_{k},}$ then

${\displaystyle {\mathcal {G}}(n)=f_{R_{2}^{\omega }(m_{1})}(f_{R_{2}^{\omega }(m_{2})}(\cdots (f_{R_{2}^{\omega }(m_{k})}(3))\cdots ))-2}$.

一些例子如下：

n			${\displaystyle {\mathcal {G}}(n)}$
1	${\displaystyle 2^{0}}$	${\displaystyle 2-1}$	${\displaystyle H_{\omega }(1)-1}$	${\displaystyle f_{0}(3)-2}$	2
2	${\displaystyle 2^{1}}$	${\displaystyle 2^{1}+1-1}$	${\displaystyle H_{\omega +1}(1)-1}$	${\displaystyle f_{1}(3)-2}$	4
3	${\displaystyle 2^{1}+2^{0}}$	${\displaystyle 2^{2}-1}$	${\displaystyle H_{\omega ^{\omega }}(1)-1}$	${\displaystyle f_{1}(f_{0}(3))-2}$	6
4	${\displaystyle 2^{2}}$	${\displaystyle 2^{2}+1-1}$	${\displaystyle H_{\omega ^{\omega }+1}(1)-1}$	${\displaystyle f_{\omega }(3)-2}$	3·2402653211 − 2 ≈ 6.895080803×10121210694
5	${\displaystyle 2^{2}+2^{0}}$	${\displaystyle 2^{2}+2-1}$	${\displaystyle H_{\omega ^{\omega }+\omega }(1)-1}$	${\displaystyle f_{\omega }(f_{0}(3))-2}$	> A(4,4)>${\displaystyle {10^{10^{10^{19728}}}}}$
6	${\displaystyle 2^{2}+2^{1}}$	${\displaystyle 2^{2}+2+1-1}$	${\displaystyle H_{\omega ^{\omega }+\omega +1}(1)-1}$	${\displaystyle f_{\omega }(f_{1}(3))-2}$	> A(6,6)
7	${\displaystyle 2^{2}+2^{1}+2^{0}}$	${\displaystyle 2^{2+1}-1}$	${\displaystyle H_{\omega ^{\omega +1}}(1)-1}$	${\displaystyle f_{\omega }(f_{1}(f_{0}(3)))-2}$	> A(8,8)
8	${\displaystyle 2^{2+1}}$	${\displaystyle 2^{2+1}+1-1}$	${\displaystyle H_{\omega ^{\omega +1}+1}(1)-1}$	${\displaystyle f_{\omega +1}(3)-2}$	> A3(3,3) = A(A(61, 61), A(61, 61))
${\displaystyle \vdots }$
12	${\displaystyle 2^{2+1}+2^{2}}$	${\displaystyle 2^{2+1}+2^{2}+1-1}$	${\displaystyle H_{\omega ^{\omega +1}+\omega ^{\omega }+1}(1)-1}$	${\displaystyle f_{\omega +1}(f_{\omega }(3))-2}$	> fω+1(64) > 葛立恒数
${\displaystyle \vdots }$
19	${\displaystyle 2^{2^{2}}+2^{1}+2^{0}}$	${\displaystyle 2^{2^{2}}+2^{2}-1}$	${\displaystyle H_{\omega ^{\omega ^{\omega }}+\omega ^{\omega }}(1)-1}$	${\displaystyle f_{\omega ^{\omega }}(f_{1}(f_{0}(3)))-2}$

（对于阿克曼函数和葛立恒数的界限，请参考高成长体系（英语：fast-growing hierarchy#Functions in fast-growing hierarchies）。）

可计算函数的应用

古德斯坦定理可用于构造一个全可计算函数，但皮亚诺算术却不能证明它是全函数。图灵机可以有效地列举古德斯坦序列；所以存在一个特殊的图灵机来计算古德斯坦函数。这个图灵机只需列举出 n 的古德斯坦序列，并在遇到 0 时结束，并传回其长度。因为每个古德斯坦序列终将结束，所以这个函数是完全的。但因为皮亚诺算术不能证明古德斯坦序列会终止，皮亚诺算术不能证明这个图灵机计算了一个完全函数。

另见

• Non-standard model of arithmetic（英语：Non-standard model of arithmetic）
• 高成长体系（英语：Fast-growing hierarchy）
• Paris–Harrington theorem（英语：Paris–Harrington theorem）
• Kanamori–McAloon theorem（英语：Kanamori–McAloon theorem）
• Kruskal's tree theorem

参考资料

1. Kirby, L.; Paris, J. Accessible Independence Results for Peano Arithmetic (PDF). Bulletin of the London Mathematical Society. 1982, 14 (4): 285 [2019-02-20]. CiteSeerX 10.1.1.107.3303 . doi:10.1112/blms/14.4.285. （原始内容存档 (PDF)于2021-01-16）.

Bibliography

• Goodstein, R., On the restricted ordinal theorem, Journal of Symbolic Logic, 1944, 9 (2): 33–41, JSTOR 2268019, doi:10.2307/2268019.
• Cichon, E., A Short Proof of Two Recently Discovered Independence Results Using Recursive Theoretic Methods, Proceedings of the American Mathematical Society, 1983, 87 (4): 704–706, JSTOR 2043364, doi:10.2307/2043364.
• Caicedo, A., Goodstein's function (PDF), Revista Colombiana de Matemáticas, 2007, 41 (2): 381–391 [2019-02-20], （原始内容存档 (PDF)于2011-10-09）.

外部链接

• 埃里克·韦斯坦因. Goodstein Sequence. MathWorld.
• Some elements of a proof that Goodstein's theorem is not a theorem of PA, from an undergraduate thesis by Justin T Miller（页面存档备份，存于互联网档案馆）
• A Classification of non standard models of Peano Arithmetic by Goodstein's theorem - Thesis by Dan Kaplan, Franklan and Marshall College Library
• Definitions of Goodstein sequences in the programming languages Ruby and Haskell, as well as a large-scale plot （页面存档备份，存于互联网档案馆）
• The Hydra game implemented as a Java applet （页面存档备份，存于互联网档案馆）
• Javascript implementation of a variant of the Hydra game （页面存档备份，存于互联网档案馆）
• Goodstein Sequences: The Power of a Detour via Infinity（页面存档备份，存于互联网档案馆） - 对古德斯坦序列和九头蛇游戏有很好的解译。