克鲁斯卡尔树定理

In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered（英语：well-quasi-ordering） set of labels is itself well-quasi-ordered under homeomorphic（英语：homeomorphism (graph theory)） embedding.

History

The theorem was conjectured by Andrew Vázsonyi（英语：Andrew Vázsonyi） and proved by Joseph Kruskal （1960）; a short proof was given by Crispin Nash-Williams （1963）. It has since become a prominent example in reverse mathematics（英语：reverse mathematics） as a statement that cannot be proved within ATR₀ (a form of arithmetical transfinite recursion（英语：arithmetical transfinite recursion）), and a finitary（英语：finitary） 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 Robertson–Seymour theorem（英语：Robertson–Seymour theorem）, a result that has also proved important in reverse mathematics and leads to the even-faster-growing SSCG function（英语：Friedman's SSCG function）.

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 T with a root, and given vertices v, w, call w a successor of v if the unique path from the root to w contains v, and call w an immediate successor of v if additionally the path from v to w contains no other vertex.

Take X to be a partially ordered set（英语：partially ordered set）. If T₁, T₂ are rooted trees with vertices labeled in X, we say that T₁ is inf-embeddable in T₂ and write T₁ ≤ T₂ if there is an injective map F from the vertices of T₁ to the vertices of T₂ such that

• For all vertices v of T₁, the label of v precedes the label of F(v),
• If w is any successor of v in T₁, then F(w) is a successor of F(v), and
• If w₁, w₂ are any two distinct immediate successors of v, then the path from F(w₁) to F(w₂) in T₂ contains F(v).

Kruskal's tree theorem then states:

If X is well-quasi-ordered（英语：well-quasi-ordering）, then the set of rooted trees with labels in X is well-quasi-ordered under the inf-embeddable order defined above. (That is to say, given any infinite sequence T₁, T₂, … of rooted trees labeled in X, there is some i < j so that T_i ≤ T_j.)

Weak tree function

Define tree(n), the weak tree function, as the length of the longest sequence of 1-labelled trees (i.e. X = {1}) such that:

• The tree at position k in the sequence has no more than k + n vertices, for all k.
• 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,^{[1][需要较佳来源]} but TREE(3) (where the argument specifies the number of labels; see below（英语：Kruskal's tree theorem#TREE(3)）) is larger than ${\displaystyle \mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{8}(7)}(7)}(7)}(7)}(7)}$

Friedman's work

For a countable label set ${\displaystyle X}$, Kruskal's tree theorem can be expressed and proven using second-order arithmetic（英语：second-order arithmetic）. However, like 古德斯坦定理 or the Paris–Harrington theorem（英语：Paris–Harrington theorem）, 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 Harvey Friedman（英语：Harvey Friedman） 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 ${\displaystyle X}$ has order one), Friedman found that the result was unprovable in <span class="ilh-all " data-orig-title="ATR₀" data-lang-code="en" data-lang-name="英语" data-foreign-title="arithmetical transfinite recursion">[[:ATR₀|ATR₀]]（英语：arithmetical transfinite recursion）,^[2] thus giving the first example of a predicative（英语：impredicativity） result with a provably impredicative proof.^[3] This case of the theorem is still provable by Π1
1-CA₀, but by adding a "gap condition"^[4] to the definition of the order on trees above, he found a natural variation of the theorem unprovable in this system.^[5][6] Much later, the Robertson–Seymour theorem would give another theorem unprovable by Π1
1-CA₀.

Ordinal analysis（英语：Ordinal analysis） confirms the strength of Kruskal's theorem, with the proof-theoretic ordinal of the theorem equaling the small Veblen ordinal（英语：small Veblen ordinal） (sometimes confused with the smaller Ackermann ordinal（英语：Ackermann ordinal）).^{[来源请求]}

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, Peano arithmetic（英语：Peano axioms） can prove that P(n) is true, but Peano arithmetic cannot prove the statement "P(n) is true for all n".^[7] 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 primitive recursive function（英语：primitive recursive function） 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.^[8] For a positive integer n, take TREE(n)^[*] 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),^[**] 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),^[9] where A(x) taking one argument, is defined as A(x, x), where A(k, n), taking two arguments, is a particular version of Ackermann's function（英语：Ackermann's function） 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 ${\displaystyle f_{\theta (\Omega ^{\omega }\omega )}}$ in the fast-growing hierarchy（英语：fast-growing hierarchy）. A^A(187196)(1) is approximately ${\displaystyle g_{3\uparrow ^{187196}3}}$, where g_x is Graham's function（英语：Graham's number）.

参见

• Paris–Harrington theorem（英语：Paris–Harrington theorem）
• Kanamori–McAloon theorem（英语：Kanamori–McAloon theorem）
• Robertson–Seymour theorem（英语：Robertson–Seymour theorem）

注释

^{^ *} Friedman originally denoted this function by TR[n].

^{^ **} 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.^[10] ${\displaystyle n(1)=3,n(2)=11,\,{\textrm {and}}\,n(3)>2\uparrow ^{7197}158386}$.

Category:Trees (graph theory)（英语：Category:Trees (graph theory)）