克魯斯卡爾樹定理 TREE函數Kruskal樹定理英語Kruskals tree theorem是逆數學的突出示例由安德魯瓦茲尼英语Andrew Vázsonyi推測並由約瑟夫克魯斯卡爾證明 已隱藏部分未翻譯内容歡迎參與翻譯 In mathematics Kruskals tree theorem states that the set of finite trees over a wellquasiordered英语wellquasiordering set of labels is itself wellquasiordered under homeomorphic英语homeomorphism graph theory embedding 在數學中克魯斯卡樹定理指出在準有序英文wellquasiordering標籤集上的有限樹集合本身在同胚下也是良準有序的英文同胚圖論嵌入 歷史 該定理由安德魯瓦茲索尼Andrew Vázsonyi猜想並由約瑟夫克魯斯卡爾Joseph Kruskal證明 Crispin NashWilliams給了一個簡短的證明它從此成為逆向數學英語reverse math中的一個突出例子作為在 ATR 內無法證明的陳述算術超限遞歸英語arithmetic transfinite recursion的一種形式和有限英語finitary應用該定理給出了快速增長的TREE 函數的存在性 年這個結果被從樹推廣到圖成為羅伯遜西摩定理英語RobertsonSeymour theorem這一結果在逆向數學中也被證明很重要並導致了增長更快的SSCG 函數英語 Friedman 的 SSCG 函數 陳述 這裡給出的版本是由 NashWilliams 證明的克魯斯卡爾的表述要強一些我們認為的所有樹木都是有限的 給定一棵有根的樹T並給定頂點vw如果從根到w 的唯一路徑包含v則稱w 為v 的後繼如果從v 到w 的路徑另外不包含v則稱w 為v 的直接後繼其他頂點 取X為偏序集中文partiallyorderedset如果 TT 是頂點標記為 X 的有根樹我們說 T 可 infembeddable 在 T 中並且如果存在從 T 的頂點到 T 的頂點的單射映射 F則寫 T  T使得 弗里德曼的工作 對於可數標籤集 X X克魯斯卡樹定理可以用二階算術來表達和證明中文二階算術然而就像古德斯坦定理或巴黎哈靈頓定理英語ParisHarrington theorem一樣該定理的一些特殊情況和變體可以用比可以證明它們的子系統弱得多的二階算術子系統來表達這是哈維弗里德曼Harvey Friedman在  世紀  年代初首次觀察到的這是當時新興的逆向數學領域的早期成功在上面的樹被認為是未標記的情況下即在 X X 有順序一Friedman 發現結果在 ATR英語算術超限遞歸 從而給出了第一個謂詞英語impredicativity結果的例子並帶有可證明的謂詞證明此定理的這種情況仍可由 Π 證明 CA但透過在上述樹的順序定義中添加間隙條件他發現該定理的自然變體在該系統中無法證明很久以後羅伯森西摩定理給了另一個無法由 Π 證明的定理 CA 序數分析中文序數分析證實了克魯斯卡爾定理的強度該定理的證明論序數等於小維勃倫序數英文小維勃倫序數有時與較小的阿克曼序數英文阿克曼序數相混淆 來源請求 樹 假設 Pn 是這樣的語句 存在一些 m如果 TTm 是未標記有根樹的有限序列其中 Tk 有 nk 個頂點則對於某些 i  jTi  Tj 根據克魯斯卡定理和柯尼格引理所有陳述 Pn 都是正確的對於每個n皮亞諾算術英語Peano axioms可以證明Pn為真但皮亞諾算術不能證明Pn對於所有n都為真這一命題此外皮亞諾算術中 Pn 的最短證明的長度作為 n 的函數增長得非常快遠遠快於任何原始遞歸函數英語primitive recursive function或阿克曼函數 Pn 所適用的最小 m 同樣隨 n 增長得非常快 透過合併標籤弗里德曼定義了一個成長速度更快的函數對於正整數 n取 TREEn 為最大的 m這樣我們有 有一個由 n 個標籤集標記的有根樹序列 TTm其中每個 Ti 最多有 i 個頂點使得 Ti  Tj 對於任何 i  j  m 不成立 TREE 序列開始為TREE   TREE  然後突然TREE 爆炸到非常大的值以至於許多其他大組合常數例如Friedman 的n 相較之下 非常小事實上它比 nn 大得多 n 的下界因此 TREE 的下界極弱為 AA其中 Ax 採用一個參數定義為 Ax x其中A k n 有兩個參數是阿克曼函數英語Ackermanns function的一個特定版本定義為 A n  n Ak   A k   Ak n  Ak Ak n例如葛立恆數遠小於下限 AA可以證明函數TREE的成長率至少為 F θ  Ω ω ω  displaystyle ftheta Omega omega omega  中的快速成長層次結構中文快速成長層次結構 AA 大約為 G     displaystyle guparrow 其中 gx 是格雷厄姆函數中文格雷厄姆數