古德斯坦定理

定理

古德斯坦定理數理邏輯中的一個關於自然數的敘述,是在 1944 年由魯本·古德斯坦所證明。其主要是在說明「古德斯坦序列」最終會結束於 0 。柯比和柏麗斯[1] 證明它在皮亞諾算術中是不可證明的(但它可以在一個更強的系統如二階算術中被證明)。這是繼哥德爾不完備定理構造的命題()和 1943 年格哈德·根岑直接證明皮亞諾算術中 ε0-induction 不可被證明之後,第三個(對自然數為真的)命題被證明在皮亞諾算術中不可證明。之後的例子是柏麗斯–哈靈頓定理

勞倫斯·柯比和傑夫·柏麗斯介紹了一個圖論中的九頭蛇遊戲,其行為類似古德斯坦序列:「九頭蛇」是一棵有根的樹,而序列每一步是砍掉它的一顆頭(即樹的分支),然後九頭蛇則對應地會依據某些規則來增加有限數量的頭。柯比和柏麗斯則證明,不管赫拉克勒斯使用何種策略來砍頭,九頭蛇最終會被斬殺(儘管這個過程可能會非常漫長)。如古德斯坦序列,柯比和柏麗斯證明其在皮亞諾算術中是不可證明的[1]

n為基底的瓜瓞式基底表示法

古德斯坦序列是由一種「以n為基底的瓜瓞式表示法」的概念來定義的。這個表示法與平常的 n 進位制表示法很像,但一般的進位表示法無法達到古德斯坦定理的目的。在原本的 n 進位表示法,n 是一個大於 1 的自然數,而任一個自然數 m 則被改寫為一些由 n 的冪次的乘積的相加之和:

 

其中,每個係數 ai 滿足0 ≤ ai < n,且ak ≠ 0。如在 2 進位中,

 

所以, 35 的二進位是 100011(25 + 2 + 1)。類似地,由 3 進位表示的 100 是 10201:

 

然而需注意的是,這些指數仍非是基於 n 的表述法。如上述表示式中的 25 和 34

將一個 n 進位表示轉換為瓜瓞式n基底表示法,首先要將每個指數改為 n 基底表示法。然後改寫指數中的指數,持續這個動作直到每個數都被改為以 n 為基底表示法。

譬如, 2 進位的 35 為 100011 ,將它改寫成以 n 為基底的瓜瓞式表示法為:

 

(5 = 22 + 1.) 。類似的,以3為基底的瓜瓞式表示法的 100 為

 

古德斯坦序列

古德斯坦序列 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   3 以 2 為基底改寫 3。
3   3 將 2 改為 3,再減 1。
4   3 將 3 改為 4,再減 1。此時已無任何 4 了。
5   2 沒有 4 需要改為 5。單純減 1。
6   1 沒有 5 需要改為 6。單純減 1。
7   0 沒有 6 需要改為 7。單純減 1。

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

瓜瓞式表示法
  4
  26
  41
  60
  83
  109
   
  253
  299
   
  1151

G(4) 會一直遞增,直到基底為   時,會達到最大值   ,並在這裡停留   步後,然後開始遞減。

這個序列到達 0 時,當時的基底為  。(有趣的是,這是個胡道爾數 。而且,對於所有起始值大於 4 的數,都是如此。[來源請求]

不過,G(4) 仍無法很好地展示古德斯坦序列的項數是如何快速地成長。G(19) 成長更迅速,其開頭幾項如下:

瓜瓞式表示法
  19
  7625597484990
   
   
   
   

         

 

         

 
   

儘管其成長如此迅速,古德斯坦定理說明了無論起始值為何,每個古德斯坦最終會終止於 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 + 20P(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] (證明了在皮亞諾算術中不會有古德斯坦定理)則是非常專門且相當困難。它使用了皮亞諾算術中的可數非標準模型英語Non-standard model of arithmetic

擴展的古德斯坦定理

假設古德斯坦定理的定義中的「將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 = 4bn+1 = 9, 則  。因此,序數   是 嚴格大於序數  

起始點為變量的序列長度函數

古德斯坦函數   定義為由 n 為起始值的古德斯坦序列的長度。因為古德斯坦序列會終止,所以這是一個完全函數。要測定   的快速成長,可由多種藉由標準基於序數體系中的函數,如Hardy hierarchy英語Hardy hierarchy 中的   函數,和 Löb and Wainer 的 高成長體系英語fast-growing hierarchy   函數。

  • Kirby and Paris (1982) 證明
  有著和   近似的成長速度(等同於  ); 更精確地說,對每個    控制  ,且   控制  
(對兩個函數  ,我們說   控制   是指,如果對於所有足夠大的   ,都有  。)
  • Cichon (1983) 證明
 
其中   是將 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        

(對於阿克曼函數葛立恆數的界限,請參考高成長體系英語fast-growing hierarchy#Functions in fast-growing hierarchies。)

可計算函數的應用

古德斯坦定理可用於構造一個全可計算函數,但皮亞諾算術卻不能證明它是全函數。圖靈機可以有效地列舉古德斯坦序列;所以存在一個特殊的圖靈機來計算古德斯坦函數。這個圖靈機只需列舉出 n 的古德斯坦序列,並在遇到 0 時結束,並傳回其長度。因為每個古德斯坦序列終將結束,所以這個函數是完全的。但因為皮亞諾算術不能證明古德斯坦序列會終止,皮亞諾算術不能證明這個圖靈機計算了一個完全函數。

另見

參考資料

  1. ^ 1.0 1.1 1.2 Kirby, L.; Paris, J. Accessible Independence Results for Peano Arithmetic (PDF). Bulletin of the London Mathematical Society. 1982, 14 (4): 285 [2019-02-20]. CiteSeerX 10.1.1.107.3303 . doi:10.1112/blms/14.4.285. (原始內容存檔 (PDF)於2021-01-16). 

Bibliography

外部連結