古德斯坦定理

**古德斯坦定理**是數理邏輯中的一個關於自然數的敘述，是在 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_ < _n_，且 _ak_ ≠ 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 步：

之後的古德斯坦序列則成長到很龐大的數字，如 _G_(4) A056193 開始如下：

_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) 成長更迅速，其開頭幾項如下：

儘管其成長如此迅速，古德斯坦定理說明了無論起始值為何，**每個古德斯坦最終會終止於 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，那麼這個序列會終止嗎？
更一般地，讓 _b_1, _b_2, _b_3, … 為任意整數列，然後讓第 _n_+1 項的 _G_(_m_)(_n_+1) 變成：
將 _G_(_m_)(_n_) 改為 _bn_ 的表示法，將 _bn_ 改為 _b_n+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 且 _b_n+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}}$ 的快速成長，可由多種藉由標準基於序數體系中的函數，如 Hardy hierarchy 中的 $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_ 的古德斯坦序列，並在遇到 0 時結束，並傳回其長度。因為每個古德斯坦序列終將結束，所以這個函數是完全的。但因為皮亞諾算術不能證明古德斯坦序列會終止，皮亞諾算術不能證明這個圖靈機計算了一個完全函數。

## 另見

* Non-standard model of arithmetic
* 高成長體系
* Paris–Harrington theorem
* Kanamori–McAloon theorem
* Kruskal's tree theorem

## 參考資料

## 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（頁面存檔備份，存於網際網路檔案館） - 對古德斯坦序列和九頭蛇遊戲有很好的解譯。