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.

A finitary application of the theorem gives the existence of a fast-growing TREE function. TREE(3) is one of the largest simply defined finite numbers, dwarfing other large numbers such as Graham's number and googolplex.

History

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 ATR₀ (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 TREE.

Statement

Friedman's work

For a countable label set ${\displaystyle 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 ${\displaystyle X}$ has size one), Friedman found that the result was unprovable in ATR₀, thus giving the first example of a predicative result with a provably impredicative proof. This case of the theorem is still provable by Π¹
₁-CA₀, but by adding a "gap condition" to the definition of the order on trees above, he found a natural variation of the theorem unprovable in this system. Much later, the Robertson–Seymour theorem would give another theorem unprovable by Π¹
₁-CA₀.

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). Kruskal's tree theorem itself proves that ${\displaystyle \Gamma _{0}}$, the Feferman–Schütte ordinal, is well-founded; in particular, the inf-embeddable ordering on a countable label set contains a well-ordered chain of order type ${\displaystyle \Gamma _{0}}$.

Weak tree function

Suppose that ${\displaystyle P(n)}$ is the statement:

There is some ${\displaystyle m}$ such that if ${\displaystyle T_{1},\ldots ,T_{m}}$ is a finite sequence of unlabeled rooted trees where ${\displaystyle T_{i}}$ has ${\displaystyle i+n}$ vertices, then ${\displaystyle T_{i}\leq T_{j}}$ for some ${\displaystyle i<j}$.

All the statements ${\displaystyle P(n)}$ are true as a consequence of Kruskal's theorem and Kőnig's lemma. For each ${\displaystyle n}$, Peano arithmetic can prove that ${\displaystyle P(n)}$ is true, but Peano arithmetic cannot prove the statement "${\displaystyle P(n)}$ is true for all ${\displaystyle n}$". Moreover, the length of the shortest proof of ${\displaystyle P(n)}$ in Peano arithmetic grows phenomenally fast as a function of ${\displaystyle n}$, far faster than any primitive recursive function or the Ackermann function, for example.^{[citation needed]} The least ${\displaystyle m}$ for which ${\displaystyle P(n)}$ holds similarly grows extremely quickly with ${\displaystyle n}$.

Friedman defined the following function, which is a weaker version of the TREE function below. For a positive integer ${\displaystyle n}$, take ${\displaystyle {\text{FFF}}(n)}$ to be the largest ${\displaystyle m}$ so that we have the following:

There is a sequence ${\displaystyle T_{1},\ldots ,T_{m}}$ of rooted trees, where each ${\displaystyle T_{i}}$ has ${\displaystyle i+n-1}$ vertices, such that ${\displaystyle T_{i}\leq T_{j}}$ does not hold for any ${\displaystyle i<j\leq m}$.

Friedman computes the first few terms of this sequence as ${\displaystyle {\text{FFF}}(1)=1}$, ${\displaystyle {\text{FFF}}(2)=2}$, and ${\displaystyle {\text{FFF}}(3)=5}$. He also estimates ${\displaystyle {\text{FFF}}(4)}$ to be less than 100, while ${\displaystyle {\text{FFF}}(5)}$ suddenly explodes to a very large value. Any proof that ${\displaystyle {\text{FFF}}(5)}$ exists in Peano arithmetic requires at least ${\displaystyle A(10)}$ symbols, where ${\displaystyle A(n)}$ is the unary version of the Ackermann function, but it can be proved to exist in ACA₀ with at most 10,000 symbols.

TREE function

By incorporating labels, Friedman defined a far faster-growing function. For a positive integer ${\displaystyle n}$, take ${\displaystyle {\text{TREE}}(n)}$^[a] to be the largest ${\displaystyle m}$ so that we have the following:

There is a sequence ${\displaystyle T_{1},\ldots ,T_{m}}$ of rooted trees labelled from a set of ${\displaystyle n}$ labels, where each ${\displaystyle T_{i}}$ has at most ${\displaystyle i}$ vertices, such that ${\displaystyle T_{i}\leq T_{j}}$ does not hold for any ${\displaystyle i<j\leq m}$.

A finite version of Kruskal's theorem can be proven, which asserts that ${\displaystyle {\text{TREE}}(n)}$ is finite for all ${\displaystyle n}$. The TREE function eventually dominates every provably recursive function of the system ACA₀ + Π¹
₂-BI. It grows far faster than ${\displaystyle f_{\Gamma _{0}}(n)}$ on the fast-growing hierarchy; Friedman calculated the ordinal ${\displaystyle \alpha }$ where ${\displaystyle {\text{TREE}}(n)}$ and ${\displaystyle f_{\alpha }(n)}$ have similar growth rate (under affine transformation of input variables).

The sequence begins ${\displaystyle {\text{TREE}}(1)=1}$, ${\displaystyle {\text{TREE}}(2)=3}$; before ${\displaystyle {\text{TREE}}(3)}$ increases to a value so large that many other "large" combinatorial constants, such as Friedman's ${\displaystyle n(4)}$ and Graham's number,^[b] are surpassed by comparison. A lower bound for ${\displaystyle n(4)}$, and, hence, an extremely weak lower bound for ${\displaystyle {\text{TREE}}(3)}$, is ${\displaystyle A^{A(187196)}(1)}$,^[c] where ${\displaystyle A(x)}$ is the single-argument version of Ackermann's function, defined as ${\displaystyle A(x)=A(x,x)}$.

Friedman showed that ${\displaystyle {\text{TREE}}(3)}$ is greater than the halting time of any Turing machine that can be proved to halt in ACA₀ + Π¹
₂-BI with at most ${\displaystyle 2\uparrow \uparrow 1000}$ symbols,^[d] where ${\displaystyle \uparrow \uparrow }$ denotes tetration.

See also

• Paris–Harrington theorem
• Kanamori–McAloon theorem
• Robertson–Seymour theorem

Notes

^{^ a} Friedman originally denoted this function by ${\displaystyle {\text{TR}}[n]}$.

^{^ b} ${\displaystyle n(k)}$ is defined as the length of the longest possible sequence that can be constructed with a ${\displaystyle k}$-letter alphabet such that no block of letters ${\displaystyle x_{i},\ldots ,x_{2i}}$ is a subsequence of any later block ${\displaystyle x_{j},\ldots ,x_{2j}}$. For example ${\displaystyle n(1)=3}$, ${\displaystyle n(2)=11}$, and ${\displaystyle n(3)>2\uparrow ^{7197}158386}$.

^{^ c} The superscript indicates iteration. For example, ${\displaystyle A^{3}(1)}$ would mean computing ${\displaystyle A(A(A(1)))}$.

^{^ d} Friedman actually writes this as 2^[1000], which denotes an exponential stack of 2's of height 1000 using his notation.

References

Citations

Bibliography

• Friedman, Harvey M. (2002). "Internal finite tree embeddings". In Sieg, Wilfried; Feferman, Solomon (eds.). Reflections on the foundations of mathematics: essays in honor of Solomon Feferman. Lecture notes in logic. Vol. 15. Natick, Mass: AK Peters. pp. 60–91. ISBN 978-1-56881-170-3. MR 1943303.
• Gallier, Jean H. (September 1991). "What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory" (PDF). Annals of Pure and Applied Logic. 53 (3): 199–260. doi:10.1016/0168-0072(91)90022-E. MR 1129778.
• Kruskal, J. B. (May 1960). "Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture" (PDF). Transactions of the American Mathematical Society. 95 (2). American Mathematical Society: 210–225. doi:10.2307/1993287. JSTOR 1993287. MR 0111704.
• Marcone, Alberto (2005). Simpson, Stephen G. (ed.). "WQO and BQO theory in subsystems of second order arithmetic" (PDF). Reverse Mathematics. Lecture Notes in Logic. 21. Cambridge: Cambridge University Press: 303–330. doi:10.1017/9781316755846.020. ISBN 978-1-316-75584-6.{{cite journal}}: CS1 maint: periodical has ISBN (link)
• Nash-Williams, C. St. J. A. (October 1963). "On well-quasi-ordering finite trees" (PDF). Mathematical Proceedings of the Cambridge Philosophical Society. 59 (4): 833–835. Bibcode:1963PCPS...59..833N. doi:10.1017/S0305004100003844. ISSN 0305-0041. MR 0153601. S2CID 251095188.
• Rathjen, Michael; Weiermann, Andreas (February 1993). "Proof-theoretic investigations on Kruskal's theorem" (PDF). Annals of Pure and Applied Logic. 60 (1): 49–88. doi:10.1016/0168-0072(93)90192-G. MR 1212407.
• Simpson, Stephen G. (1985). "Nonprovability of certain combinatorial properties of finite trees". In Friedman, Harvey; Harrington, L. A.; Scedrov, A.; et al. (eds.). Harvey Friedman's research on the foundations of mathematics. Studies in logic and the foundations of mathematics. Amsterdam; New York: North-Holland. pp. 87–117. ISBN 978-0-444-87834-2.
• Smith, Rick L. (1985). "The Consistency Strengths of Some Finite Forms of the Higman and Kruskal Theorems". In Friedman, Harvey; Harrington, L. A. (eds.). Harvey Friedman's research on the foundations of mathematics. Studies in logic and the foundations of mathematics. Vol. 117. Amsterdam; New York: North-Holland. pp. 119–136. doi:10.1016/s0049-237x(09)70157-0. ISBN 978-0-444-87834-2.