Kruskal's tree theorem

From Wikipedia, the free encyclopedia

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 proved by Kruskal (1960), and a short proof was given by (Nash-Williams 1963).

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.

[edit] 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 T₁,...,T_m is a finite sequence of trees where T_k has k+n vertices, then T_i ≤ T_j 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.

The ordinal measuring the strength of Kruskal's theorem is the small Veblen ordinal (sometimes confused with the smaller Ackermann ordinal).

[edit] References

• Friedman, Harvey M. (2002), Internal finite tree embeddings. Reflections on the foundations of mathematics (Stanford, CA, 1998), vol. 15, Lect. Notes Log., Urbana, IL: Assoc. Symbol. Logic, pp. 60--91,, MR1943303 
• Gallier, Jean H. (1991), “What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory”, Ann. Pure Appl. Logic 53 (3): 199--260, MR1129778, <http://stinet.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA290387> 
• Kruskal, J. B. (1960), “Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture”, Transactions of the American Mathematical Society 95 (2): 210–225, MR0111704, <http://links.jstor.org/sici?sici=0002-9947%28196005%2995%3A2%3C210%3AWTTTAV%3E2.0.CO%3B2-N> 
• Nash-Williams, C. St.J. A. (1963), “On well-quasi-ordering finite trees”, Proc. of the Cambridge Phil. Soc. 59: 833–835, MR0153601 

• 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