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 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.

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"₁,...,"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"₁,...,"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 smaller Ackermann ordinal).

References

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

Théorème de Kruskal — En mathématiques, le théorème des arbres de Kruskal est un résultat de théorie des graphes conjecturé en 1937 par Andrew Vázsonyi et démontré indépendamment en 1960 par Joseph Kruskal et S. Tarkowski[1], affirmant que l ensemble des arbres… … Wikipédia en Français
Joseph Kruskal — Joseph Bernard Kruskal, Jr. (born January 29 1928) is an American mathematician, statistician, and psychometrician. He was a student at the University of Chicago and at Princeton University, where he completed his Ph.D. in 1954, nominally under… … Wikipedia
Robertson–Seymour theorem — In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem[1]) states that the undirected graphs, partially ordered by the graph minor relationship, form a well quasi ordering.[2] Equivalently, every family of graphs that … Wikipedia
Martin David Kruskal — Born September 28, 1925(1925 09 28) New York City … Wikipedia
Minimum spanning tree — The minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length. Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all… … Wikipedia
List of mathematics articles (K) — NOTOC K K approximation of k hitting set K ary tree K core K edge connected graph K equivalence K factor error K finite K function K homology K means algorithm K medoids K minimum spanning tree K Poincaré algebra K Poincaré group K set (geometry) … Wikipedia
Gödel's incompleteness theorems — In mathematical logic, Gödel s incompleteness theorems, proved by Kurt Gödel in 1931, are two theorems stating inherent limitations of all but the most trivial formal systems for arithmetic of mathematical interest. The theorems are of… … Wikipedia
Undecidable problem — In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct an algorithm that leads to a yes or no answer the problem is not decidable.A decision problem is any … Wikipedia
List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… … Wikipedia
Well-quasi-ordering — In mathematics, specifically order theory, a well quasi ordering or wqo is a well founded quasi ordering with an additional restriction on sequences that there is no infinite sequence x i with x i ot le x j for all i < j . Motivation We can use… … Wikipedia

Academic Dictionaries and Encyclopedias

Kruskal's tree theorem

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Kruskal's tree theorem

Look at other dictionaries:

Share the article and excerpts

Direct link