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.

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.

History

The theorem was conjectured by 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 as a statement that cannot be proved in ATR0 (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.

Statement

For labeled trees

The version given here is that proven by Kruskal (1960). All trees we consider are finite.

Given a tree T with a root, and given vertices v, w, call w a descendant of v if the unique path from the root to w contains v, and call w a child of v if additionally the path from v to w is of length one (contains no other vertex).

Take (X,≤X) to be a quasi-ordered (preordered) set. If T1, T2 are rooted trees with vertices labeled in X, we say that T1 is inf-embeddable in T2 and write T1≤T2 if there is an injective map F from the vertices of T1 to the vertices of T2 such that:

  • For all vertices v of T1, the label of v is ≤X the label of F(v);
  • If w is any descendant of v in T1, then F(w) is a descendant of F(v); and
  • If w1, w2 are any two distinct children of v, then F(w1) and F(w2) lie in different subtrees of F(v).

Kruskal's tree theorem then states:

If X is well-quasi-ordered, 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 T1,T2,… of rooted trees labeled in X, there is some i<j so that Ti≤Tj.

Statement for plain (unlabeled) trees

The following is a corollary of the above; Nash-Williams (1963) provides a direct proof of this statement.

If T1, T2 are unlabeled rooted trees, we say that T1 is embeddable in T2 and write T1≤T2 if there is an injective map F from the vertices of T1 to the vertices of T2 such that only the second and third of the above conditions hold:

  • If w is any descendant of v in T1, then F(w) is a descendant of F(v); and
  • If w1, w2 are any two distinct children of v, then F(w1) and F(w2) lie in different subtrees of F(v).

Then:

The set of unlabeled rooted trees is well-quasi-ordered under the embeddable order defined above. That is to say, given any infinite sequence T1,T2,… of unlabeled rooted trees, there is some i<j so that Ti≤Tj.

Friedman's work

For a countable label set 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 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 X has size one), 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 by Π1
1
-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 by Π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). Kruskal's tree theorem itself proves that Γ0, the Feferman–Schütte ordinal, is well-founded; in particular, the inf-embeddable ordering on a countable label set contains a well-ordered chain of order type Γ0.

Weak tree function

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 Ti has i+n vertices, then Ti≤Tj 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 n, Peano arithmetic can prove that P(n) is true, but Peano arithmetic cannot prove the statement "P(n) is true for all n". 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 or the Ackermann function, for example.[citation needed] The least m for which P(n) holds similarly grows extremely quickly with n.

Friedman defined the following function, which is a weaker version of the TREE function below. For a positive integer n, take FFF(n) to be the largest m so that we have the following:

There is a sequence T1,…,Tm of rooted trees, where each Ti has i+n−1 vertices, such that Ti≤Tj does not hold for any i<j≤m.

Friedman computes the first few terms of this sequence as FFF(1)=1, FFF(2)=2, and FFF(3)=5. He also estimates FFF(4) to be less than 100, while FFF(5) suddenly explodes to a very large value. Any proof that FFF(5) exists in Peano arithmetic requires at least A(10) symbols, where A(n) is the unary version of the Ackermann function, but it can be proved to exist in ACA0 with at most 10,000 symbols.

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 nth tree in the sequence contains at most n vertices, and no tree is inf-embeddable within any later tree in the sequence. TREE(3) 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 n, take TREE(n)[a] 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.

A finite version of Kruskal's theorem can be proven, which asserts that TREE(n) is finite for all n. The TREE function eventually dominates every provably recursive function of the system ACA0 + Π1
2
-BI. It grows far faster than fΓ0(n) on the fast-growing hierarchy; Friedman calculated the ordinal α where TREE(n) and fα(n) have similar growth rate (under affine transformation of input variables).

The sequence begins TREE(1)=1, TREE(2)=3; before TREE(3) increases to a value so large that many other "large" combinatorial constants, such as Friedman's n(4) and Graham's number,[b] are surpassed by comparison. A lower bound for n(4), and, hence, an extremely weak lower bound for TREE(3), is AA(187196)(1),[c] where A(x) is the single-argument version of Ackermann's function, defined as A(x)=A(x,x).

Friedman showed that TREE(3) is greater than the halting time of any Turing machine that can be proved to halt in ACA0 + Π1
2
-BI with at most 2↑↑1000 symbols,[d] where ↑↑ denotes tetration.

See also