![]() | This article may be too technical for most readers to understand.(June 2024) |
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 conjectured by Andrew Vázsonyi and proved by Joseph Kruskal ( 1960); a short proof was given by Crispin Nash-Williams ( 1963). It has since become a prominent example in reverse mathematics as a statement that cannot be proved in ATR0 (a second-order arithmetic theory with a form of arithmetical transfinite recursion).
In 2004, the result was generalized from trees to graphs as the Robertson–Seymour theorem, a result that has also proved important in reverse mathematics and leads to the even-faster-growing SSCG function, which dwarfs . A finitary application of the theorem gives the existence of the fast-growing TREE function.
The version given here is that proven by Nash-Williams; Kruskal's formulation is somewhat stronger. All trees we consider are finite.
Given a tree T with a root, and given vertices v, w, call w a successor of v if the unique path from the root to w contains v, and call w an immediate successor of v if additionally the path from v to w contains no other vertex.
Take X to be a partially ordered set. If T1, T2 are rooted trees with vertices labeled in X, we say that T1 is inf-embeddable in T2 and write if there is an injective map F from the vertices of T1 to the vertices of T2 such that:
Kruskal's tree theorem then states:
If X is well-quasi-ordered, then the set of rooted trees with labels in X is well-quasi-ordered under the inf-embeddable order defined above. (That is to say, given any infinite sequence T1, T2, … of rooted trees labeled in X, there is some so that .)
For a
countable label set X, Kruskal's tree theorem can be expressed and proven using
second-order arithmetic. However, like
Goodstein's theorem or the
Paris–Harrington theorem, some special cases and variants of the theorem can be expressed in subsystems of second-order arithmetic much weaker than the subsystems where they can be proved. This was first observed by
Harvey Friedman in the early 1980s, an early success of the then-nascent field of reverse mathematics. In the case where the trees above are taken to be unlabeled (that is, in the case where X has size one), Friedman found that the result was unprovable in
ATR0,
[1] thus giving the first example of a
predicative result with a provably impredicative proof.
[2] This case of the theorem is still provable by Π1
1-CA0, but by adding a "gap condition"
[3] to the definition of the order on trees above, he found a natural variation of the theorem unprovable in this system.
[4]
[5] Much later, the Robertson–Seymour theorem would give another theorem unprovable by Π1
1-CA0.
Ordinal analysis confirms the strength of Kruskal's theorem, with the proof-theoretic ordinal of the theorem equaling the small Veblen ordinal (sometimes confused with the smaller Ackermann ordinal). [6]
Suppose that is the statement:
All the statements are true as a consequence of Kruskal's theorem and Kőnig's lemma. For each n, Peano arithmetic can prove that is true, but Peano arithmetic cannot prove the statement " is true for all n". [7] Moreover, the length of the shortest proof of in Peano arithmetic grows phenomenally fast as a function of n, far faster than any primitive recursive function or the Ackermann function, for example.[ citation needed] The least m for which holds similarly grows extremely quickly with n.
Define , the weak tree function, as the largest m so that we have the following:
It is known that , , (about 844 trillion), (where is Graham's number), and (where the argument specifies the number of labels; see below) is larger than
To differentiate the two functions, "TREE" (with all caps) is the big TREE function, and "tree" (with all letters in lowercase) is the weak tree function.
By incorporating labels, Friedman defined a far faster-growing function. [8] For a positive integer n, take [a] to be the largest m so that we have the following:
The TREE sequence begins , , then suddenly, explodes to a value that is so big that many other "large" combinatorial constants, such as Friedman's , , and Graham's number, [b] are extremely small by comparison. A lower bound for , and, hence, an extremely weak lower bound for , is . [c] [9] Graham's number, for example, is much smaller than the lower bound , which is approximately , where is Graham's function.
Citations
Bibliography
![]() | This article may be too technical for most readers to understand.(June 2024) |
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 conjectured by Andrew Vázsonyi and proved by Joseph Kruskal ( 1960); a short proof was given by Crispin Nash-Williams ( 1963). It has since become a prominent example in reverse mathematics as a statement that cannot be proved in ATR0 (a second-order arithmetic theory with a form of arithmetical transfinite recursion).
In 2004, the result was generalized from trees to graphs as the Robertson–Seymour theorem, a result that has also proved important in reverse mathematics and leads to the even-faster-growing SSCG function, which dwarfs . A finitary application of the theorem gives the existence of the fast-growing TREE function.
The version given here is that proven by Nash-Williams; Kruskal's formulation is somewhat stronger. All trees we consider are finite.
Given a tree T with a root, and given vertices v, w, call w a successor of v if the unique path from the root to w contains v, and call w an immediate successor of v if additionally the path from v to w contains no other vertex.
Take X to be a partially ordered set. If T1, T2 are rooted trees with vertices labeled in X, we say that T1 is inf-embeddable in T2 and write if there is an injective map F from the vertices of T1 to the vertices of T2 such that:
Kruskal's tree theorem then states:
If X is well-quasi-ordered, then the set of rooted trees with labels in X is well-quasi-ordered under the inf-embeddable order defined above. (That is to say, given any infinite sequence T1, T2, … of rooted trees labeled in X, there is some so that .)
For a
countable label set X, Kruskal's tree theorem can be expressed and proven using
second-order arithmetic. However, like
Goodstein's theorem or the
Paris–Harrington theorem, some special cases and variants of the theorem can be expressed in subsystems of second-order arithmetic much weaker than the subsystems where they can be proved. This was first observed by
Harvey Friedman in the early 1980s, an early success of the then-nascent field of reverse mathematics. In the case where the trees above are taken to be unlabeled (that is, in the case where X has size one), Friedman found that the result was unprovable in
ATR0,
[1] thus giving the first example of a
predicative result with a provably impredicative proof.
[2] This case of the theorem is still provable by Π1
1-CA0, but by adding a "gap condition"
[3] to the definition of the order on trees above, he found a natural variation of the theorem unprovable in this system.
[4]
[5] Much later, the Robertson–Seymour theorem would give another theorem unprovable by Π1
1-CA0.
Ordinal analysis confirms the strength of Kruskal's theorem, with the proof-theoretic ordinal of the theorem equaling the small Veblen ordinal (sometimes confused with the smaller Ackermann ordinal). [6]
Suppose that is the statement:
All the statements are true as a consequence of Kruskal's theorem and Kőnig's lemma. For each n, Peano arithmetic can prove that is true, but Peano arithmetic cannot prove the statement " is true for all n". [7] Moreover, the length of the shortest proof of in Peano arithmetic grows phenomenally fast as a function of n, far faster than any primitive recursive function or the Ackermann function, for example.[ citation needed] The least m for which holds similarly grows extremely quickly with n.
Define , the weak tree function, as the largest m so that we have the following:
It is known that , , (about 844 trillion), (where is Graham's number), and (where the argument specifies the number of labels; see below) is larger than
To differentiate the two functions, "TREE" (with all caps) is the big TREE function, and "tree" (with all letters in lowercase) is the weak tree function.
By incorporating labels, Friedman defined a far faster-growing function. [8] For a positive integer n, take [a] to be the largest m so that we have the following:
The TREE sequence begins , , then suddenly, explodes to a value that is so big that many other "large" combinatorial constants, such as Friedman's , , and Graham's number, [b] are extremely small by comparison. A lower bound for , and, hence, an extremely weak lower bound for , is . [c] [9] Graham's number, for example, is much smaller than the lower bound , which is approximately , where is Graham's function.
Citations
Bibliography