How does TREE(3) grow to get so big? (Laymen explanation)

I'll try to answer. It's a rather difficult question since (1) answering why something in mathematics is the way it is is troublesome; and (2) this subject has technical details that make it difficult to give a "layman's explanation".

It appears that you have watched David Metzler's videos on fast-growing functions, so you know a little about ordinals, and specifically on how they give rise to fast-growing functions. I will first describe a function on ordinals that outputs fast-growing functions; second, I will explain how this relates to the tree(n) function, which is about sequences of unlabelled trees; finally, I will show how the TREE(n) function, which is about labelled trees, grows even faster. So bear with me here.

First, let us assume that for every limit ordinal (a limit ordinal is an ordinal with no predecessor) in a sufficiently large initial segment of ordinals, we have defined a fundamental sequence; that is, an increasing sequence of ordinals whose limit is the original ordinal. So for $\omega$ we can take the sequence {0, 1, 2, ...}; for $\omega * 2$ we can take the sequence $\\{ \omega, \omega + 1, \omega + 2, \ldots, \\}$; for $\omega ^ 2$, we can take the sequence $\\{ 0, \omega, \omega * 2, \ldots, \\}$; and so on. For an ordinal $\alpha$, define $\alpha [n]$ to be the $n$th element of the fundamental sequence of $\alpha$ when $\alpha$ is a limit ordinal, and the predecessor of $\alpha$ when $\alpha$ is a successor ordinal.

Notice that $\alpha[n] < \alpha$ for all ordinals $\alpha$ and natural numbers $n$. So $\alpha, \alpha[n], \alpha[n][n+1], \alpha[n][n+1][n+2], \ldots$ is a strictly decreasing sequence of ordinals. A defining property of ordinals is that there is no infinite decreasing sequence of ordinals; so for $\alpha > 0$, there exists a minimal natural number $m$ so that $\alpha[n][n+1] \ldots [m] = 0$. Define $H(\alpha,n)$ to be this minimal $m$.

Some examples:

$1[n] = 0$ for all $n$, so $H(1,n) = n$.

$2[n] = 1, 2[n][n+1] = 0$ for all $n$, so $H(2, n) = n+1$.

Similarly, $m[n][n+1] \ldots [n+m-1] = 0$, for all $n$, so $H(m, n) = n + m - 1$.

$\omega[n] = n, \omega[n][n+1] = n-1, \ldots, \omega[n][n+1] \ldots [2n] = 0$, so $H(\omega, n) = 2n$.

$(\omega+1)[n] = \omega, (\omega+1)[n][n+1] = n+1, (\omega+1)[n][n+1] \ldots [2n+2] = 0$, so $H(\omega+1, n) = 2n + 2$.

Similarly, $H(\omega+m, n) = 2n + 2m$.

$(\omega * 2)[n] = \omega + n, (\omega*2)[n]\ldots[2n] = \omega, (\omega*2)[n]\ldots[2n+1] = 2n+1, (\omega*2)[n]\ldots[4n+2] = 0$, so $H(\omega*2, n) = 4n + 2$.

Similarly, $H(\omega * 2 + m, n) = 4n + 4m + 2$.

$H(\omega*3, n) = 4(2n+1) + 2 = 8n + 6$.

$H(\omega*4, n) = 8(2n+1) + 6 = 16n + 14$.

$H(\omega*m, n) = 2^m n + 2^m - 2$.

$H(\omega^2, n) = 2^n (n+2) - 2 > F_2 (n) > 2^n$. (Here $F_{\alpha}(n)$ is the fast-growing hierarchy as described in Metzler's videos.)

$H(\omega^3, n) > F_3 (n) > 2 \uparrow \uparrow n$.

...

$H(\omega^{\omega}, n) > F_{\omega}(n) > $ Ackermann($n, n$).

$H(\omega^{\omega^{\omega}}, n) > F_{\omega^{\omega}}(n)$.

...

$H(\varepsilon_0, n) > F_{\varepsilon_0}(n-1)$.

...and so on. As you can see, this construction leads to the same large numbers as the fast-growing hierarchy. In general, $H(\omega^{\alpha}, n)$ is approximately $ F_{\alpha} (n)$.

Okay, on to trees. Define tree(n) to be the longest sequence of unlabelled, unordered trees $T_1, T_2, \ldots$ such that, for all $i$, $T_i$ has at most $n + i$ vertices, and for all $i, j$ with $i < j$, $T_i$ is not homeomorphically embeddable into $T_j$.

One might wonder why the sequence can't be infinite. This is basically because trees, ordered under embeddability, are "well-quasi-ordered", or WQO. This means that it has the same "no infinite descending sequence" property that ordinals have, but it may have elements that are incomparable. In fact it does: take one tree to be a root with two children, and another to be a tree with a child and a grandchild. These two trees are incomparable; neither one embeds in the other.

So, trees under embeddability are not well-ordered. But we can extend our partial order to a well-order; we will use a modification of the well-ordering used by Levitz and Jervell. (The Levitz/Jervell ordering is for ordered trees; we need one for unordered trees.)

We don't really need the exact details of the well-ordering, but I will give it here for reference. Given two trees, $S$ and $T$, we use the following comparison algorithm. First check, inductively, if $S$ is less than or equal to any of the immediate subtrees of $T$; if so, then $S < T$. Similarly, check if $T$ is less than or equal to any of the immediate subtrees of $S$; if so, then $T < S$. If neither of those checks apply, then compare the number of children of the root of $S$ to the number of children of the root of $T$; the tree with the larger number is greater. Finally, if the roots of $S$ and $T$ have the same number of children, compare the immediate subtrees of $S$ and $T$ one by one, starting from the smallest pair, then going to the second smallest pair, etc. The first time you find two different immediate subtrees, the greater of the two will belong to the greater original tree.

Okay, so now we have a well-ordering of trees, such that if $T_i < T_j$, then $T_i$ is not embeddable into $T_j$. This gives us a strategy for constructing long sequences of trees that obey the required conditions: take $T_{i+1}$ to be the largest tree less than $T_i$ with no more than the largest allowable number of nodes.

So, what kind of numbers do we get? Well, the situation is very similar to our above sequences of decreasing ordinals! For example, let the tree $T$ consist of a single path of $m$ vertices; this corresponds to the finite ordinal $m$. Let $n$ be the maximum allowable number of vertices in the next tree. Then the next tree, which we will denote $T[n]$, will be a path of $m-1$ vertices, which corresponds to the ordinal $m-1$, which is exactly $m[n]$. Similarly, the next tree, $T[n][n+1]$, will correspond to the ordinal $m[n][n+1]$, and so on, so we will reach the empty tree at the same time the corresponding ordinal reaches 0, so the length of the sequence starting from $T$ will be $H(m, n) - n + 1$.

Similarly, suppose $T$ is the tree where the root has two childless children. This corresponds to the ordinal $\omega$. $T[n]$ will then be a path of n nodes, which is the tree that corresponds to the ordinal $\omega[n]$. So we reach the empty tree at $T[n] \ldots [2n]$, since $\omega[n] \ldots [2n] = 0$. So the length of the sequence starting from $T$ is $H(\omega, n) - n + 1 = n + 1$. For larger trees/ordinals, we won't get a length of exactly $H(\alpha, n) - n + 1$, but it will be pretty close.

So, if we start from a tree corresponding to $\omega^{\alpha}$, we will get a function comparable to $F_{\alpha}$ in the fast-growing hierarchy. The natural question to ask is: what is the ordinal corresponding to this well-ordering of trees?

Metzler's videos decribes the Veblen hierarchy, going up to $\Gamma_0$. We can continue on by defining $\phi(1, 0, \alpha)$ to be the $\alpha$th fixed point of $f(x) = \phi(x, 0)$. (So $\phi(1, 0, 0) = \Gamma_0$.) We then define a second Veblen hierarchy where the starting function is $\phi(1, 0, \alpha)$ instead of $\omega^{\alpha}$; so

$\phi(1, \alpha+1, \beta)$ is the $\beta$th fixed point of $f(x) = \phi(1, \alpha, x)$.

When $\alpha$ is a limit ordinal, $\phi(1, \alpha, \beta)$ is the $\beta$th ordinal in the ranges of $f(x) = \phi (1, \gamma, x)$ for all $\gamma < \alpha$.

We can then define

$\phi(2, 0, \alpha)$ to be the $\alpha$th fixed point of $f(x) = \phi(1, x, 0)$.

More generally, we define

$\phi(\alpha+1, 0, \beta)$ to be the $\beta$th fixed point of $f(x) = \phi(\alpha, x, 0)$

and for $\alpha$ a limit ordinal,

$\phi(\alpha, 0, \beta)$ is the $\beta$th ordinal in the ranges of $f(x) = \phi(\gamma, x, 0)$ for all $\gamma < \alpha$.

Next, we can go to 4 places: define

$\phi (\alpha+1, 0, 0, \beta)$ to be the $\beta$th fixed point of $f(x) = \phi(\alpha, x, 0, 0)$

and for $\alpha$ a limit ordinal

$\phi (\alpha, 0, 0, \beta)$ is the $\beta$th ordinal in the ranges of $f(x) = \phi(\gamma, x, 0, 0)$ for all $\gamma < \alpha$.

You can see how to extend this to arbitrarily many places. The smallest ordinal that cannot be reached by applying this extended phi notation is called the Small Veblen ordinal.

Well, it turns out that the Small Veblen ordinal is the limit of Levitz'/Jervell's well-ordering. In particular,

the tree whose root has two childless children corresponds to $\omega$. the tree whose root has three childless children corresponds to $\epsilon_0$. the tree whose root has four childless children corresponds to $\phi(1,0,0,0)$. In general, the tree whose root has n childless children for $n \ge 4$ corresponds to $\phi(1, 0, 0, \ldots, 0)$ with $n-1$ $0$'s.

Now we can finally relate this all to TREE(n). TREE(n) is defined as the length of the longest sequence of trees $T_1, T_2, \ldots$ labelled from {1, 2, ..., n} such that, for all $i$, $T_i$ has at most $i$ vertices, and for all $i, j$ such that $i < j$, there is no label-preserving homeomorphic embedding from $T_i$ into $T_j$.

TREE(1) is clearly 1. The first tree can only be the unique one-vertex tree labelled with 1. This tree obviously embeds into any other tree, so we are done at 1.

TREE(2) is 3. The first tree can only be the unique one-vertex tree, labelled with either 1 or 2, it doesn't matter which. Say we label it with 1. Then no remaining trees can use the label 1; all vertices must be labelled with 2. The second tree can either be the unique one-vertex tree or the unique two-vertex tree. If it is the former, we can have no more trees; if it is the latter, the only tree that the two-vertex tree does not embed into is the one vertex tree, so it is the only choice for the third tree is the one-vertex tree, and again we are done.

So, so far we are not getting very long sequences! But TREE(3) is a totally different kettle of fish.

Before we get to TREE(3), let's examine some smaller sequences that will build up towards it.

To describe a tree, I will use () to denote a vertex labelled with 1, and [] to denote a vertex labelled with 2. The children of a vertex will be placed within the separators for the vertex; so for example

([][][])

means a vertex labelled with 1 with three children labelled with 2; and

[(()()) ()]

means a vertex labelled with 2 with two children labelled with 1; the left child has two children labelled with 1.

We will start by examining trees that are paths, with the root labelled with 2 and the rest of the vertices labelled with 1.

[]

(())

()

starting from a single vertex labelled with 2 leads to a sequence of length 3.

[()]

(()[])

((([])))

(([]))

([])

[]

(()()()()()()())

the last tree is the first tree in the sequence for tree(7) so we get a sequence of length greater than tree(7)

[(())]

(()[()])

((([()])))

(([()]))

([()])

[()]

(()()()()()()()[])

the last tree is the first tree in the sequence for tree(8), except the last vertex is labelled with a 2. We can thus continue with a sequence of length tree(8) of trees with all but one vertex labelled with 1, finally ending in a tree consisting of one vertex labelled with 2. The next tree is then a tree with more than tree(8) vertices with all vertices labelled with one; this leads to a sequence of more than tree(tree(8)) vertices.

Continuing in this fashion, a path with one vertex labelled with 2 and n vertices labelled with 1 will lead to a sequence of more than tree$^n(n+6)$ trees. If we define tree$_2 (n)$ to be tree$^n(n)$, then our lower bound is more than tree$_2 (n)$ trees.

Now consider a tree consisting of a path of length $n+1$ with the bottom vertex of the path having two children. Again, the root will have label 2 and the rest of the vertices will have label 1. For example, with n = 3 the tree is

[(((()())))]

We can construct a sequence of more than tree$_2 (n-1)$ trees by basically following the previous sequence, with the two children at the bottom added on. This leads us to the tree [()()]. We follow that with the tree [(((...()...)))] with more than tree$_2 (n-1)$ vertices. By our previous bound, we will wind up with a sequence of length greater than tree$_2$ (tree$_2 (n-1))$.

If we next consider a tree similar to the previous one, except we add a child to one of the two children at the bottom, we will get a lower bound of tree$_2$ (tree$_2$ (tree$_2 (n-1)))$. If we add a path of length $m$ rather than a single child, we get a lower bound of tree$_2^{m+2}(n-1)$. Define tree$_3 (n)$ to be tree$_2^n(n)$. If $n \ge m+3$, we have a lower bound of tree$_3 (m)$.

Now we are ready to find a lower bound for TREE(3). Start with:

{} (one vertex with label 3)

[[]]

([][])

[()()()]

[(())(())]

[((()) ()) ()]

[(((()()))) ()]

[((((()()))()))]

((((()()))()))

((([(((()()))())])))

(([(((()()))())]))

([(((()()))())])

[(((()()))())]

(()()()()()()()[((()()))()])

this leads to a sequence of tree(8) trees, ending in

[((()()))()]

this is followed by

[((()())())]

where the ( stands for tree(8) ('s and ) stands for tree(8) )'s.

This leads to a sequence of tree$_2$ (tree(8)) trees, ending in

[(()())()]

This is followed by

[(( () )())]

where the ( stands for tree$_2$ (tree(8)) ('s and ) stands for tree$_2$ (tree(8)) )'s.

This leads to a sequence of more than tree$_3$ (tree$_2$ (tree(8))) trees.

Thus TREE(3) > tree$_3$ (tree$_2$ (tree(8))).

As you can imagine, the TREE(n) function clearly outpaces the tree(n) function, which is already at the level of the Small Veblen Ordinal in the fast-growing hierarchy. This is not surprising, since labelled trees lead to more possibilities than unlabelled trees.

I know this was very long, but I wanted to go step by step since I know you are not an expert in this subject. Please feel free to ask about anything you are confused about.