古德斯坦定理是數理邏輯中的一個關於自然數的敘述,是在 1944 年由魯本·古德斯坦所證明。其主要是在說明「古德斯坦序列」最終會結束於 0 。柯比和柏麗斯[1] 證明它在皮亞諾算術中是不可證明的(但它可以在一個更強的系統如二階算術中被證明)。這是繼哥德爾不完備定理構造的命題(
)和 1943 年格哈德·根岑直接證明皮亞諾算術中 ε0-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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9f92833f63c5c1a225a0ce7ba5f7b78de3b0573)
其中,每個系數 ai 滿足0 ≤ ai < n,且ak ≠ 0。如在 2 進位中,
![{\displaystyle 35=32+2+1=2^{5}+2^{1}+2^{0}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/636de9306e9a2756ce3b786b52957948fbd15931)
所以, 35 的二進位是 100011(25 + 2 + 1)。類似地,由 3 進位表示的 100 是 10201:
![{\displaystyle 100=81+18+1=3^{4}+2\cdot 3^{2}+3^{0}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9455987bbea6282db05abdfc682acf4f7150c6a0)
然而需注意的是,這些指數仍非是基於 n 的表述法。如上述表示式中的 25 和 34 。
將一個 n 進位表示轉換為瓜瓞式n基底表示法,首先要將每個指數改為 n 基底表示法。然後改寫指數中的指數,持續這個動作直到每個數都被改為以 n 為基底表示法。
譬如, 2 進位的 35 為 100011 ,將它改寫成以 n 為基底的瓜瓞式表示法為:
![{\displaystyle 35=2^{2^{2}+1}+2+1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d45bb27e6a8ade53205d93ad929128f613a91419)
(5 = 22 + 1.) 。類似的,以3為基底的瓜瓞式表示法的 100 為
![{\displaystyle 100=3^{3+1}+2\cdot 3^{2}+1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac894ad333c59d2bf927ea9e58ad20be047badd2)
古德斯坦序列
古德斯坦序列 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e27ce9b5b61362e577679f593180e2f8fdf72a22) |
3 |
以 2 為基底改寫 3。
|
3 |
![{\displaystyle 3^{1}+1-1=3^{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3bd6e3985e40469b1dffed112f7e7de5875bcf2a) |
3 |
將 2 改為 3,再減 1。
|
4 |
![{\displaystyle 4^{1}-1=3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a45cdb0bb670dd3b557cedb03a69ee5239a27b25) |
3 |
將 3 改為 4,再減 1。此時已無任何 4 了。
|
5 |
![{\displaystyle 3-1=2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09bdf1ca439ba3f857af8da87f0a53a28648e2c8) |
2 |
沒有 4 需要改為 5。單純減 1。
|
6 |
![{\displaystyle 2-1=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e790a95dd451fdb4c8e2f74f60823807ca50f2b) |
1 |
沒有 5 需要改為 6。單純減 1。
|
7 |
![{\displaystyle 1-1=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6e3a458263e924d197c37a58beae62ade425ddf) |
0 |
沒有 6 需要改為 7。單純減 1。
|
之後的古德斯坦序列則成長到很龐大的數字,如 G(4) A056193 開始如下:
瓜瓞式表示法 |
值
|
![{\displaystyle 2^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/efd7711cd907a2d46557a410fb67fc0d84c52ba3) |
4
|
![{\displaystyle 3^{3}-1=2\cdot 3^{2}+2\cdot 3+2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9ddc5a170223c0d10302fc268afa46bba9e8a32) |
26
|
![{\displaystyle 2\cdot 4^{2}+2\cdot 4+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c368f1b4655bd12e829bd7fec209d1c36b957097) |
41
|
![{\displaystyle 2\cdot 5^{2}+2\cdot 5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f83dd2214160f498cd27305fe8585a52411e8554) |
60
|
![{\displaystyle 2\cdot 6^{2}+2\cdot 6-1=2\cdot 6^{2}+6+5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c79ebf7fc21a9ff62aa2150f2eeec5913d96ece) |
83
|
![{\displaystyle 2\cdot 7^{2}+7+4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ea481d05c5978de457104069208d8da24a8e6bb) |
109
|
![{\displaystyle \vdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8039d9feb6596ae092e5305108722975060c083) |
|
![{\displaystyle 2\cdot 11^{2}+11}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99a7c16646f297034ce8b982f1e13bd8c3b095c7) |
253
|
![{\displaystyle 2\cdot 12^{2}+12-1=2\cdot 12^{2}+11}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50f6cac23558e2acd65c09d28f257b04e7bb39f9) |
299
|
![{\displaystyle \vdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8039d9feb6596ae092e5305108722975060c083) |
|
![{\displaystyle 2\cdot 24^{2}-1=24^{2}+24\cdot 23+23}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50968eeaa463b70fba3c6036929bb45a559f878d) |
1151
|
G(4) 會一直遞增,直到基底為
時,會達到最大值
,並在這裏停留
步後,然後開始遞減。
這個序列到達 0 時,當時的基底為
。(有趣的是,這是個胡道爾數:
。而且,對於所有起始值大於 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 。序數的加法、乘法和指數都是良好定義的。
我們可聲明
。在古德斯坦序列中,將 G(m)(n) 改換基底後,將其記為
。明顯的,
,現在我們套用 -1 運算後,因為
,所以
。
譬如,
乃
,所以
和
是嚴格變小。需注意的是,若要計算 f(G(m)(n),n+1) ,我們要先將 G(m)(n) 改為以 n+1 為基底的表示法。所以如
等的表示式,既不會是無意義的也非等同
。
P(m) 是嚴格遞減的。而標準排序運算元 < 在序數上是良基關係,一個無窮的嚴格遞減序列是不可能存在的。換句話說,每個嚴格遞減的序數序列會停止(不可能無限)。但P(m)(n) 是由 G(m)(n) 計算出來的。 G(m)(n) 也必然停止,這意味着它會達到 0 。
雖然這個證明相當簡單,但柯比-柏麗斯定理[1] (證明了在皮亞諾算術中不會有古德斯坦定理)則是非常專門且相當困難。它使用了皮亞諾算術中的可數非標準模型。
擴展的古德斯坦定理
假設古德斯坦定理的定義中的「將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,
則
。因此,序數
是
嚴格大於序數
。
起始點為變量的序列長度函數
古德斯坦函數
定義為由 n 為起始值的古德斯坦序列的長度。因為古德斯坦序列會終止,所以這是一個完全函數。要測定
的快速成長,可由多種藉由標準基於序數體系中的函數,如Hardy hierarchy 中的
函數,和 Löb and Wainer 的 高成長體系
函數。
- Kirby and Paris (1982) 證明
有着和
近似的成長速度(等同於
); 更精確地說,對每個
,
控制
,且
控制
。
- (對兩個函數
,我們說
控制
是指,如果對於所有足夠大的
,都有
。)
![{\displaystyle {\mathcal {G}}(n)=H_{R_{2}^{\omega }(n+1)}(1)-1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fbcc1d05c5be45338ede84ef18f587f0fc75daf)
- 其中
是將 n 改為以 2 為基底的瓜瓞式表示法,並將所有 2 改為 ω 的結果(即古德斯坦定理的證明中所做的事)。
- Caicedo (2007) 證明如果
且有
then
.
一些例子如下:
n
|
|
1
|
|
|
|
|
2
|
2
|
|
|
|
|
4
|
3
|
|
|
|
|
6
|
4
|
|
|
|
|
3·2402653211 − 2 ≈ 6.895080803×10121210694
|
5
|
|
|
|
|
> A(4,4)>
|
6
|
|
|
|
|
> A(6,6)
|
7
|
|
|
|
|
> A(8,8)
|
8
|
|
|
|
|
> A3(3,3) = A(A(61, 61), A(61, 61))
|
|
12
|
|
|
|
|
> fω+1(64) > 葛立恆數
|
|
19
|
|
|
|
|
|
(對於阿克曼函數和葛立恆數的界限,請參考高成長體系。)
可計算函數的應用
古德斯坦定理可用於構造一個全可計算函數,但皮亞諾算術卻不能證明它是全函數。圖靈機可以有效地列舉古德斯坦序列;所以存在一個特殊的圖靈機來計算古德斯坦函數。這個圖靈機只需列舉出 n 的古德斯坦序列,並在遇到 0 時結束,並傳回其長度。因為每個古德斯坦序列終將結束,所以這個函數是完全的。但因為皮亞諾算術不能證明古德斯坦序列會終止,皮亞諾算術不能證明這個圖靈機計算了一個完全函數。
另見
參考資料
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) .
外部連結