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?
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) ?
Feldmann Denis
- 3.6k
- 1
- 20
- 36