古德斯坦定理 是數理邏輯 中的一個關於自然數 的敘述,是在 1944 年由魯本·古德斯坦所證明。其主要是在說明「古德斯坦序列」最終會結束於 0 。柯比和柏麗斯[1] 證明它在皮亞諾算術 中是不可證明的(但它可以在一個更強的系統如二階算術 中被證明)。這是繼哥德爾不完備定理 構造的命題( C o n s ( P A ) {\displaystyle {\mathsf {Cons(PA)}}} )和 1943 年格哈德·根岑 直接證明皮亞諾算術中 ε0 -induction 不可被證明之後,第三個(對自然數為真的)命題被證明在皮亞諾算術中不可證明。之後的例子是柏麗斯–哈靈頓定理。
勞倫斯·柯比和傑夫·柏麗斯介紹了一個圖論中的九頭蛇 遊戲 ,其行為類似古德斯坦序列:「九頭蛇 」是一棵有根的樹,而序列每一步是砍掉它的一顆頭(即樹的分支),然後九頭蛇則對應地會依據某些規則來增加有限數量的頭。柯比和柏麗斯則證明,不管赫拉克勒斯 使用何種策略來砍頭,九頭蛇最終會被斬殺(儘管這個過程可能會非常漫長)。如古德斯坦序列,柯比和柏麗斯證明其在皮亞諾算術中是不可證明的[1] 。
以n 為基底的瓜瓞式基底表示法 编辑
古德斯坦序列是由一種「以n 為基底的瓜瓞式表示法」的概念來定義的。這個表示法與平常的 n 進位制 表示法很像,但一般的進位表示法無法達到古德斯坦定理的目的。在原本的 n 進位表示法,n 是一個大於 1 的自然數,而任一個自然數 m 則被改寫為一些由 n 的冪次的乘積的相加之和:
m = a k n k + a k − 1 n k − 1 + ⋯ + a 0 , {\displaystyle 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 . {\displaystyle 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 ⋅ 3 2 + 3 0 . {\displaystyle 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 , {\displaystyle 35=2^{2^{2}+1}+2+1,} (5 = 22 + 1. ) 。類似的,以3 為基底的瓜瓞式表示法的 100 為
100 = 3 3 + 1 + 2 ⋅ 3 2 + 1. {\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 2 1 + 1 {\displaystyle 2^{1}+1} 3 以 2 為基底改寫 3。 3 3 1 + 1 − 1 = 3 1 {\displaystyle 3^{1}+1-1=3^{1}} 3 將 2 改為 3,再減 1。 4 4 1 − 1 = 3 {\displaystyle 4^{1}-1=3} 3 將 3 改為 4,再減 1。此時已無任何 4 了。 5 3 − 1 = 2 {\displaystyle 3-1=2} 2 沒有 4 需要改為 5。單純減 1。 6 2 − 1 = 1 {\displaystyle 2-1=1} 1 沒有 5 需要改為 6。單純減 1。 7 1 − 1 = 0 {\displaystyle 1-1=0} 0 沒有 6 需要改為 7。單純減 1。
之後的古德斯坦序列則成長到很龐大的數字,如 G (4) A056193 開始如下:
瓜瓞式表示法 值 2 2 {\displaystyle 2^{2}} 4 3 3 − 1 = 2 ⋅ 3 2 + 2 ⋅ 3 + 2 {\displaystyle 3^{3}-1=2\cdot 3^{2}+2\cdot 3+2} 26 2 ⋅ 4 2 + 2 ⋅ 4 + 1 {\displaystyle 2\cdot 4^{2}+2\cdot 4+1} 41 2 ⋅ 5 2 + 2 ⋅ 5 {\displaystyle 2\cdot 5^{2}+2\cdot 5} 60 2 ⋅ 6 2 + 2 ⋅ 6 − 1 = 2 ⋅ 6 2 + 6 + 5 {\displaystyle 2\cdot 6^{2}+2\cdot 6-1=2\cdot 6^{2}+6+5} 83 2 ⋅ 7 2 + 7 + 4 {\displaystyle 2\cdot 7^{2}+7+4} 109 ⋮ {\displaystyle \vdots } ⋮ {\displaystyle \vdots } 2 ⋅ 11 2 + 11 {\displaystyle 2\cdot 11^{2}+11} 253 2 ⋅ 12 2 + 12 − 1 = 2 ⋅ 12 2 + 11 {\displaystyle 2\cdot 12^{2}+12-1=2\cdot 12^{2}+11} 299 ⋮ {\displaystyle \vdots } ⋮ {\displaystyle \vdots } 2 ⋅ 24 2 − 1 = 24 2 + 24 ⋅ 23 + 23 {\displaystyle 2\cdot 24^{2}-1=24^{2}+24\cdot 23+23} 1151
G (4) 會一直遞增,直到基底為 3 ⋅ 2 402 653 209 {\displaystyle 3\cdot 2^{402\,653\,209}} 時,會達到最大值 3 ⋅ 2 402 653 210 − 1 {\displaystyle 3\cdot 2^{402\,653\,210}-1} ,並在這裡停留 3 ⋅ 2 402 653 209 {\displaystyle 3\cdot 2^{402\,653\,209}} 步後,然後開始遞減。
這個序列到達 0 時,當時的基底為 3 ⋅ 2 402 653 211 − 1 {\displaystyle 3\cdot 2^{402\,653\,211}-1} 。(有趣的是,這是個胡道爾數 : 3 ⋅ 2 402 653 211 − 1 = 402 653 184 ⋅ 2 402 653 184 − 1 {\displaystyle 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 ) {\displaystyle f(G(m)(n),n+1)>f(G(m)(n+1),n+2)} 。在古德斯坦序列中,將 G (m )(n ) 改換基底後,將其記為 G ′ ( m ) ( n ) {\displaystyle G'(m)(n)} 。明顯的, f ( G ( m ) ( n ) , n + 1 ) = f ( G ′ ( m ) ( n ) , n + 2 ) {\displaystyle f(G(m)(n),n+1)=f(G'(m)(n),n+2)} ,現在我們套用 -1 運算後,因為 G ′ ( m ) ( n ) = G ( m ) ( n + 1 ) + 1 {\displaystyle G'(m)(n)=G(m)(n+1)+1} ,所以 f ( G ′ ( m ) ( n ) , n + 2 ) > f ( G ( m ) ( n + 1 ) , n + 2 ) {\displaystyle f(G'(m)(n),n+2)>f(G(m)(n+1),n+2)} 。
譬如, G ( 4 ) ( 1 ) = 2 2 {\displaystyle G(4)(1)=2^{2}} 乃 G ( 4 , 2 ) = 2 ⋅ 3 2 + 2 ⋅ 3 + 2 {\displaystyle G(4,2)=2\cdot 3^{2}+2\cdot 3+2} ,所以 f ( 2 2 , 2 ) = ω ω {\displaystyle f(2^{2},2)=\omega ^{\omega }} 和 f ( 2 ⋅ 3 2 + 2 ⋅ 3 + 2 , 3 ) = 2 ω 2 + 2 ω + 2 {\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 為基底的表示法。所以如 ω ω − 1 {\displaystyle \omega ^{\omega }-1} 等的表示式,既不會是無意義的也非等同 ω ω {\displaystyle \omega ^{\omega }} 。
P (m ) 是嚴格遞減的。而標準排序運算元 < 在序數上是良基关系 ,一個無窮的嚴格遞減序列是不可能存在的。換句話說,每個嚴格遞減的序數序列會停止(不可能無限)。但P (m )(n ) 是由 G (m )(n ) 計算出來的。 G (m )(n ) 也必然停止,這意味著它會達到 0 。
雖然這個證明相當簡單,但柯比-柏麗斯定理[1] (證明了在皮亞諾算術中不會有古德斯坦定理)則是非常專門且相當困難。它使用了皮亞諾算術中的可數非標準模型 。
擴展的古德斯坦定理 编辑
假設古德斯坦定理的定義中的「將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 ⋅ 4 4 4 + 4 , 4 ) = 3 ω ω ω + ω = f ( 3 ⋅ 9 9 9 + 9 , 9 ) {\displaystyle f(3\cdot 4^{4^{4}}+4,4)=3\omega ^{\omega ^{\omega }}+\omega =f(3\cdot 9^{9^{9}}+9,9)} 。因此,序數 f ( 3 ⋅ 4 4 4 + 4 , 4 ) {\displaystyle f(3\cdot 4^{4^{4}}+4,4)} 是嚴格大於序數 f ( ( 3 ⋅ 9 9 9 + 9 ) − 1 , 9 ) {\displaystyle f((3\cdot 9^{9^{9}}+9)-1,9)} 。
起始點為變量的序列長度函數 编辑
古德斯坦函數 G ( n ) {\displaystyle {\mathcal {G}}(n)} 定義為由 n 為起始值的古德斯坦序列的長度。因為古德斯坦序列會終止,所以這是一個完全函數 。要測定 G {\displaystyle {\mathcal {G}}} 的快速成長,可由多種藉由標準基於序數體系中的函數,如Hardy hierarchy 中的 H α {\displaystyle H_{\alpha }} 函數,和 Löb and Wainer 的 高成長體系 f α {\displaystyle f_{\alpha }} 函數。
Kirby and Paris (1982) 證明 G {\displaystyle {\mathcal {G}}} 有著和 H ϵ 0 {\displaystyle H_{\epsilon _{0}}} 近似的成長速度(等同於 f ϵ 0 {\displaystyle f_{\epsilon _{0}}} ); 更精確地說,對每個 α < ϵ 0 {\displaystyle \alpha <\epsilon _{0}} , G {\displaystyle {\mathcal {G}}} 控制 H α {\displaystyle H_{\alpha }} ,且 H ϵ 0 {\displaystyle H_{\epsilon _{0}}} 控制 G {\displaystyle {\mathcal {G}}\,\!} 。(對兩個函數 f , g : N → N {\displaystyle f,g:\mathbb {N} \to \mathbb {N} } ,我們說 f {\displaystyle f} 控制 g {\displaystyle g} 是指,如果對於所有足夠大的 n {\displaystyle n} ,都有 f ( n ) > g ( n ) {\displaystyle f(n)>g(n)} 。) G ( n ) = H R 2 ω ( n + 1 ) ( 1 ) − 1 , {\displaystyle {\mathcal {G}}(n)=H_{R_{2}^{\omega }(n+1)}(1)-1,} 其中 R 2 ω ( n ) {\displaystyle R_{2}^{\omega }(n)} 是將 n 改為以 2 為基底的瓜瓞式表示法,並將所有 2 改為 ω 的結果(即古德斯坦定理的證明中所做的事)。 Caicedo (2007) 證明如果 n = 2 m 1 + 2 m 2 + ⋯ + 2 m k {\displaystyle n=2^{m_{1}}+2^{m_{2}}+\cdots +2^{m_{k}}} 且有 m 1 > m 2 > ⋯ > m k , {\displaystyle m_{1}>m_{2}>\cdots >m_{k},} then G ( n ) = f R 2 ω ( m 1 ) ( f R 2 ω ( m 2 ) ( ⋯ ( f R 2 ω ( m k ) ( 3 ) ) ⋯ ) ) − 2 {\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 G ( n ) {\displaystyle {\mathcal {G}}(n)} 1 2 0 {\displaystyle 2^{0}} 2 − 1 {\displaystyle 2-1} H ω ( 1 ) − 1 {\displaystyle H_{\omega }(1)-1} f 0 ( 3 ) − 2 {\displaystyle f_{0}(3)-2} 2 2 2 1 {\displaystyle 2^{1}} 2 1 + 1 − 1 {\displaystyle 2^{1}+1-1} H ω + 1 ( 1 ) − 1 {\displaystyle H_{\omega +1}(1)-1} f 1 ( 3 ) − 2 {\displaystyle f_{1}(3)-2} 4 3 2 1 + 2 0 {\displaystyle 2^{1}+2^{0}} 2 2 − 1 {\displaystyle 2^{2}-1} H ω ω ( 1 ) − 1 {\displaystyle H_{\omega ^{\omega }}(1)-1} f 1 ( f 0 ( 3 ) ) − 2 {\displaystyle f_{1}(f_{0}(3))-2} 6 4 2 2 {\displaystyle 2^{2}} 2 2 + 1 − 1 {\displaystyle 2^{2}+1-1} H ω ω + 1 ( 1 ) − 1 {\displaystyle H_{\omega ^{\omega }+1}(1)-1} f ω ( 3 ) − 2 {\displaystyle f_{\omega }(3)-2} 3·2402653211 − 2 ≈ 6.895080803×10121210694 5 2 2 + 2 0 {\displaystyle 2^{2}+2^{0}} 2 2 + 2 − 1 {\displaystyle 2^{2}+2-1} H ω ω + ω ( 1 ) − 1 {\displaystyle H_{\omega ^{\omega }+\omega }(1)-1} f ω ( f 0 ( 3 ) ) − 2 {\displaystyle f_{\omega }(f_{0}(3))-2} > A (4,4)> 10 10 10 19728 {\displaystyle {10^{10^{10^{19728}}}}} 6 2 2 + 2 1 {\displaystyle 2^{2}+2^{1}} 2 2 + 2 + 1 − 1 {\displaystyle 2^{2}+2+1-1} H ω ω + ω + 1 ( 1 ) − 1 {\displaystyle H_{\omega ^{\omega }+\omega +1}(1)-1} f ω ( f 1 ( 3 ) ) − 2 {\displaystyle f_{\omega }(f_{1}(3))-2} > A (6,6) 7 2 2 + 2 1 + 2 0 {\displaystyle 2^{2}+2^{1}+2^{0}} 2 2 + 1 − 1 {\displaystyle 2^{2+1}-1} H ω ω + 1 ( 1 ) − 1 {\displaystyle H_{\omega ^{\omega +1}}(1)-1} f ω ( f 1 ( f 0 ( 3 ) ) ) − 2 {\displaystyle f_{\omega }(f_{1}(f_{0}(3)))-2} > A (8,8) 8 2 2 + 1 {\displaystyle 2^{2+1}} 2 2 + 1 + 1 − 1 {\displaystyle 2^{2+1}+1-1} H ω ω + 1 + 1 ( 1 ) − 1 {\displaystyle H_{\omega ^{\omega +1}+1}(1)-1} f ω + 1 ( 3 ) − 2 {\displaystyle f_{\omega +1}(3)-2} > A 3 (3,3) = A (A (61, 61), A (61, 61)) ⋮ {\displaystyle \vdots } 12 2 2 + 1 + 2 2 {\displaystyle 2^{2+1}+2^{2}} 2 2 + 1 + 2 2 + 1 − 1 {\displaystyle 2^{2+1}+2^{2}+1-1} H ω ω + 1 + ω ω + 1 ( 1 ) − 1 {\displaystyle H_{\omega ^{\omega +1}+\omega ^{\omega }+1}(1)-1} f ω + 1 ( f ω ( 3 ) ) − 2 {\displaystyle f_{\omega +1}(f_{\omega }(3))-2} > f ω+1 (64) > 葛立恆數 ⋮ {\displaystyle \vdots } 19 2 2 2 + 2 1 + 2 0 {\displaystyle 2^{2^{2}}+2^{1}+2^{0}} 2 2 2 + 2 2 − 1 {\displaystyle 2^{2^{2}}+2^{2}-1} H ω ω ω + ω ω ( 1 ) − 1 {\displaystyle H_{\omega ^{\omega ^{\omega }}+\omega ^{\omega }}(1)-1} f ω ω ( f 1 ( f 0 ( 3 ) ) ) − 2 {\displaystyle f_{\omega ^{\omega }}(f_{1}(f_{0}(3)))-2}
(對於阿克曼函數 和葛立恆數 的界限,請參考高成長體系 。)
可計算函數的應用 编辑
古德斯坦定理可用於構造一個全可计算函数 ,但皮亞諾算術卻不能證明它是全函數。图灵机 可以有效地列舉古德斯坦序列;所以存在一個特殊的圖靈機來計算古德斯坦函數。這個圖靈機只需列舉出 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) .外部連結 编辑