I am not a mathematician but I am interested in big numbers. I find them to be really interesting, almost god-like.

I am watching a series of videos from David Metzler on YouTube. I have a basic understanding of some fast growing functions.

David does not cover TREE(n) which I’ve read is one of the fastest growing functions. I’ve looked at it explained in many places and even asked someone via Quora to help explain it to me, but I still don’t get it.

I think I need some sort of example of what TREE(1), TREE(2) and so on look like.If anyone could help me understand it I’d be really appreciative.

**Answer**

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 ω we can take the sequence {0, 1, 2, …}; for ω∗2 we can take the sequence ω,ω+1,ω+2,…,; for ω2, we can take the sequence 0,ω,ω∗2,…,; and so on. For an ordinal α, define α[n] to be the nth element of the fundamental sequence of α when α is a limit ordinal, and the predecessor of α when α is a successor ordinal.

Notice that α[n]<α for all ordinals α and natural numbers n. So α,α[n],α[n][n+1],α[n][n+1][n+2],… is a strictly decreasing sequence of ordinals. A defining property of ordinals is that there is no infinite decreasing sequence of ordinals; so for α>0, there exists a minimal natural number m so that α[n][n+1]…[m]=0. Define H(α,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]…[n+m−1]=0, for all n, so H(m,n)=n+m−1.

ω[n]=n,ω[n][n+1]=n−1,…,ω[n][n+1]…[2n]=0, so H(ω,n)=2n.

(ω+1)[n]=ω,(ω+1)[n][n+1]=n+1,(ω+1)[n][n+1]…[2n+2]=0, so H(ω+1,n)=2n+2.

Similarly, H(ω+m,n)=2n+2m.

(ω∗2)[n]=ω+n,(ω∗2)[n]…[2n]=ω,(ω∗2)[n]…[2n+1]=2n+1,(ω∗2)[n]…[4n+2]=0, so H(ω∗2,n)=4n+2.

Similarly, H(ω∗2+m,n)=4n+4m+2.

H(ω∗3,n)=4(2n+1)+2=8n+6.

H(ω∗4,n)=8(2n+1)+6=16n+14.

H(ω∗m,n)=2mn+2m−2.

H(ω2,n)=2n(n+2)−2>F2(n)>2n. (Here Fα(n) is the fast-growing hierarchy as described in Metzler's videos.)

H(ω3,n)>F3(n)>2↑↑n.

...

H(ωω,n)>Fω(n)> Ackermann(n,n).

H(ωωω,n)>Fωω(n).

...

H(ε0,n)>Fε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(ωα,n) is approximately Fα(n).

Okay, on to trees. Define tree(n) to be the longest sequence of unlabelled, unordered trees T1,T2,… such that, for all i, Ti has at most n+i vertices, and for all i,j with i<j, Ti is not homeomorphically embeddable into Tj.

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 Ti<Tj, then Ti is not embeddable into Tj. This gives us a strategy for constructing long sequences of trees that obey the required conditions: take Ti+1 to be the largest tree less than Ti 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 ω. T[n] will then be a path of n nodes, which is the tree that corresponds to the ordinal ω[n]. So we reach the empty tree at T[n]…[2n], since ω[n]…[2n]=0. So the length of the sequence starting from T is H(ω,n)−n+1=n+1. For larger trees/ordinals, we won't get a length of exactly H(α,n)−n+1, but it will be pretty close.

So, if we start from a tree corresponding to ωα, we will get a function comparable to Fα 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 Γ0. We can continue on by defining ϕ(1,0,α) to be the αth fixed point of f(x)=ϕ(x,0). (So ϕ(1,0,0)=Γ0.) We then define a second Veblen hierarchy where the starting function is ϕ(1,0,α) instead of ωα; so

ϕ(1,α+1,β) is the βth fixed point of f(x)=ϕ(1,α,x).

When α is a limit ordinal,

ϕ(1,α,β) is the βth ordinal in the ranges of f(x)=ϕ(1,γ,x) for all γ<α.

We can then define

ϕ(2,0,α) to be the αth fixed point of f(x)=ϕ(1,x,0).

More generally, we define

ϕ(α+1,0,β) to be the βth fixed point of f(x)=ϕ(α,x,0)

and for α a limit ordinal,

ϕ(α,0,β) is the βth ordinal in the ranges of f(x)=ϕ(γ,x,0) for all γ<α.

Next, we can go to 4 places: define

ϕ(α+1,0,0,β) to be the βth fixed point of f(x)=ϕ(α,x,0,0)

and for α a limit ordinal

ϕ(α,0,0,β) is the βth ordinal in the ranges of f(x)=ϕ(γ,x,0,0) for all γ<α.

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 ω.

the tree whose root has three childless children corresponds to ϵ0.

the tree whose root has four childless children corresponds to ϕ(1,0,0,0).

In general, the tree whose root has n childless children for n≥4 corresponds to ϕ(1,0,0,…,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 T1,T2,… labelled from {1, 2, ..., 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.

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 treen(n+6) trees. If we define tree2(n) to be treen(n), then our lower bound is more than tree2(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 tree2(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 tree2(n−1) vertices. By our previous bound, we will wind up with a sequence of length greater than tree2 (tree2(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 tree2 (tree2 (tree2(n−1))). If we add a path of length m rather than a single child, we get a lower bound of treem+22(n−1). Define tree3(n) to be treen2(n). If n≥m+3, we have a lower bound of tree3(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 tree2 (tree(8)) trees, ending in

[(()())()]

This is followed by

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

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

This leads to a sequence of more than tree3 (tree2 (tree(8))) trees.

Thus TREE(3) > tree3 (tree2 (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.

**Attribution***Source : Link , Question Author : Josh Kerr , Answer Author : Deedlit*