Kruskal's Tree Theorem

From Wikipedia, the free encyclopedia

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 the fast-growing TREE function. TREE(3) is largely accepted to be one of the largest simply defined finite numbers, dwarfing other large numbers such as [Grah…

From Wikipedia, the free encyclopedia

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

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 descendant of $v$ if the unique path from the root to $w$ contains $v$ , and call $w$ a child of $v$ if additionally the path from $v$ to $w$ contains no other vertex.

Take $(X,\leq _{X})$ to be a partially ordered set. If $T_{1}$ , $T_{2}$ are rooted trees with vertices labeled in $X$ , we say that $T_{1}$ is inf-embeddable in $T_{2}$ and write $T_{1}\leq T_{2}$ if there is an injective map $F$ from the vertices of $T_{1}$ to the vertices of $T_{2}$ 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 $T_{1},T_{2},\ldots$ of rooted trees labeled in $X$ , there is some $i<j$ so that $T_{i}\leq T_{j}$ .)

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,[2] thus giving the first example of a predicative result with a provably impredicative proof.[3] This case of the theorem is still provable by Π1 1-CA0, but by adding a “gap condition”[4] to the definition of the order on trees above, he found a natural variation of the theorem unprovable in this system.[5][6] 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).[7]

Suppose that $P(n)$ is the statement:

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

All the statements $P(n)$ are true as a consequence of Kruskal’s theorem and Kőnig’s lemma. 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$ ”.[8] Moreover, the length of 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.[citation needed] The least $m$ for which $P(n)$ holds similarly grows extremely quickly with $n$ .

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

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

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

A sequence of rooted trees labelled from a set of 3 labels (blue < red < green). The $n$ th tree in the sequence contains at most $n$ vertices, and no tree is inf-embeddable within any later tree in the sequence. ${\text{TREE}}(3)$ is defined to be the longest possible length of such a sequence.

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

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

Kruskal’s theorem asserts that ${\text{TREE}}(n)$ is finite for all $n$ . The TREE function eventually dominates every provably recursive function of the system ACA0 + Π1 2-BI.[10]

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

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

^ a Friedman originally denoted this function by ${\text{TR}}[n]$ . ^ b $n(k)$ is defined as the length of the longest possible sequence that can be constructed with a $k$ -letter alphabet such that no block of letters $x_{i},\ldots ,x_{2i}$ is a subsequence of any later block $x_{j},\ldots ,x_{2j}$ .[12] For example $n(1)=3$ , $n(2)=11$ , and $n(3)>2\uparrow ^{7197}158386$ . ^ c The superscript indicates iteration. For example, $A^{3}(1)$ would mean computing $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.[13]