古德斯坦定理

古德斯坦定理是數理邏輯中的一個關於自然數的敘述，是在 1944 年由魯本·古德斯坦所證明。其主要是在說明「古德斯坦序列」最終會結束於 0 。柯比和柏麗斯 證明它在皮亞諾算術中是不可證明的命題被證明在皮亞諾算術中不可證明。之後的例子是柏麗斯–哈靈頓定理。勞倫斯·柯比和傑夫·柏麗斯介紹了一個圖論中的九頭蛇遊戲，其行為類似古德斯坦序列：「九頭蛇」是一棵有根的樹，而序列每一步是砍掉它的一顆頭。如古德斯坦序列，柯比和柏麗斯證明其在皮亞諾算術中是不可證明的。以"n"為基底的瓜瓞式基底表示法.古德斯坦序列是由一種「以"n"為基底的瓜瓞式表示法」的概念來定義的。這個表示法與平常的 "n" 進位製表示法很像，但一般的進位表示法無法達到古德斯坦定理的目的。在原本的 "n" 進位表示法，"n" 是一個大於 1 的自然數，而任一個自然數 "m" 則被改寫為一些由 "n" 的冪次的乘積的相加之和：formula_2其中，每個係數 "ai" 滿足0 ≤ "ai" &lt; "n"，且"ak" ≠ 0。如在 2 進位中，formula_3所以， 35 的二進位是 100011。類似地，由 3 進位表示的 100 是 10201:formula_4然而需注意的是，這些指數仍非是基於 "n" 的表述法。如上述表示式中的 25 和 34 。將一個 "n" 進位表示轉換為瓜瓞式"n"基底表示法，首先要將每個指數改為 "n" 基底表示法。然後改寫指數中的指數，持續這個動作直到每個數都被改為以 "n" 為基底表示法。譬如， 2 進位的 35 為 100011 ，將它改寫成以 "n" 為基底的瓜瓞式表示法為：formula_5(5 = 22 + 1.) 。類似的，以"3"為基底的瓜瓞式表示法的 100 為formula_6古德斯坦序列.古德斯坦序列 "G"("m") 是一個自然數的序列。第一項為 "m" 本身。第二項則是先將 "m" 以 2 為基底得出其的瓜瓞式表示法，再將所有的 2 改為 3，再減去 1。更一般地，第 ("n" + 1) 項的 "G"("m")("n" + 1) 為：前幾個古德斯坦序列會很快地終止，如 "G"(3) 結束於第 6 步：之後的古德斯坦序列則成長到很龐大的數字，如 "G"(4) [ A056193] 開始如下："G"(4) 會一直遞增，直到基底為 formula_7 時，會達到最大值 formula_8 ，並在這裡停留 formula_7 步後，然後開始遞減。這個序列到達 0 時，當時的基底為 formula_10。不過，"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 。序數的加法、乘法和指數都是良好定義的。我們可宣告 formula_12 。在古德斯坦序列中，將 "G"("m")("n") 改換基底後，將其記為 formula_13 。明顯的，formula_14 ，現在我們套用 "-1" 運算後，因為 formula_15，所以 formula_16。譬如， formula_17 乃 formula_18，所以 formula_19 和 formula_20 是嚴格變小。需注意的是，若要計算 "f(G(m)(n),n+1)" ，我們要先將 "G"("m")("n") 改為以 "n"+1 為基底的表示法。所以如 formula_21 等的表示式，既不會是無意義的也非等同 formula_22 。"P"("m") 是嚴格遞減的。而標準排序運算元 &lt; 在序數上是良基關係，一個無窮的嚴格遞減序列是不可能存在的。換句話說，每個嚴格遞減的序數序列會停止。但"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，則formula_23。因此，序數 formula_24 是嚴格大於序數 formula_25。起始點為變數的序列長度函式.古德斯坦函式 formula_26 定義為由 "n" 為起始值的古德斯坦序列的長度。因為古德斯坦序列會終止，所以這是一個完全函式。要測定 formula_27 的快速成長，可由多種藉由標準基於序數體系中的函式，如 中的 formula_28 函式，和 Löb and Wainer 的 formula_29 函式。formula_27 有著和 formula_31 近似的成長速度; 更精確地說，對每個 formula_33，formula_27 控制 formula_28，且 formula_31 控制 formula_37。(對兩個函式 formula_38，我們說 formula_39 控制 formula_40 是指，如果對於所有足夠大的 formula_41 ，都有 formula_42。）formula_43其中 formula_44 是將 "n" 改為以 2 為基底的瓜瓞式表示法，並將所有 2 改為 ω 的結果。formula_47.一些例子如下：可計算函式的應用.古德斯坦定理可用於構造一個全可計算函式，但皮亞諾算術卻不能證明它是全函式。圖靈機可以有效地列舉古德斯坦序列；所以存在一個特殊的圖靈機來計算古德斯坦函式。這個圖靈機只需列舉出 "n" 的古德斯坦序列，並在遇到 0 時結束，並傳回其長度。因為每個古德斯坦序列終將結束，所以這個函式是完全的。但因為皮亞諾算術不能證明古德斯坦序列會終止，皮亞諾算術不能證明這個圖靈機計算了一個完全函式。