Concept
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 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(3). A finitary application of the theorem gives the existence of the fast-growing TREE function. 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 T with a root, and given vertices v, w, call w a successor of v if the unique path from the root to w contains v, and call w an immediate successor of v if additionally the path from v to w contains no other vertex. Take X to be a partially ordered 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 precedes the label of F(v), If w is any successor of v in T1, then F(w) is a successor of F(v), and If w1, w2 are any two distinct immediate successors of v, then the path from F(w1) to F(w2) in T2 contains 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.) For a countable label set X, Kruskal's tree theorem can be expressed and proven using second-order arithmetic.