古德斯坦定理

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

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

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

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

$$m = a_k n^k + a_{k-1} n^{k-1} + \cdots + a_0,$$

其中，每个系数 ai 满足0 ≤ ai k ≠ 0。如在 2 进位中。

$$35 = 32 + 2 + 1 = 2^5 + 2^1 + 2^0.$$

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

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

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

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

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

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

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

$$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｜$2^1 + 1$｜3｜以 2 为基底改写 3。

3｜$3^1 + 1 - 1 = 3^1$｜3｜将 2 改为 3，再减 1。

4｜$4^1 - 1 = 3$｜3｜将 3 改为 4，再减 1。此时已无任何 4 了。

5｜$3 - 1 = 2$｜2｜没有 4 需要改为 5。单纯减 1。

6｜$2 - 1 = 1$｜1｜没有 5 需要改为 6。单纯减 1。

7｜$1 - 1 = 0$｜0｜没有 6 需要改为 7。单纯减 1。

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

瓜瓞式表示法｜值

$2^2$｜4

$3^3 - 1 = 2 \cdot 3^2 + 2 \cdot 3 + 2$｜26

$2 \cdot 4^2 + 2 \cdot 4 + 1$｜41

$2 \cdot 5^2 + 2 \cdot 5$｜60

$2 \cdot 6^2 + 2 \cdot 6 - 1 = 2 \cdot 6^2 + 6 + 5$｜83

$2 \cdot 7^2 + 7 + 4$｜109

$\vdots$｜$\vdots$

$2 \cdot 11^2 + 11$｜253

$2 \cdot 12^2 + 12 - 1 = 2 \cdot 12^2 + 11$｜299

$\vdots$｜$\vdots$

$2 \cdot 24^2 - 1 = 24^2 + 24 \cdot 23 + 23$｜1151

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

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

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

瓜瓞式表示法｜值

$2^{2^2} + 2 + 1$｜19

$3^{3^3} + 3$｜7625597484990

$4^{4^4} + 3$｜$\approx 1.3 \times 10^{154}$

$5^{5^5} + 2$｜$\approx 1.8 \times 10^{2184}$

$6^{6^6} + 1$｜$\approx 2.6 \times 10^{36\,305}$

$7^{7^7}$｜$\approx 3.8 \times 10^{695\,974}$

$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)}$ $+ 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$ $+ 7 \cdot 8^{(8+2)} + 7 \cdot 8^{(8+1)} + 7 \cdot 8^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$｜$\approx 6 \times 10^{15\,151\,335}$

$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)}$ $+ 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$ $+ 7 \cdot 9^{(9+2)} + 7 \cdot 9^{(9+1)}+ 7 \cdot 9^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$｜$\approx 4.3 \times 10^{369\,693\,099}$

$\vdots$｜$\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 = 21 + 20 和 P(3)(1) = f(21 + 20,2) = ω1 + ω0 = ω + 1。序数的加法、乘法和指数都是良好定义的。

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

譬如， $G(4)(1)=2^2$ 乃 $G(4,2)=2\cdot 3^2 + 2\cdot 3+2$，所以 $f(2^2,2)=\omega^\omega$ 和 $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 为基底的表示法。所以如 $\omega^\omega-1$ 等的表示式，既不会是无意义的也非等同 $\omega^\omega$。

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

虽然这个证明相当简单，但柯比-柏丽斯定理 （证明了在皮亚诺算术中不会有古德斯坦定理）则是非常专门且相当困难。它使用了皮亚诺算术中的算术非标准模型。

## 扩展的古德斯坦定理

假设古德斯坦定理的定义中的“将b改为b+1”的这个动作，将它改为 b+2，那么这个序列会终止吗？

更一般地，让 b1, b2, b3, … 为任意整数列，然后让第 n+1 项的 G(m)(n+1) 变成：

将 G(m)(n) 改为 bn 的表示法，将 bn 改为 bn+1 再减 1。

我们仍可断言这个序列仍会终止。

扩展的证明则将 P(m)(n) = f(G(m)(n), n) 定义为如下：

将 G(m)(n) 改为 bn 表示法，再将所有的 bn 改为第一个无限序数 ω。

古德斯坦序列中，从G(m)(n)到G(m)(n+1)的换底运算并不会改变 f 的值。

譬如，如果 bn = 4 且 bn+1 = 9。

则$f(3 \cdot 4^{4^4} + 4,4) = 3 \omega^{\omega^\omega} + \omega= f(3 \cdot 9^{9^9} + 9,9)$。因此，序数 $f(3 \cdot 4^{4^4} + 4,4)$ 是严格大于序数 $f((3 \cdot 9^{9^9} + 9 )-1,9)$。

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

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

- Kirby and Paris (1982) 证明

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

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

- Cichon (1983) 证明

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

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

- Caicedo (2007) 证明如果 $n = 2^{m_1} + 2^{m_2} + \cdots + 2^{m_k}$ 且有 $m_1 > m_2 > \cdots > m_k,$ then

$\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｜$\mathcal{G}(n)$

1｜$2^0$｜$2 - 1$｜$H_\omega(1) - 1$｜$f_0(3) - 2$｜2

2｜$2^1$｜$2^1 + 1 - 1$｜$H_{\omega + 1}(1) - 1$｜$f_1(3) - 2$｜4

3｜$2^1 + 2^0$｜$2^2 - 1$｜$H_{\omega^\omega}(1) - 1$｜$f_1(f_0(3)) - 2$｜6

4｜$2^2$｜$2^2 + 1 - 1$｜$H_{\omega^\omega + 1}(1) - 1$｜$f_\omega(3) - 2$｜3·2402653211 − 2 ≈ 6.895080803×10121210694

5｜$2^2 + 2^0$｜$2^2 + 2 - 1$｜$H_{\omega^\omega + \omega}(1) - 1$｜$f_\omega(f_0(3)) - 2$｜> A(4,4)>${10^{10^{10^{19728}}}}$

6｜$2^2 + 2^1$｜$2^2 + 2 + 1 - 1$｜$H_{\omega^\omega + \omega + 1}(1) - 1$｜$f_\omega(f_1(3)) - 2$｜> A(6,6)

7｜$2^2 + 2^1 + 2^0$｜$2^{2 + 1} - 1$｜$H_{\omega^{\omega + 1}}(1) - 1$｜$f_\omega(f_1(f_0(3))) - 2$｜> A(8,8)

8｜$2^{2 + 1}$｜$2^{2 + 1} + 1 - 1$｜$H_{\omega^{\omega + 1} + 1}(1) - 1$｜$f_{\omega + 1}(3) - 2$｜> A3(3,3) = A(A(61, 61), A(61, 61))

$$\vdots$$

12｜$2^{2 + 1} + 2^2$｜$2^{2 + 1} + 2^2 + 1 - 1$｜$H_{\omega^{\omega + 1} + \omega^\omega + 1}(1) - 1$｜$f_{\omega + 1}(f_\omega(3)) - 2$｜> fω+1(64) > 葛立恒数

$$\vdots$$

19｜$2^{2^2} + 2^1 + 2^0$｜$2^{2^2} + 2^2 - 1$｜$H_{\omega^{\omega^\omega} + \omega^\omega}(1) - 1$｜$f_{\omega^\omega}(f_1(f_0(3))) - 2$

（对于阿克曼函数和葛立恒数的界限，请参考。）

## 可计算函数的应用

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

## 另见

- Kruskal's tree theorem

## 外部链接

- GoodsteinSequence
- 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 - 对古德斯坦序列和九头蛇游戏有很好的解译。