Kruskal's 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 ; a short proof was given by . It has since become a prominent example in reverse mathematics as a statement that cannot be proved within ATR0, 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. All trees we consider are finite.
Given a tree with a root, and given vertices,, call a successor of if the unique path from the root to contains, and call an immediate successor of if additionally the path from to contains no other vertex.
Take to be a partially ordered set. If are rooted trees with vertices labeled in, we say that is inf-embeddable in and write if there is an injective map from the vertices of to the vertices of such that
Kruskal's tree theorem then states:
If is well-quasi-ordered, then the set of rooted trees with labels in is well-quasi-ordered under the inf-embeddable order defined above.

Weak tree function

Define, the weak tree function, as the length of the longest sequence of 1-labelled trees such that:
It is known that tree = 2, tree = 3, and tree > 844424930131960, but is larger than.

Friedman's work

For a countable label set, 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, Friedman found that the result was unprovable in ATR0, thus giving the first example of a predicative result with a provably impredicative proof. This case of the theorem is still provable in Π-CA0, 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 inside Π-CA0.
Ordinal analysis confirms the strength of Kruskal's theorem, with the proof-theoretic ordinal of the theorem equaling the small Veblen ordinal.

TREE(3)

Suppose that P is the statement:
All the statements P are true as a consequence of Kruskal's theorem and Kőnig's lemma. For each n, Peano arithmetic can prove that P is true, but Peano arithmetic cannot prove the statement "P is true for all n". Moreover the length of the shortest proof of P 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 holds similarly grows extremely quickly with n.
By incorporating labels, Friedman defined a far faster-growing function. For a positive integer n, take TREE to be the largest m so that we have the following:
The TREE sequence begins TREE = 1, TREE = 3, then suddenly TREE explodes to a value so immensely large that many other "large" combinatorial constants, such as Friedman's n, are extremely small by comparison. In fact, it is much larger than nn. A lower bound for n, and hence an extremely weak lower bound for TREE, is AA, where A is a version of Ackermann's function:. Graham's number, for example, is approximately A64, which is much smaller than the lower bound AA. It can be shown that the growth-rate of the function TREE is at least in the fast-growing hierarchy. AA is approximately, where gx is Graham's function.