- 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 proved byharvs|txt=yes|year= 1960 |authorlink=Joseph Kruskal|last=Kruskal, and a short proof was given by harv|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 .**Friedman's finite form**harvs|authorlink=Harvey Friedman|last=Friedman|year=2002|txt=yes 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 theParis-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"

_{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 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 theAckermann 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 "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 "n"-labelled 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 "completely unnoticeable" by comparison. 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 "A"'s is "A"(187196), and "A"() is a version of Ackermann's function: "A"("x") = 2↑↑...↑"x" with "x"-1 ↑s (Knuth up-arrows).

Graham's number , for example, is "unnoticeable" even in comparison to this "unnoticeable" lower bound for "TREE"(3).The ordinal measuring the strength of Kruskal's theorem is the

small Veblen ordinal (sometimes confused with the smallerAckermann ordinal ).**References***citation|id=MR|1943303

last=Friedman|first= Harvey M.

title=Internal finite tree embeddings. Reflections on the foundations of mathematics (Stanford, CA, 1998)|pages= 60--91,

series=Lect. Notes Log.|volume=15|publisher= Assoc. Symbol. Logic|publication-place= Urbana, IL|year= 2002

*citation|id=MR|1129778|last= Gallier|first= Jean H.|title= What's so special about Kruskal's theorem and the ordinal Γ_{0}? A survey of some results in proof theory|journal= Ann. Pure Appl. Logic|volume= 53 |year=1991|issue= 3|pages= 199--260|url=http://stinet.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA290387

*citation

first = J. B.

last = Kruskal

authorlink = Joseph Kruskal

year = 1960

month = May

title = Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture

journal = Transactions of the American Mathematical Society

volume = 95

issue = 2

pages = 210–225

id = MR|0111704

url = http://links.jstor.org/sici?sici=0002-9947%28196005%2995%3A2%3C210%3AWTTTAV%3E2.0.CO%3B2-N

*citation|first=C. St.J. A. |last=Nash-Williams|authorlink=Crispin St. J. A. Nash-Williams|title= On well-quasi-ordering finite trees|journal= Proc. of the Cambridge Phil. Soc. |volume=59 |year=1963|pages= 833–835|id=MR|0153601*citation|first= Stephen G. |last=Simpson

chapter= Nonprovability of certain combinatorial properties of finite trees.

editor1-first=L. A.|editor1-last= Harrington|editor2-first= M. |editor2-last=Morley|editor3-first= A. |editor3-last=Scedrov|editor4-first= S. G.|editor4-last= Simpson

title=Harvey Friedman's Research on the Foundations of Mathematics|series= Studies in Logic and the Foundations of Mathematics|publisher= North-Holland

pages =87-117|year= 1985

*Wikimedia Foundation.
2010.*