Pardon my ignorance, but isn't TREE(3) a finite number? -Dylan Thurston

It is my understanding as well that TREE(3) is finite (Proof that TREE(n) where n >= 3 is finite?).

However, I have seen statements such as:

TREE(3) is known to exceed the $\Gamma_0$-level, which is much higher than the $\epsilon_0$-level. -Source

It is also my understanding that $\omega < \epsilon_0 < \Gamma_0$ (where $\omega$, $\epsilon_0$ & $\Gamma_0$ are transfinite).

If $\Gamma_0<TREE(3)$, wouldn't that imply TREE(3) is transfinite?

  • 3
    $\begingroup$ I think this refers not to the size of $\operatorname{TREE}(3)$ itself, but of the power of the formal system required to show that the expression “$\operatorname{TREE}(3)$” is meaningfully defined. Recall that the definition of $\operatorname{TREE}$ begins “the maximum value such that…”. In general there may not be such a maximum value; its existence requires a proof, typically an inductive proof. Some axiomatic systems are only strong enough to provide induction over a set of size $\epsilon_0$; others, more powerful, can induct over larger sets. $\endgroup$ – MJD Dec 18 '18 at 22:14
  • 1
    $\begingroup$ I have no idea! $\endgroup$ – MJD Dec 19 '18 at 0:29
  • 2
    $\begingroup$ The claim is made in the context of a specific fast growing hierarchy of functions $f_\alpha\!:\mathbb N\to\mathbb N$. I assume that what they mean is that $f_{\Gamma_0}(3)<\mathrm{TREE}(3)$. $\endgroup$ – Andrés E. Caicedo Dec 19 '18 at 2:05
  • 1
    $\begingroup$ (The question on MO linked to at the beginning explains this for a different $\alpha$.) $\endgroup$ – Andrés E. Caicedo Dec 19 '18 at 2:09
  • 1
    $\begingroup$ @AndrésE.Caicedo I think your comments are very nearly the answer to the question, so feel free to expand them to an answer. $\endgroup$ – Mark S. Dec 19 '18 at 2:42

This is indeed a confusing bit of language. $TREE(3)$ is indeed finite. I think the later comment by Peter clears things up:

"For example, Graham's number is approximately $f_{\omega+1}(64)$, so we say that Graham's number is at level $f_{\omega+1}$, or [for] short at the $\omega+1$-level."

Basically, we want to say that a number is "at level $\kappa$" if it is $f_\kappa(s)$ for some "small" $s$ (e.g. here $64$ is considered small). Note that this is a subjective distinction - what's the least non-small number? :P - but it still gives a sense of the size of the number involved. The point, roughly, is to say: $TREE(3)$ is so huge that, even with a special symbol for $f_{\Gamma_0}$, it is still infeasible to express $TREE(3)$.

There are various precise versions of this - e.g. the statement "$f_{\Gamma_0}(3)<TREE(3)$" (per Andres) is a perfectly precise statement, and (I believe) is known to be true - but I think it's better to view this as a general piece of descriptive language


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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