In mathematics, Kruskal's tree theorem states that the set of finite trees over a wellquasiordered set of labels is itself wellquasiordered (under homeomorphic embedding). The theorem was conjectured by Andrew Vázsonyi and proved by Joseph Kruskal (1960); a short proof was given by NashWilliams (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.
Contents

Friedman's finite form 1

See also 2

Notes 3

References 4
Friedman's finite form
Friedman (2002) observed that Kruskal's tree theorem has special cases that can be stated but not proved in firstorder arithmetic (though they can easily be proved in secondorder arithmetic). Another similar statement is the Paris–Harrington theorem.
Suppose that P(n) is the statement

There is some m such that if T_{1},...,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 nontrivial 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 labelpreserving):

For every n, there is an m so large that if T_{1},...,T_{m} is a finite sequence of trees with vertices labelled from a set of n labels, where each T_{i} has at most i vertices, then T_{i} ≤ T_{j} 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 nlabelled trees T_{1},...,T_{m} in which each T_{i} 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.^{[1]} 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),^{[2]} and A() is a version of Ackermann's function: A(x) = 2 [x + 1] x in hyperoperation. Graham's number, for example, is approximately A^{64}(4) which is much smaller than the lower bound A^{A(187196)}(1). It can be shown that the growthrate of the function TREE exceeds that of the function f_{Γ0} in the fastgrowing hierarchy, where Γ_{0} is the Feferman–Schütte ordinal.
The ordinal measuring the strength of Kruskal's theorem is the small Veblen ordinal (sometimes confused with the smaller Ackermann ordinal).
See also
Notes
^{^ *} n(k) is defined as the length of the longest possible sequence that can be constructed with a kletter alphabet such that no block of letters x_{i},...,x_{2i} is a subsequence of any later block x_{j},...,x_{2j}.^{[3]} n(1) = 3, n(2) = 11 and n(3) > 2 [7199] 158386.
References

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,

Gallier, Jean H. (1991), ? A survey of some results in proof theory"_{0}"What's so special about Kruskal's theorem and the ordinal Γ (PDF), Ann. Pure Appl. Logic 53 (3): 199–260,



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, NorthHolland, pp. 87–117

^ http://www.cs.nyu.edu/pipermail/fom/2006March/010279.html

^ https://u.osu.edu/friedman.8/files/2014/01/EnormousInt.12pt.6_1_0023kmig3.pdf

^ https://u.osu.edu/friedman.8/files/2014/01/LongFinSeq982f0wmq3.pdf p.5, 48 (Thm.6.8)


Examples in numerical order



Expression methods



Related articles





This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.