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 Joseph Kruskal (1960); a short proof was given by Nash-Williams (1963).
Higman's lemma is a special case of this theorem, of which there are many generalizations involving trees with a planar embedding, infinite trees, and so on. A generalization from trees to arbitrary graphs is given by the Robertson–Seymour theorem.
Friedman's finite form
Friedman (2002) observed that Kruskal's tree theorem has special cases that can be stated but not proved in first-order arithmetic (though they can easily be proved in second-order arithmetic). Another similar statement is the Paris–Harrington theorem, but Friedman's finite form of Kruskal's theorem needs a much stronger fragment of second-order arithmetic to prove than the Paris-Harrington principle.
Suppose that P(n) is the statement
- There is some m such that if T1,...,Tm is a finite sequence of trees where Tk has k+n vertices, then Ti ≤ Tj for some i < j.
This is essentially a special case of Kruskal's theorem, where the size of the first tree is specified, and the trees are constrained to grow in size at the simplest non-trivial growth rate. 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 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.
Friedman also proved the following finite form of Kruskal's theorem for labelled trees with no order among siblings, parameterising on the size of the set of labels rather than on the size of the first tree in the sequence (and the homeomorphic embedding, ≤, now being inf- and label-preserving):
- For every n, there is an m so large that if T1,...,Tm is a finite sequence of trees with vertices labelled from a set of n labels, where each Ti has at most i vertices, then Ti ≤ Tj for some i < j.
The latter theorem ensures the existence of a rapidly growing function that Friedman called TREE, such that TREE(n) is the length of a longest sequence of n-labelled trees T1,...,Tm in which each Ti has at most i vertices, and no tree is embeddable into a later tree.
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 the case of n(4) it may be equal to TREE(3), see below). 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 As is A(187196), and A() is a version of Ackermann's function: A(x) = 2↑x-1x in Knuth's up-arrow notation. 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 exceeds that of the function fΓ0 in the fast-growing hierarchy, where Γ0 is the Feferman–Schütte ordinal.
^ * 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. n(1) = 3, n(2) = 11 and n(3) > 2↑7197*158386.
- Friedman, Harvey M. (2002), Internal finite tree embeddings. Reflections on the foundations of mathematics (Stanford, CA, 1998), Lect. Notes Log. 15, Urbana, IL: Assoc. Symbol. Logic, pp. 60–91, MR 1943303
- Gallier, Jean H. (1991), "What's so special about Kruskal's theorem and the ordinal Γ0? A survey of some results in proof theory", Ann. Pure Appl. Logic 53 (3): 199–260, doi:10.1016/0168-0072(91)90022-E, MR 1129778
- Kruskal, J. B. (May 1960), "Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture", Transactions of the American Mathematical Society (American Mathematical Society) 95 (2): 210–225, doi:10.2307/1993287, JSTOR 1993287, MR 0111704
- Nash-Williams, C. St.J. A. (1963), "On well-quasi-ordering finite trees", Proc. Of the Cambridge Phil. Soc. 59 (04): 833–835, doi:10.1017/S0305004100003844, MR 0153601
- Simpson, Stephen G. (1985), "Nonprovability of certain combinatorial properties of finite trees", in Harrington, L. A.; Morley, M.; Scedrov, A. et al., Harvey Friedman's Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics, North-Holland, pp. 87–117