# Kruskal's tree theorem

(Redirected from Kruskal tree theorem)

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. The theorem was conjectured by Andrew Vázsonyi and proved by Joseph Kruskal (1960); a short proof was given by Nash-Williams (1963). It has since become a prominent example in reverse mathematics as a statement that cannot be proved within ATR0 (a form of arithmetical transfinite recursion), and a finitary application of the theorem gives the existence of the notoriously fast-growing TREE function.

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.

## Statement

We give the version proved by Nash-Williams; Kruskal's formulation is somewhat stronger. Given a tree ${\displaystyle T}$ with a root, and given vertices ${\displaystyle v}$, ${\displaystyle w}$, call ${\displaystyle v}$ a successor of ${\displaystyle w}$ if the unique path from the root to ${\displaystyle v}$ contains ${\displaystyle w}$, and call ${\displaystyle v}$ an immediate successor of ${\displaystyle w}$ if additionally the path from ${\displaystyle w}$ to ${\displaystyle v}$ contains no other vertex. Take ${\displaystyle X}$ to be a partially ordered set. Taking ${\displaystyle T_{1},T_{2}}$ to be rooted trees with vertices labeled in ${\displaystyle X}$, we say that ${\displaystyle T_{1}}$ is inf-embeddable in ${\displaystyle T_{2}}$ and write ${\displaystyle T_{1}\leq T_{2}}$ if there is a map ${\displaystyle F}$ from the vertices of ${\displaystyle T_{1}}$ to the vertices of ${\displaystyle T_{2}}$ such that

• For all vertices ${\displaystyle v}$ of ${\displaystyle T_{1}}$, the label of ${\displaystyle v}$ precedes the label of ${\displaystyle F(v)}$,
• If ${\displaystyle w}$ is any successor of ${\displaystyle v}$ in ${\displaystyle T_{1}}$, then ${\displaystyle F(w)}$ is a successor of ${\displaystyle F(v)}$, and
• If ${\displaystyle w_{1},w_{2}}$ are any pair of distinct immediate successors of ${\displaystyle v}$, then the path from ${\displaystyle F(w_{1})}$ to ${\displaystyle F(w_{2})}$ in ${\displaystyle T_{2}}$ contains ${\displaystyle F(v)}$.

Then result states that, if ${\displaystyle X}$ is well-quasi-ordered, it follows that the set of rooted trees with labels in ${\displaystyle X}$ is well-quasi-ordered under the order defined above. That is to say, given any infinite sequence ${\displaystyle T_{1},T_{2},\dots }$ of rooted trees labeled in ${\displaystyle X}$, there is some ${\displaystyle i so that ${\displaystyle T_{i}\leq T_{j}}$.

## Weak tree function

Define tree(n), the weak tree function, as the length of the longest sequence of 1-labelled trees such that:

• Every tree at position k (for all k) has no more than k + n vertices.
• 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) > 262140, but TREE(3) (see below) is larger than treetreetreetreetree8(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. 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 1980's, 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 ATR0,[1] thus giving the first example of a predicative result with a provably impredicative proof.[2] This case of the theorem is still provable in Π1
1
-CA0, but by adding a "gap condition" [3] to the definition of the order on trees above, he found a natural variation of the theorem unprovable in this system.[4][5] Much later, the Robertson-Seymour theorem would give another theorem unprovable inside Π1
1
-CA0.

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).

### TREE(3)

Suppose that P(n) is the statement:

There is some m such that if T1,...,Tm is a finite sequence of unlabeled rooted trees where Tk has n+k vertices, then Ti ≤ Tj for some i < j.

This statement is a simple application of Kruskal's theorem. For each n, Peano arithmetic can prove that P(n) is true, but Peano arithmetic cannot prove the statement "P(n) is true for all n".[6] Moreover the shortest proof of P(n) in Peano arithmetic grows phenomenally fast as a function of n; far faster than any primitive recursive function or the Ackermann function 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.[7] For a positive integer n, take TREE(n)[*] to be the largest m so that we have the following:

There is a sequence T1,...,Tm of rooted trees labelled from a set of n labels, where each Ti has at most i vertices, such that Ti  ≤  Tj 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 enormously 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 nn(5)(5). A lower bound for n(4), and hence an extremely weak lower bound for TREE(3), is A(A(...A(1)...)), where the number of A's is A(187196),[8] and A() is a version of Ackermann's function: A(x) = 2 [x+1] x in hyperoperation. Graham's number, for example, is approximately A64(4), which is much smaller than the lower bound AA(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.

## Notes

^ * 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 xi,...,x2i is a subsequence of any later block xj,...,x2j.[9] n(1) = 3, n(2) = 11 and n(3) > 2 [7199] 158386.

## References

Citations
1. ^ Simpson 1985, Theorem 1.8
2. ^ Friedman 2002, p. 60
3. ^ Simpson 1985, Definition 4.1
4. ^ Simpson 1985, Theorem 5.14
5. ^ Marcone 2001, p. 8–9
6. ^ Smith 1985, p. 120
7. ^ Friedman, Harvey (28 March 2006). "273:Sigma01/optimal/size". Ohio State University Department of Maths. Retrieved 8 August 2017.
8. ^ Friedman, Harvey M. (1 June 2000). "Enormous Integers In Real Life" (PDF). Ohio State University. Retrieved 8 August 2017.
9. ^ Friedman, Harvey M. (8 October 1998). "Long Finite Sequences" (PDF). Ohio State University Department of Mathematics. pp. 5, 48 (Thm.6.8). Retrieved 8 August 2017.
Bibliography