Kruskal's tree theorem

Template:Short description In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding.

A finitary application of the theorem gives the existence of the fast-growing TREE function. TREE(3) is largely accepted to be one of the largest simply defined finite numbers, dwarfing other large numbers such as Graham's number and googolplex.

History

The theorem was conjectured by Andrew Vázsonyi and proved by Template:Harvs; a short proof was given by Template:Harvs. It has since become a prominent example in reverse mathematics as a statement that cannot be proved in ATR₀ (a second-order arithmetic theory with a form of arithmetical transfinite recursion).

In 2004, the result was generalized from trees to graphs as the Robertson–Seymour theorem, a result that has also proved important in reverse mathematics and leads to the even-faster-growing SSCG function, which dwarfs $\text{TREE}(3)$.

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 partially ordered set. 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 $T_1\le T_2$ 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 $F(v)$;
• If Template:Mvar is any successor of Template:Mvar in Template:Math, then $F(w)$ is a successor of $F(v)$; and
• If Template:Math, Template:Math are any two distinct immediate successors of Template:Mvar, then the path from $F(w_1)$ to $F(w_2)$ in Template:Math contains $F(v)$.

Kruskal's tree theorem then states:

If Template:Mvar is well-quasi-ordered, 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

$i<j$

so that

$T_i\le T_j$

.)

Friedman's work

For a countable label set Template:Mvar, Kruskal's tree theorem can be expressed and proven using second-order arithmetic. However, like Goodstein's theorem or the 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 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 Template:Mvar has size one), Friedman found that the result was unprovable in ATR₀, thus giving the first example of a predicative 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₀.

Ordinal analysis confirms the strength of Kruskal's theorem, with the proof-theoretic ordinal of the theorem equaling the small Veblen ordinal (sometimes confused with the smaller Ackermann ordinal).Template:Sfn

Weak tree function

Suppose that $P(n)$ is the statement:

There is some Template:Mvar such that if Template:Math is a finite sequence of unlabeled rooted trees where Template:Mvar has $i+n$ vertices, then $T_i\le T_j$ for some $i<j$.

All the statements $P(n)$ are true as a consequence of Kruskal's theorem and Kőnig's lemma. For each Template:Mvar, Peano arithmetic can prove that $P(n)$ is true, but Peano arithmetic cannot prove the statement "$P(n)$ is true for all Template:Mvar". Moreover, the length of the shortest proof of $P(n)$ in Peano arithmetic grows phenomenally fast as a function of Template:Mvar, far faster than any primitive recursive function or the Ackermann function, for example. The least Template:Mvar for which $P(n)$ holds similarly grows extremely quickly with Template:Mvar.

TREE function

Sequence of trees where each node is colored either green, red, blue

A sequence of rooted trees labelled from a set of 3 labels (blue < red < green). The Template:Mvarth tree in the sequence contains at most Template:Mvar vertices, and no tree is inf-embeddable within any later tree in the sequence. Template:Math is defined to be the longest possible length of such a sequence.

By incorporating labels, Friedman defined a far faster-growing function. For a positive integer Template:Var, take $\text{TREE}(n)$^[a] to be the largest Template:Var so that we have the following:

There is a sequence Template:Math of rooted trees labelled from a set of Template:Mvar labels, where each Template:Mvar has at most Template:Mvar vertices, such that $T_i\le T_j$ does not hold for any $i<j\le m$.

The TREE sequence begins $\text{TREE}(1)=1$, $\text{TREE}(2)=3$, before $\text{TREE}(3)$ suddenly explodes to a value so large that many other "large" combinatorial constants, such as Friedman's $n(4)$, $n^{n(5)}(5)$, and Graham's number,^[b] are extremely small by comparison. A lower bound for $n(4)$, and, hence, an extremely weak lower bound for $\text{TREE}(3)$, is $A^{A(187196)}(1)$.^[c] Graham's number, for example, is much smaller than the lower bound $A^{A(187196)}(1)$, which is approximately $g_{3{\uparrow }^{187196}3}$, where $g_x$ is Graham's function.

See also

• Paris–Harrington theorem
• Kanamori–McAloon theorem
• Robertson–Seymour theorem

Notes

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

^{^ b} 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{<mrow data-mjx-texclass="ORD">and</mrow>}n(3)>2{\uparrow }^{7197}158386$.

^{^ c} 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 defined as: A(1, n) = 2n, A(k+1, 1) = A(k, 1), A(k+1, n+1) = A(k, A(k+1, n)).

References

Citations Template:Reflist Bibliography