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 a fast-growing TREE function. TREE(3) is one of the largest simply defined finite numbers, dwarfing other large numbers such as Graham's number and googolplex.
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 in ATR<sub>0</sub> (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 TREE.
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 with a root, and given vertices , , call a descendant of if the unique path from the root to contains , and call a child 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:
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 field of reverse mathematics. In the case where the trees above are taken to be unlabeled (that is, in the case where has size one), Friedman found that the result was unprovable in ATR<sub>0</sub>, thus giving the first example of a predicative result with a provably impredicative proof. This case of the theorem is still provable by à-CA<sub>0</sub>, 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 à-CA<sub>0</sub>.
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).
Suppose that is the statement:
All the statements are true as a consequence of Kruskal's theorem and KÃ Ânig's lemma. For each , Peano arithmetic can prove that is true, but Peano arithmetic cannot prove the statement " is true for all ". Moreover, the length of the shortest proof of in Peano arithmetic grows phenomenally fast as a function of , far faster than any primitive recursive function or the Ackermann function, for example. The least for which holds similarly grows extremely quickly with .
Friedman defined the following function, which is a weaker version of the TREE function below. For a positive integer , take to be the largest so that we have the following:
Friedman computes the first few terms of this sequence as , , and . He also estimates to be less than 100, while suddenly explodes to a very large value. Any proof that exists in Peano arithmetic requires at least symbols, where is the unary version of the Ackermann function, but it can be proved to exist in ACA<sub>0</sub> with at most 10,000 symbols.
By incorporating labels, Friedman defined a far faster-growing function. For a positive integer , take to be the largest so that we have the following:
Kruskal's theorem asserts that is finite for all . The TREE function eventually dominates every provably recursive function of the system ACA<sub>0</sub> + ÃÂ -BI.
The sequence begins , ; before suddenly explodes to a value so large that many other "large" combinatorial constants, such as Friedman's and Graham's number, are extremely small by comparison. A lower bound for , and, hence, an extremely weak lower bound for , is , where is the single-argument version of Ackermann's function, defined as .
Friedman showed that is greater than the halting time of any Turing machine that can be proved to halt in ACA<sub>0</sub> + ÃÂ -BI with at most symbols, where denotes tetration.
Citations
Bibliography