Return to Question

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

• Long finite sequences, Journal of Combinatorial Theory, Series A 95 Issue 1 (2001) pp. 102-144, doi:10.1006/jcta.2000.3154, author pdf

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  : "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$  ?".

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

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

• Long finite sequences, Journal of Combinatorial Theory, Series A 95 Issue 1 (2001) pp. 102-144, doi:10.1006/jcta.2000.3154, author pdf

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

Friedman, in http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf, 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 http://www.math.osu.edu/~friedman.8/pdf/finiteseq10_8_98.pdf), 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 : "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$ ?".

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

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

• Long finite sequences, Journal of Combinatorial Theory, Series A 95 Issue 1 (2001) pp. 102-144, doi:10.1006/jcta.2000.3154, author pdf

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 : "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$ ?".

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