克魯斯卡爾樹定理

TREE函數與克魯斯卡爾樹定理（）是逆數學中極具代表性的例子。該定理最早由提出猜想，隨後由約瑟夫·克魯斯卡爾給出證明。
在數學上，克魯斯卡爾樹定理指出：如果一個標籤集合本身具備，那麼由這些標籤構成的所有有限樹的集合，在同胚嵌入的意義下，也同樣具備良準序。

歷史
如前所述，該定理由安德魯·瓦茲尼提出猜想，並於1960年由證明；隨後在1963年，給出了一個更為簡潔的證明。此後，它成為了逆數學領域的經典案例——人們發現該定理無法在 ATR0（算術超限遞歸的一種形式）系統內被證明。此外，將該定理應用於情況時，可以推導出增長速度極快的TREE函數的存在性。

2004年，這一結論從「樹」推廣到了「圖」，即著名的羅伯遜-西摩定理（）。該定理在逆數學中同樣意義重大，並由此衍生出了增長更為迅猛的。

定理敘述
這裡採用的版本基於納什-威廉斯的證明，克魯斯卡爾最初的表述則要更強一些。在此，我們討論的所有樹均默認為有限樹。

給定一棵有根樹 以及頂點 和 ：如果從根節點到 的唯一路徑經過了 ，我們就稱 是 的「後繼」（successor）；如果從 到 的路徑上沒有其他頂點，則稱 是 的「直接後繼」（immediate successor）。

設 為一個偏序集。假設 和 是兩棵有根樹，且它們的頂點都帶有集合 中的標籤。如果存在一個從 的頂點集到 的頂點集的單射映射 ，並且滿足以下三個條件，我們就稱 「下確界可嵌入」（inf-embeddable）於 ，記作 ：

• 對於 中的任意頂點 ， 的標籤在偏序中不大於（即小於或等於） 的標籤；
• 如果 是 中 的任意後繼，那麼 也必須是 的後繼；
• 如果 和 是 的任意兩個不同的直接後繼，那麼在 中，從 到 的路徑必須經過 。

克魯斯卡爾樹定理的核心結論如下：
如果標籤集 具備，那麼在上述的下確界嵌入關係下，所有帶有 中標籤的有根樹所構成的集合也是良準序的。（也就是說，給定任意一個由上述有根樹組成的無窮序列 ，必然能找到一對索引 ，使得 。）

弱 tree 函數
我們定義「弱 tree 函數」 為滿足以下條件的最長單標籤（即標籤集 {{math|1=X = {1} }}）樹序列的長度：

• 序列中第 棵樹的頂點數不能超過 （對所有的 均成立）。
• 序列中的任何一棵樹，都不能同胚嵌入到排在它後面的任意一棵樹中。

已知 tree(1) = 2，tree(2) = 5，且 tree(3) ≥ 844,424,930,131,960， 但強版本的 （其中的參數指的是「標籤的種類數」，詳見）要大得多，甚至超過了 \mathrm{tree}^{\mathrm{tree}^{\mathrm{tree}^{\mathrm{tree}^{\mathrm{tree}^{8}(7)}(7)}(7)}(7)}(7)。

弗里德曼的貢獻
對於可數標籤集 X，克魯斯卡爾樹定理可以使用來表述和證明。然而，正如古德斯坦定理和一樣，該定理的一些特例和變體，雖然能在極弱的二階算術子系統中被「表述」，卻無法在這些系統中被「證明」。這一現象最早由在20世紀80年代初發現，這也是當時新興的逆數學領域取得的早期重大成功之一。

弗里德曼發現，即使只考慮無標籤樹（即標籤集 X 的大小為 1），該結果在 系統中依然無法被證明。 這給出了史上首個「具備性質，但其證明被證實必須依賴非直謂方法」的例子。 雖然這種無標籤情況仍能被更強的 Π-CA0 系統證明，但弗里德曼進一步發現在樹的偏序定義中加入一個「間隙條件」（gap condition）後，所得到的一個自然變體連 Π-CA0 也無法證明。 直到很久以後，羅伯遜-西摩定理才提供了另一個無法由 Π-CA0 證明的例子。

進一步證實了克魯斯卡爾定理的邏輯強度：該定理的證明論序數等於（注意不要與較小的混淆）。

TREE(3)
考慮以下命題 P(n)：
:必然存在某個整數 m，使得對於任意一個長度為 m 的無標籤有根樹序列 T1, ..., Tm（其中第 k 棵樹 Tk 擁有 n+k 個頂點），都必然存在索引 i i ≤ Tj。

根據克魯斯卡爾定理和柯尼格引理，所有的命題 P(n) 都是正確的。對於每一個具體的 n，皮亞諾算術都能證明 P(n) 為真；然而，皮亞諾算術卻無法證明「對於所有的 n，P(n) 都為真」這一全稱命題。 此外，在皮亞諾算術中，證明 P(n) 所需的最短步驟數，作為 n 的函數增長得極其狂野，其速度遠遠超過任何原始遞歸函數或阿克曼函數。同樣地，能讓 P(n) 成立的最小 m 值也隨著 n 的增加而以極其恐怖的速度飆升。

通過在樹上引入標籤，弗里德曼定義出了一個增長速度更為誇張的函數。 對於正整數 n，我們定義 TREE(n) 為滿足以下條件的最大序列長度 m：
:存在一個有根樹序列 T1, ..., Tm，這些樹的頂點從一個包含 n 種不同標籤的集合中取值，且每棵樹 Ti 最多包含 i 個頂點；同時，對於任意的 i i ≤ Tj。

TREE 序列的初始值看似平淡無奇：TREE(1) = 1，TREE(2) = 3。然而，TREE(3) 卻突然「爆炸」至一個難以估量的巨大數值。與之相比，許多其他被認為是「天文數字」的組合學常數（例如弗里德曼自己的 n(4)）都顯得微不足道。事實上，TREE(3) 遠遠大於 nn(5)(5)。已知 n(4) 的一個下界是 AA(187196)(1)（這也是 TREE(3) 的一個極端保守的下界）。

這裡的單參數函數 A(x) 定義為 A(x, x)，而雙參數函數 A(k, n) 是阿克曼函數的一種變體，定義為：A(1, n) = 2n，A(k+1, 1) = A(k, 1)，A(k+1, n+1) = A(k, A(k+1, n))。作為參考，廣為人知的葛立恆數甚至遠遠夠不到下界 AA(187196)(1)。在快速增長層次（）中，可以證明 TREE 函數的增長率至少達到了 f_{\theta(\Omega^\omega \omega)}。此外，AA(187196)(1) 大致相當於 g_{3 \uparrow^{187196} 3}，其中 gx 為。

參見
*
*
*羅伯遜-西摩定理（）

註釋
: 弗里德曼最初將此函數表示為 TR[n]。
: n(k) 定義為：使用 k 個字母的字母表可以構造的最長序列的長度，滿足沒有任何字母區塊 xi,...,x2i 是後續任何字母區塊 xj,...,x2j 的子序列。n(1) = 3, n(2) = 11，且 n(3) > 2 \uparrow^{7197} 158386。

參考
;文中引註

;書目
*
*
*
*
*
*
*
*