古德斯坦定理

古德斯坦定理（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 - 對古德斯坦序列和九頭蛇遊戲有很好的解譯。