43
$\begingroup$

Friedman, in _Lectures notes on enormous integers shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman function and exponentiation denotes iteration). But actually, using the fast-growing hierarchy, $n(p)$ is smaller than $f_{\omega^{\omega^\omega}}(p)$, shown by Friedman in

while it seems that TREE grows faster than $f_{\Gamma_0}$ (${\Gamma_0}$ being the Feferman-Schütte ordinal). So it could well be that in fact TREE(3) is larger than, say, n(n(4)), or even any number expressible by iterations of n. What is known on this question?

For reference, I should have added that TREE(3) is the incredibly (at first, or even second look) large answer to the question: "what is the length of the longest sequence $(T_1,T_2,T_3,\dots,T_n)$ of labeled trees such that $T_k$ has at most $k$ nodes labeled $a$, $b$, or $c$, and $T_i$ is not a subtree of $T_j$ for $i < j$?".

Here, trees are rooted trees, and are treated as poset on their sets of vertices. A tree $T$ is called a subtree of $T'$ if there is an inf-preserving embedding from $T$ into $T'$, (that is, an injective map $h:Vertices(T) \to Vertices(T')$ such that $h(\inf(x,y)) = \inf((h(x), h(y))$) that respects the labeling by $a$ or $b$.

$\endgroup$
11
  • 18
    $\begingroup$ Pardon my ignorance, but isn't TREE(3) a finite number? As such, it can't possibly be larger than "any number expressible by iterations of n", can it? $\endgroup$ Apr 12, 2012 at 11:58
  • 4
    $\begingroup$ Out of interest, what is the theoretical significance of proving integers like TREE(3) to be "incomprehensibly large"? $\endgroup$
    – Colin Reid
    Apr 14, 2012 at 7:27
  • 25
    $\begingroup$ The answer is that such integers cannot be proved to "exist" in usual first-order theory of arithmetic like PA, giving examples of undecidability results much more natural than Gödel's ones $\endgroup$ Apr 14, 2012 at 12:00
  • 3
    $\begingroup$ and you might want to include the wiki page en.wikipedia.org/wiki/Kruskal%27s_tree_theorem for more background, there is also googology.wikia.com/wiki/TREE_sequence. $\endgroup$
    – Wolfgang
    Nov 15, 2014 at 9:41
  • 4
    $\begingroup$ @FeldmannDenis Belated, but for the record: $\mathsf{PA}$ can prove that $\mathsf{TREE}(3)$ exists, and indeed for each $n$ $\mathsf{PA}$ can prove that $\mathsf{TREE}(n)$ exists. This is because the definition of the $\mathsf{TREE}$ function is sufficiently simple that $\mathsf{PA}$ (or indeed vastly less) can verify each instance of it. What $\mathsf{PA}$ can't prove is "$\forall n$, $\mathsf{TREE}(n)$ exists." Note that the same situation holds re: consistency (for each $n$ $\mathsf{PA}$ proves "there is no contradiction in $\mathsf{PA}$ of length $<n$," Godel's second notwithstanding). $\endgroup$ Apr 5, 2022 at 15:28

5 Answers 5

30
$\begingroup$

I believe I can state with some confidence that TREE(3) is larger than $f_{\vartheta (\Omega^{\omega}, 0)} (n(4))$, given a natural definition of $f$ up to $\vartheta (\Omega^{\omega}, 0)$. I can state with certainty that TREE(3) is larger than $H_{\vartheta (\Omega^{\omega}, 0)} (n(4))$, where H is a certain version of the Hardy hierarchy.

To obtain this result, I will first define a version of TREE(n) for unlabeled trees:

Let tree(n) be the length of the longest sequence of unlabeled rooted trees $T_1, T_2, \ldots, T_m$ such that $T_i$ has less than or equal to $n+i$ vertices and for no $i, j$ with $i < j$ do we have $T_i$ homeomorphically embeddable into $T_j$. (Note the term "embeddable" rather than "subtree"; the terms are different, and I believe using "subtree" would lead to infinite sequences.)

In order to obtain a long sequence of trees, we will define a well-order on unlabeled rooted trees. This definition will be by induction on the sum of the heights of the two trees being compared.

Define an immediate subtree of a rooted tree $T$ to be a full subtree starting at one of its children.

Given two rooted trees $S, T$, we define $S = T$ if the two trees are identical. We define $S \leq T$ if $S = T$ or $S < T$.

Given two rooted trees $S, T$, we define $ < $ as follows. Say $S < T$ if $S \leq T_i$, where $T_i$ is an immediate subtree of $T$. Similarly, say $T < S$ if $T \leq S_i$, where $S_i$ is an immediate subtree of $S$.

Otherwise, compare the number of children of $S$ and $T$. If $S$ has more children than $T$, then $S > T$, and vice versa.

Otherwise, suppose $S$ and $T$ both have $n$ children. Let $S_1, S_2, \ldots, S_n$ and $T_1, T_2, \ldots T_n$ be the immediate subtrees of $S$ and $T$ respectively, ordered from smallest to largest. Compare $S_1$ to $T_1$, then $S_2$ to $T_2$, etc., until we get a pair of unequal trees $S_i$ and $T_i$. If $S_i > T_i$ then $S > T$, and vice versa. Of course, of all pairs of immediate subtrees are equal, then $S$ and $T$ will be equal.

This gives a linear order on unlabeled rooted trees, and one can prove that this is a well-order. Further, this well-ordering has order type $\vartheta(\Omega^\omega,0)$. This definition is a modification of a well-ordering of ordered rooted trees due to Levitz, and expounded on in papers by Jervell.

From this well-ordering we can define fundamental sequences for ordinals up to $\vartheta (\Omega^{\omega}, 0)$. Simply put, given an ordinal $\alpha$, let $\alpha[n]$ be the largest ordinal less than $\alpha$ corresponding to a tree of $n$ vertices or less.

From this, we can define our version of the Hardy hierarchy:

$H_0(n) = n$

$H_{\alpha + 1}( n) = H_{\alpha}( n+1)$

For $\alpha$ a limit ordinal, $H_{\alpha}( n) = H_{\alpha[n+1]}( n+1)$

Note the $n+1$'s in the last line - this differs from the usual values of $n$. Of course, this will only make the functions larger.

$H_{\alpha}( n)$ for $\alpha < \vartheta (\Omega^{\omega}, 0)$ is the final index $m$ in the sequence of trees $T_n, T_{n+1}, \ldots, T_m$ where $T_n$ corresponds to $\alpha$ and $T_i$ is the largest tree with at most $i$ vertices that is smaller than $T_{i-1}$, and $T_m$ is the tree with one vertex. Thus $H_{\vartheta (\Omega^{\omega}, 0)}( n)$ will be the final index $m$ in the sequence of trees $T_{n+1}, T_{n+2}, \ldots, T_m$ where $T_{n+1}$ is arbitrary.

Thus tree(n) $\geq H_{\vartheta (\Omega^{\omega}, 0)}( n) - n$.

So where does TREE(3) come in? Harvey Friedman himself explains in a post to the Foundations of Mathematics message boards:

http://www.cs.nyu.edu/pipermail/fom/2006-March/010260.html

In the post he explains why a proof of the theorem "TREE(3) exists" in the theory $ACA_0 + \Pi^1_2\text{-}BI$ must have more than $2\uparrow\uparrow 1000$ symbols. He does this by showing that TREE(3) must be very large - specifically, he constructs a sequence of more than $n(4)$ rooted trees labeled from {1,2,3} such that $T_i$ has at most $i$ vertices, for no $i, j$ with $i < j$ do we have $T_i$ homeomorphically embeddable into $T_j$, and each tree contains either a 2 label or a 3 label. We can obviously continue this with tree($n(4)$) trees with all labels 1. Thus we have

TREE(3) $\geq$ tree$(n(4)) + n(4) \geq H_{\vartheta (\Omega^{\omega}, 0)}(n(4))$

In fact, we can do somewhat better than this; we can replace the $n(4)$ above by $F(4)$, where $F(4)$ is defined as the length of the longest sequence of sequences $x_1, x_2, \ldots x_n$ from {1,2,3,4} such that $x_i$ has length $i+1$ and for no $i,j$ with $i < j$ do we have $x_i$ a subsequence of $x_j$. I can prove much better bounds for $F(4)$ than Friedman's lower bound for $n(4)$; specifically,

$F(4) > f_{\omega^2 + \omega + 1}f_{\omega^2 + \omega + 1}f_{\omega^2 + \omega}f_{\omega^2 + 1}f_{\omega^2 + 1}f_{\omega^2}f_{ \omega + 1}f_{ \omega + 1}f_{\omega}(30)$

But such specificity is perhaps unwarranted given how far from TREE(3) it may be.

$\endgroup$
13
$\begingroup$

I should perhaps have asked this question to Harvey Friedman himself... Anyway, a reasonable answer is given on the talk page for Wikipedia article on Kruskal tree theorem, where one can find this quotation (from H. Friedman himself)

Also, numbers derived from Goodstein sequences or Paris/Harrington Ramsey theory, although bigger than n(4), are also completely UNNOTICEABLE in comparison to TREE[3].

To clarify my remark "any number expressible by iterations of n" in the question (and answer Dylan Thurston's comment), I meant that TREE(3) is bigger than expressions like $n^{n^{n(100)}(100)}(100)$, say, where again exponentiation means iteration, and the whole expression has no more than $n(4)$ symbols; this would indeed be true if, for instance, as suggested, we had TREE(3)$>f_{\Gamma_0}(n(4))$. For reference, I should have added that TREE(3) is the incredibly (at first, or even second look) large answer to the question:

which is the length of the longest sequence $(T_2,T_3,T_4,\dots,T_n)$ of labeled trees such that $T_k$ has at most $k$ nodes labeled $a$ or $b$, and $T_i$ is not a subtree of $T_j$ for $i < j$?

$\endgroup$
2
  • $\begingroup$ Incidentally, what is the significance of the number 3 in the definition of TREE(3)? $\endgroup$
    – S. Carnahan
    Apr 14, 2012 at 11:22
  • 2
    $\begingroup$ TREE(3) is about 3-labeled trees (when you include $T_1$) $\endgroup$
    – Woett
    Apr 14, 2012 at 11:54
7
$\begingroup$

(Following are two comments, posted this way because I ("r.e.s.") cannot post comments directly.)

Comment on the answer by "Deedlit":

He does this by showing that TREE(3) must be very large - specifically, he constructs a sequence of more than $n(4)$ rooted trees labeled from {1,2,3} such that $T_i$ has at most $i$ vertices, for no $i,j$ with $i \lt j$ do we have $T_i$ homeomorphically embeddable into $T_j$, and each tree contains either a 2 label or a 3 label. We can obviously continue this with tree$(n(4))$ trees with all labels 1.

That's not quite right. His first tree $T_1$ uses label 3 (so this label cannot be used later at all), followed by more than $n(4)$ trees using labels 1,2 -- not, as you wrote, using labels 2,3. It's because of the way these latter {1,2}-labelled trees are constructed, that they can nevertheless be followed by a long sequence of trees using only label 1. (I show the beginning of his sequence in my other comment below, using bracket expressions in which the bracket-types (),[],{} correspond to his labels 1,2,3 respectively.)

In fact, we can do somewhat better than this; we can replace the $n(4)$ above by $F(4)$, where $F(4)$ is defined as the length of the longest sequence of sequences $x_1,x_2,…x_n$ from {1,2,3,4} such that $x_i$ has length $i+1$ and for no $i,j$ with $i \lt j$ do we have $x_i$ a subsequence of $x_j$.

Actually, we can do even better, although these may be relatively "small" adjustments: by playing with various ways to start a long embedding-free sequence, one can improve upon the sequence constructed by Friedman (displayed below), but still using his method of coding $n()$- or $F()$-type longest word-sequences via certain subtrees. For example, one can find sequences that demonstrate (in Deedlit's notation)

TREE(3) $\ \geq \ $ tree$(N) + \\ N \ \geq \ H_{\vartheta (\Omega^{\omega}, 0)}(N)$

where

$N \ = \ F_\omega F_\omega F_\omega F_{\omega+1} F_\omega F_\omega \ F(4)$

with $F_\alpha$ being a fast-growing hierarchy that begins with $F_0 = F$, rather than beginning as usual with $F_0(x) = x+1$. (Friedman showed that $F$ eventually dominates every $f_{\lt \omega^\omega}$ in the usual fast-growing hierarchy.)

I've posted a very terse derivation-sketch of this result.


Comment on the answer by "Feldman Denis":

[TREE(3) is] the length of the longest sequence $(T_2,T_3,T_4,…,T_n)$ of labeled trees such that $T_k$ has at most $k$ nodes labeled $a$ or $b$, and $T_i$ is not a subtree of $T_j$ for $i \lt j$.

Rather than "is not a subtree of", that should be "is not homeomorphically embeddable into", which is a very much more stringent requirement. (There might not even exist a longest such sequence in the less-stringent case. A similar situation occurs for Friedman's $n()$ and $F()$ functions concerning word-sequences: these use "is not a subsequence of" rather than the less-stringent "is not a substring of", there being no longest word-sequence in the latter case.) With this correction, and by starting with $T_2$, the length of the resulting sequence will of course be TREE(3) - 1.

A convenient way of representing these trees is to use nested bracket expressions (well-formed in the usual way with pairs of matching brackets) involving only three bracket-types -- say (),[],{} -- each tree being uniquely represented by a nest of such brackets (up to isomorphism with respect to sibling order). A lower bound on TREE(3) is then the length of a longest sequence $(X_1,X_2,…,X_n)$ of nests such that each $X_k$ has at most $k$ bracket pairs and no $X_i$ is embedded in a later $X_j$, where $X$ is embedded in $Y$ means that $X$ can be obtained from $Y$ by erasing zero or more pairs of matching brackets. (Thus, if $X$ is not embedded in $Y$, then the tree represented by $X$ is not inf-and-label-preserving embeddable into the tree represented by $Y$; the converse, however, does not hold.)

Because $X_1$ must be some single bracket-pair which cannot then appear in any later nest in an embedding-free sequence, it may be assumed that $X_1=\ ${}, with all later nests using only the two bracket-types (),[]. Also, note that TREE(3) concerns trees with unordered siblings, so, for example, the nests ([]()) and (()[]) are not regarded as distinct. (Some authors have treated wqo's for rooted trees with ordered siblings, with corresponding "longest sequence" results.)

To illustrate the use of bracket expressions, here is a representation of the initial tree sequence used by Friedman to prove the lower bound mentioned by the OP:

T1  {}
T2  [[]]
T3  [()()]
T4  [((()))]
T5  ([][][][])
T6  ([][][](()))
T7  ([][](()()()))
T8  ([][](()(())))
T9  ([][](((((()))))))
T10 ([][]((((())))))
T11 ([][](((()))))
T12 ([][]((())))
T13 ([][](()))
T14 ([][]())
...

NB: It should be noted that the article linked by the OP does not treat Friedman's TREE function, but a rather different function TR. The confusion may be partly due to the fact that "TR" is also what Friedman called the TREE function before he changed it to the latter name in a follow-up article to the one mentioned in Deedlit's posting.

$\endgroup$
2
  • $\begingroup$ Thanks for your comments, r.e.s. I believe you misread what I wrote; I meant that every tree in the initial part of the sequence had at least one 2 label or 3 label, not that it consisted solely of 2 and 3 labels. This is of course enough to imply that no tree in the initial part will be homeomorphically embeddable into a tree in the later part with solely 1 labels. Very nice construction of N. One can do even better; I can prove that TREE(3) > tree(tree(tree(6))), and tree(tree(6)) will certainly be much greater than your N. $\endgroup$
    – Deedlit
    Jul 30, 2012 at 18:02
  • $\begingroup$ You actually have it reversed with regard to more stringent versus less stringent. The less stringent definition of $T_i < T_j$ will mean fewer sequences satisfy the requirement, so if we define SUBTREE(n) as the longest possible sequence using this less stringent definition, SUBTREE(n) will exist and SUBTREE(n) <= TREE(n). It's an interesting question as to what the growth rate of SUBTREE(n) is. Regarding the two versions of n(k), the substring definition is more stringent, and that version of n(k) is infinite for k >= 3. $\endgroup$
    – Deedlit
    Jul 30, 2012 at 18:10
4
$\begingroup$

Chris Bird has a series of articles that list functions with high growth rates, all the way to the Bachmann-Howard ordinal. They're all over my head, but they might be useful for getting a more accurate (although still extremely broad) approximation of TREE(3).

$\endgroup$
1
  • 4
    $\begingroup$ Chris Bird's notations are very interesting, but they serve much the same function as the fast-growing hierarchy does. Note that I had to choose a very specific definition of fundamental sequences for the Hardy hierarchy to get proven inequalities; Comparing TREE(3) to Bird's notation, or indeed to the Hardy hierarchy for a different definition of fundamental sequences, seems quite difficult. And then there's the problem of finding an upper bound for TREE(3); so far, I am at a loss. The problem is not really notational, as the Hardy and fast-growing hierarchies extend quite far. $\endgroup$
    – Deedlit
    Sep 22, 2012 at 2:54
2
$\begingroup$

I'd like to post an improvement of what originally posted here, by Deedlit and myself. Another related post is here, which shows an even better bound, though there are questions how the order in the last post exaclty works, i.e. it does not contain evidence why it should be like this. Anyway, we start with these trees:

T1  {}
T2  [[]]
T3  [()()]
T4  [(()())]
T5  [(((())))]
T6  ([((()))][])
T7  ([((()))]()())
T8  ([((()))]()())
T9  ([((()))]((())))
T10 ([((()))](()()))
T11 ([((()))](((()))))
T12 ([((()))]((())))
T13 ([((()))](()))
T14 ([((()))]())
T15 ([((()))])
T16 ([(())][(())][(())][(())][(())])
T17 ([(())][(())][(())][(())]([()][]))
T18 ([(())][(())][(())][(())]([()][]))
T19 ([(())][(())][(())][(())]([()]()()))
T20 ([(())][(())][(())][(())]([()]())[()])
T21 ([(())][(())][(())][(())]([()]())(([])))
T22 ([(())][(())][(())][(())]([()]())([][][]))
T23 ([(())][(())][(())][(())]([()]())([][])([]))
T24 ([(())][(())][(())][(())]([()]())([][])[][][])
T25 ([(())][(())][(())][(())]([()]())([][])[][]()())
T26 ([(())][(())][(())][(())]([()]())([][])[][]((())))
T27 ([(())][(())][(())][(())]([()]())([][])[][](()))
T28 ([(())][(())][(())][(())]([()]())([][])[][]())
T29 ([(())][(())][(())][(())]([()]())([][])[][])
T30 ([(())][(())][(())][(())]([()]())([][])[]#)

where # is the first tree of $\mathrm{tree}(8)$.

This is very important. We can now reduce # for $\mathrm{tree}(8)$ steps. In general, we can reduce [] for as many steps as it allows. Generally this will be comparable to the number of brackets allowed in total.

This means that we can preform basic recursion around tree already. We can spawn a ([]) to $n$ []s, so this is already at $f_{1}$ where $f_0 = \mathrm{tree}$. We can spawn a () to $n$ ([])s so it is at at $f_2$. Similiarly, we can take ([]#) for any tree # and reduce it just like as we would as in tree. We can reach $f_{\vartheta(\Omega^{\omega})}(n)$ in the modified hierarchy this way. $f$ is a certain variant of the fast growing hierarchy.

But $f_{\vartheta(\Omega^{\omega})}(n)$ in the modified hierarchy is just $F_{\vartheta(\Omega^{\omega},0)2}(n)$, where $F$ is a certain variant of the normal fast growing hierarchy (with $F_0=n+1$.)

Similiarly, we have ([][]#), reaching $F_{\vartheta(\Omega^{\omega})3}(n)$ at ([][][]) and $F_{\vartheta(\Omega^{\omega})\omega}(n)$ at (([])). $F_{\vartheta(\Omega^{\omega})(\omega+1)}(n)$ is reached by (([])[]), $F_{\vartheta(\Omega^{\omega})(\omega2)}(n)$ by (([])([])), and $F_{\vartheta(\Omega^{\omega})\omega^2}(n)$ at (()). With # we work in the product, reaching $F_{\vartheta(\Omega^{\omega})^2}(n)$ at (([][])) and $F_{\vartheta(\Omega^{\omega})^\omega}(n)$ at ((([]))).

A pattern emerges. We can in fact reach $F_{\varepsilon_{\vartheta(\Omega^{\omega})+1}}$ at [()] which would evaluate to (((...((([])))...))) with as many pairs as possible.

We see that TREE(3) is already far beyond the tree function itself.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.