Kruskal's tree theorem
Encyclopedia
In mathematics
, Kruskal's tree theorem states that the set of finite tree
s over a well-quasi-ordered
set of labels is itself well-quasi-ordered (under homeomorphic embedding). The theorem was proved by
, and a short proof was given by .
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
.
). 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
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):
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. 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 with x-1 ↑s (Knuth up-arrows
). 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
.
The ordinal measuring the strength of Kruskal's theorem is the small Veblen ordinal
(sometimes confused with the smaller Ackermann ordinal
).
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Kruskal's tree theorem states that the set of finite tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
s over a well-quasi-ordered
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 \not \le x_j for all i...
set of labels is itself well-quasi-ordered (under homeomorphic embedding). The theorem was proved by
, and a short proof was given by .
Higman's lemma
Higman's lemma
In mathematics, Higman's lemma states that the set of finite sequences over a finite alphabet, as partially ordered by the subsequence relation, is well-quasi-ordered...
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
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...
.
Friedman's finite form
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 arithmeticSecond-order arithmetic
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. It was introduced by David Hilbert and Paul Bernays in their...
). 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
Primitive recursive function
The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions...
or the Ackermann function
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...
for example.
Friedman also proved the following finite form of Kruskal's theorem for labelled trees
Tree (set theory)
In set theory, a tree is a partially ordered set In set theory, a tree is a partially ordered set (poset) In set theory, a tree is a partially ordered set (poset) (T, In set theory, a tree is a partially ordered set (poset) (T, ...
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. 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 with x-1 ↑s (Knuth up-arrows
Knuth's up-arrow notation
In mathematics, Knuth's up-arrow notation is a method of notation for very large integers, introduced by Donald Knuth in 1976. It is closely related to the Ackermann function and especially to the hyperoperation sequence. The idea is based on the fact that multiplication can be viewed as iterated...
). Graham's number
Graham's number
Graham's number, named after Ronald Graham, is a large number that is an upper bound on the solution to a certain problem in Ramsey theory.The number gained a degree of popular attention when Martin Gardner described it in the "Mathematical Games" section of Scientific American in November 1977,...
, 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
Fast-growing hierarchy
In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy is an ordinal-indexed family of rapidly increasing functions fα: N → N...
, where Γ0 is the Feferman–Schütte ordinal
Feferman–Schütte ordinal
In mathematics, the Feferman–Schütte ordinal Γ0 is a large countable ordinal.It is the proof theoretic ordinal of several mathematical theories, such as arithmetical transfinite recursion.It is named after Solomon Feferman and Kurt Schütte....
.
The ordinal measuring the strength of Kruskal's theorem is the small Veblen ordinal
Small Veblen ordinal
In mathematics, the small Veblen ordinal is a certain large countable ordinal, named after Oswald Veblen. It is occasionally called the Ackermann ordinal, though the Ackermann ordinal described by is somewhat smaller than the small Veblen ordinal....
(sometimes confused with the smaller Ackermann ordinal
Ackermann ordinal
In mathematics, the Ackermann ordinal is a certain large countable ordinal, named after Wilhelm Ackermann. The term "Ackermann ordinal" is also occasionally used for the small Veblen ordinal, a somewhat larger ordinal....
).