5
$\begingroup$

I'm interested in where TREE(n) would rank on the fast growing hierarchy. I've read that the small tree(n) function is bound by the Small Veblen Ordinal. Given that TREE(n) grows faster, where would TREE(n) fall in the FGH?

Assuming Friedman's definition of TREE(n):

TREE(n) is the length of the longest sequence of trees T1,T2, … labeled from {1,2,3,..,n} such that, for all i, Ti has at most i vertices, and for all i, j such that $i<j$, there is no label-preserving homeomorphic embedding from Ti into Tj.

$\endgroup$
8
$\begingroup$

The key piece of information that determines the growth rate of TREE(n) is the length, or maximal order type, of $\omega$-labeled rooted trees ordered by label and infemum preserving embedding. Now, this ordering is a well-partial order, but not a well order, so it does not immediately correspond to an ordinal. There is of course the rank of the ordering, but that is just $\omega$, and it is not what we want. Rather, we want the maximal order type of all extensions of this ordering to linear orders (hence well orders). This is what is called the length of the ordering. (Note: It is a theorem that the supremum over all order types of linear extensions of a well-partial order is in fact the order type of a linear extension of that well-partial order, so it makes sense to talk about the maximum.)

The length of the TREE ordering turns out to be $\theta (\Omega^\omega \omega, 0)$. We can show that this is a lower bound for the length by exhibiting a linear extension with this order type. Consider the following ordering:

Given $\omega$-labeled rooted trees $S$ and $T$, inductively use the following rules in order:

  1. Define a child subtree of a tree $T$ to be the full subtree whose root is a child of $T$'s root. If $S$ is less than or identical to a child subtree of $T$, then $S < T$; if $T$ is less than or identical to a child subtree of $S$, then $T < S$.

  2. Otherwise, if $S$'s root has a larger label than $T$'s root, then $S > T$. If $T$'s root has a larger label than $S$'s root, then $T > S$.

  3. Otherwise, if $S$'s root has more children than $T$, then $S > T$. If $T$'s root has more children than $S$, $T > S$.

  4. Otherwise, compare the children of $S$'s root with the children of $T$'s root, starting from the smallest (using this ordering), then the second smallest, and so on. Whichever tree first has a larger child, that tree is bigger; otherwise, the trees are identical, so they are equal.

With some work one can show that this is a well-ordering of order type $\theta(\Omega^\omega \omega,0)$ that respects the ordering under label and infemum preserveing embedding.

That $\theta(\Omega^\omega \omega,0)$ is an upper bound as well was proven in 1979 by Diana Schmidt in her thesis. More generally, the TREE ordering using labels from an ordinal $\alpha$ has length $\theta(\Omega^\omega \alpha, 0)$.

The other part is using this fact to prove that TREE(n) grows at roughly $F_{\theta(\Omega^\omega \omega,0)}(n)$ in the fast-growing hierarchy.

The lower bound is again easier. First, given a tree $T$ and a nonnegative integer $n$, define a finite sequence of trees $S(T,n)_i$ starting from $i=n$ by setting $T_n = T$, and defining $T_{i+1}$ to be the largest tree less than $T_i$ (using the above ordering) with at most $i+1$ vertices. Since the above ordering is a well-ordering, the sequence reaches the root tree after some finite number of steps, and the sequence ends there.

Next, define $t(\alpha)$ to be the tree that corresponds to the ordinal $\alpha$ in the above well-ordering of trees, and let $T_\alpha(n)$ be the index of the final tree in the sequence $S(t(\alpha),n)$. It is then immediate that $T_\alpha(n)$ satisfies:

$T_0(n) = n$

If $t(\alpha)$ has at most $n+1$ vertices, $T_{\alpha+1}(n) = T_\alpha(n+1)$

If $\alpha$ is limit, then $T_\alpha(n) = T_{\alpha[n+1]}(n+1)$, where $\alpha[n]$ is defined to be the ordinal such that $t(\alpha[n])$ is the largest tree less than $t(\alpha)$ with at most $n$ vertices.

Note that this is very similar to the Hardy hierarchy $H_\alpha(n)$ using the same definition of $\alpha[n]$, except for the second rule where $t(\alpha)$ is required to have less than or equal to $n+1$ vertices. So long as this is true, then $T_\alpha(n) \ge H_\alpha(n)$. Since $F_\alpha(n) \approx H_{\omega^\alpha}(n)$, for $\varepsilon$-numbers $\alpha$ we will have $T_\alpha(n) \ge H_\alpha(n) \approx F_\alpha(n)$. Now, $\theta(\Omega^\omega \omega,0)$ does not correspond to a tree, but one can see that under the above rules $T_{\theta(\Omega^\omega \omega,0)}(n)$ will be the final index of the sequence $S(T,n)$ where $T$ is simply chosen to be the largest tree with at most n vertices. Therefore $TREE(n) \ge T_{\theta(\Omega^\omega \omega,0)}(n+1) \approx F_{\theta(\Omega^\omega \omega,0)}(n+1)$.

The other direction is harder; I don't know the specifics, but from talking with Andreas Weiermann, upper bounds can be extracted "subrecusively" using the length of the ordering, but unfortunately this work remains unpublished. I believe the upper bounds will be in the same general range as the lower bound, either $F_{\theta(\Omega^\omega \omega,0)}(cn)$ or perhaps $F_{\theta(\Omega^\omega \omega,0)+1}(n)$. So I think it is reasonable to say that TREE(n) lies at $F_{\theta(\Omega^\omega \omega,0)}(n)$ in the fast-growing hierarchy.

$\endgroup$
  • $\begingroup$ Would it be possible to prove that ${\rm TREE}(n)\le f_{\vartheta(\Omega^{\omega+1})}(n)$, for example? $\endgroup$ – Simply Beautiful Art Nov 24 '17 at 18:08

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.