Skip to main content
3 of 8
retag since this is not what people normally call combinatorics; edited tags
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253

How large is TREE(3) ?

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?

Feldmann Denis
  • 3.6k
  • 1
  • 20
  • 36