克魯斯卡爾樹定理

TREE函數、Kruskal樹定理（Template:Lang-en）是逆數學的突出示例。由Template:Tsl推測並由約瑟夫·克魯斯卡爾證明。

In Template:Tsl, Kruskal's tree theorem states that the set of finite Template:Tsls over a Template:Tsl set of labels is itself well-quasi-ordered under Template:Tsl embedding. 在數學中，克魯斯卡樹定理指出，在準有序（英文：well-quasi-ordering）標籤集上的有限樹集合本身在同胚下也是良準有序的（英文：同胚（圖論））嵌入。

歷史 該定理由安德魯·瓦茲索尼（Andrew Vázsonyi）猜想並由約瑟夫·克魯斯卡爾（Joseph Kruskal，1960）證明； Crispin Nash-Williams（1963）給了一個簡短的證明。它從此成為逆向數學（英語：reverse math）中的一個突出例子，作為在 ATR0 內無法證明的陳述（算術超限遞歸（英語：arithmetic transfinite recursion）的一種形式）和有限（英語：finitary）應用該定理給出了快速增長的TREE 函數的存在性。

2004年，這個結果被從樹推廣到圖，成為羅伯遜-西摩定理（英語：Robertson-Seymour theorem），這一結果在逆向數學中也被證明很重要，並導致了增長更快的SSCG 函數（英語： Friedman 的 SSCG 函數）。

陳述 這裡給出的版本是由 Nash-Williams 證明的；克魯斯卡爾的表述要強一些。我們認為的所有樹木都是有限的。

給定一棵有根的樹T，並給定頂點v、w，如果從根到w 的唯一路徑包含v，則稱w 為v 的後繼；如果從v 到w 的路徑另外不包含v，則稱w 為v 的直接後繼其他頂點。

取X為偏序集（中文：partiallyorderedset）。如果 T1、T2 是頂點標記為 X 的有根樹，我們說 T1 可 inf-embeddable 在 T2 中，並且如果存在從 T1 的頂點到 T2 的頂點的單射映射 F，則寫 T1 ≤ T2，使得

弗里德曼的工作 對於可數標籤集 X X.克魯斯卡樹定理可以用二階算術來表達和證明（中文：二階算術）。然而，就像古德斯坦定理或巴黎-哈靈頓定理（英語：Paris-Harrington theorem）一樣，該定理的一些特殊情況和變體可以用比可以證明它們的子系統弱得多的二階算術子系統來表達。這是哈維·弗里德曼（Harvey Friedman）在 20 世紀 80 年代初首次觀察到的，這是當時新興的逆向數學領域的早期成功。在上面的樹被認為是未標記的情況下（即，在 X X 有順序一），Friedman 發現結果在 ATR0（英語：算術超限遞歸）,[2] 從而給出了第一個謂詞（英語：impredicativity）結果的例子，並帶有可證明的謂詞證明.[3]此定理的這種情況仍可由 Π1 證明 1-CA0，但透過在上述樹的順序定義中添加「間隙條件」[4]，他發現該定理的自然變體在該系統中無法證明。[5][6]很久以後，羅伯森-西摩定理給了另一個無法由 Π1 證明的定理 1-CA0。

序數分析（中文：序數分析）證實了克魯斯卡爾定理的強度，該定理的證明論序數等於小維勃倫序數（英文：小維勃倫序數）（有時與較小的阿克曼序數（英文：阿克曼序數）相混淆） ).[來源請求]

樹(3) 假設 P(n) 是這樣的語句：

存在一些 m，如果 T1,...,Tm 是未標記有根樹的有限序列，其中 Tk 有 n+k 個頂點，則對於某些 i < j，Ti ≤ Tj。 根據克魯斯卡定理和柯尼格引理，所有陳述 P(n) 都是正確的。對於每個n，皮亞諾算術（英語：Peano axioms）可以證明P(n)為真，但皮亞諾算術不能證明“P(n)對於所有n都為真”這一命題。[7]此外，皮亞諾算術中 P(n) 的最短證明的長度作為 n 的函數增長得非常快，遠遠快於任何原始遞歸函數（英語：primitive recursive function）或阿克曼函數。 P(n) 所適用的最小 m 同樣隨 n 增長得非常快。

透過合併標籤，弗里德曼定義了一個成長速度更快的函數。[8]對於正整數 n，取 TREE(n)[*] 為最大的 m，這樣我們有：

有一個由 n 個標籤集標記的有根樹序列 T1,...,Tm，其中每個 Ti 最多有 i 個頂點，使得 Ti ≤ Tj 對於任何 i < j ≤ m 不成立。 TREE 序列開始為TREE(1) = 1, TREE(2) = 3，然後突然TREE(3) 爆炸到非常大的值，以至於許多其他「大」組合常數，例如Friedman 的n(4), [*相較之下，*] 非常小。事實上，它比 nn(5)(5) 大得多。 n(4) 的下界（因此 TREE(3) 的下界極弱）為 AA(187196)(1),[9]，其中 A(x) 採用一個參數，定義為 A(x, x)，其中A (k, n) 有兩個參數，是阿克曼函數（英語：Ackermann's function）的一個特定版本，定義為： 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 θ （ Ω ω ω ） {\displaystyle f_{\theta (\Omega ^{\omega }\omega )}} 中的快速成長層次結構（中文：快速成長層次結構）。 AA(187196)(1) 大約為 G 3 ↑ 187196 3 {\displaystyle g_{3\uparrow ^{187196}3}}，其中 gx 是格雷厄姆函數（中文：格雷厄姆數）。

History

The theorem was conjectured by Template:Tsl and proved by Template:Harvs; a short proof was given by Template:Harvs. It has since become a prominent example in Template:Tsl as a statement that cannot be proved within ATR₀ (a form of Template:Tsl), and a Template:Tsl application of the theorem gives the existence of the fast-growing TREE function.

In 2004, the result was generalized from trees to graphs as the Template:Tsl, a result that has also proved important in reverse mathematics and leads to the even-faster-growing Template:Tsl.

Statement

The version given here is that proven by Nash-Williams; Kruskal's formulation is somewhat stronger. All trees we consider are finite.

Given a tree Template:Mvar with a root, and given vertices Template:Mvar, Template:Mvar, call Template:Mvar a successor of Template:Mvar if the unique path from the root to Template:Mvar contains Template:Mvar, and call Template:Mvar an immediate successor of Template:Mvar if additionally the path from Template:Mvar to Template:Mvar contains no other vertex.

Take Template:Mvar to be a Template:Tsl. If Template:Math, Template:Math are rooted trees with vertices labeled in Template:Mvar, we say that Template:Math is inf-embeddable in Template:Math and write Template:Math if there is an injective map Template:Mvar from the vertices of Template:Math to the vertices of Template:Math such that

• For all vertices Template:Mvar of Template:Math, the label of Template:Mvar precedes the label of Template:Math,
• If Template:Mvar is any successor of Template:Mvar in Template:Math, then Template:Math is a successor of Template:Math, and
• If Template:Math, Template:Math are any two distinct immediate successors of Template:Mvar, then the path from Template:Math to Template:Math in Template:Math contains Template:Math.

Kruskal's tree theorem then states:

If Template:Mvar is Template:Tsl, then the set of rooted trees with labels in Template:Mvar is well-quasi-ordered under the inf-embeddable order defined above. (That is to say, given any infinite sequence Template:Math of rooted trees labeled in Template:Mvar, there is some Template:Math so that Template:Math.)

Weak tree function

Define Template:Math, the weak tree function, as the length of the longest sequence of 1-labelled trees (i.e. Template:Math) such that:

• The tree at position Template:Mvar in the sequence has no more than Template:Math vertices, for all Template:Mvar.
• No tree is homeomorphically embeddable into any tree following it in the sequence.

It is known that tree(1) = 2, tree(2) = 5, and tree(3) ≥ 844424930131960,Template:Better source needed but Template:Math (where the argument specifies the number of labels; see Template:Tsl) is larger than ${\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}}^{{\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}}^{{\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}}^{{\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}}^{{\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}}^8(7)}(7)}(7)}(7)}(7)$

Friedman's work

For a countable label set $X$, Kruskal's tree theorem can be expressed and proven using Template:Tsl. However, like 古德斯坦定理 or the Template:Tsl, some special cases and variants of the theorem can be expressed in subsystems of second-order arithmetic much weaker than the subsystems where they can be proved. This was first observed by Template:Tsl in the early 1980s, an early success of the then-nascent field of reverse mathematics. In the case where the trees above are taken to be unlabeled (that is, in the case where $X$ has order one), Friedman found that the result was unprovable in Template:Tsl, thus giving the first example of a Template:Tsl result with a provably impredicative proof. This case of the theorem is still provable by ΠTemplate:Su-CA₀, but by adding a "gap condition" to the definition of the order on trees above, he found a natural variation of the theorem unprovable in this system. Much later, the Robertson–Seymour theorem would give another theorem unprovable by ΠTemplate:Su-CA₀.

Template:Tsl confirms the strength of Kruskal's theorem, with the proof-theoretic ordinal of the theorem equaling the Template:Tsl (sometimes confused with the smaller Template:Tsl).Template:Citation needed

TREE(3)

Suppose that P(n) is the statement:

There is some m such that if T₁,...,T_m is a finite sequence of unlabeled rooted trees where T_k has n+k vertices, then T_i ≤ T_j for some i < j.

All the statements P(n) are true as a consequence of Kruskal's theorem and 柯尼格引理. For each n, Template:Tsl can prove that P(n) is true, but Peano arithmetic cannot prove the statement "P(n) is true for all n". Moreover the length of the shortest proof of P(n) in Peano arithmetic grows phenomenally fast as a function of n, far faster than any Template:Tsl or the 阿克曼函數 for example. The least m for which P(n) holds similarly grows extremely quickly with n.

By incorporating labels, Friedman defined a far faster-growing function. For a positive integer n, take TREE(n)Template:Ref label to be the largest m so that we have the following:

There is a sequence T₁,...,T_m of rooted trees labelled from a set of n labels, where each T_i has at most i vertices, such that T_i  ≤  T_j does not hold for any i < j  ≤ m.

The TREE sequence begins TREE(1) = 1, TREE(2) = 3, then suddenly TREE(3) explodes to a value so immensely large that many other "large" combinatorial constants, such as Friedman's n(4),Template:Ref label are extremely small by comparison. In fact, it is much larger than nⁿ⁽⁵⁾(5). A lower bound for n(4), and hence an extremely weak lower bound for TREE(3), is A^A(187196)(1), where A(x) taking one argument, is defined as A(x, x), where A(k, n), taking two arguments, is a particular version of Template:Tsl defined as: A(1, n) = 2n, A(k+1, 1) = A(k, 1), A(k+1, n+1) = A(k, A(k+1, n)). 葛立恆數, for example, is much smaller than the lower bound A^A(187196)(1). It can be shown that the growth-rate of the function TREE is at least $f_{\theta ({\mathrm{\Omega }}^{\omega }\omega )}$ in the Template:Tsl. A^A(187196)(1) is approximately $g_{3{\uparrow }^{187196}3}$, where g_x is Template:Tsl.

参见

• Template:Tsl
• Template:Tsl
• Template:Tsl

注释

Template:Note label Friedman originally denoted this function by TR[n].

Template:Note label n(k) is defined as the length of the longest possible sequence that can be constructed with a k-letter alphabet such that no block of letters x_i,...,x_2i is a subsequence of any later block x_j,...,x_2j. $n(1)=3,n(2)=11,\text{and}n(3)>2{\uparrow }^{7197}158386$.

參考

Citations

Bibliography

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Cite journal
• Template:Citation
• Template:Cite journal
• Template:Citation
• Template:Citation