Skip to main content
5 of 5
Tidying up
David Roberts
  • 35.5k
  • 11
  • 124
  • 349

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

Feldmann Denis
  • 3.6k
  • 1
  • 20
  • 36