TREE(3) Explained: Why It’s Bigger Than Graham’s Number

Quick answer: TREE(3) is the length of the longest possible sequence in a tree-building game with 3 colors of nodes, where the k-th tree has at most k nodes and no tree may “contain” an earlier one. Kruskal’s tree theorem (1960) guarantees the game always ends, so TREE(3) is finite. TREE(1) = 1 and TREE(2) = 3, but TREE(3) is so large that it makes Graham’s number look tiny. Harvey Friedman, who studied the TREE function, showed that any proof of its finiteness in certain standard formal systems must be astronomically long.

Some huge numbers are built on purpose, like Graham’s number. TREE(3) is different: it comes from a simple game with colored trees, and it turns out to be one of the largest numbers ever to appear naturally in mathematics. Here is the game.

The Tree Game

A tree here is a set of dots (nodes) joined by lines with no loops, with one dot marked as the root. Each node gets one of \(n\) colors. You build a sequence of trees \(T_1, T_2, T_3, \dots\) following two rules:

  1. Tree \(T_k\) has at most \(k\) nodes.
  2. No tree may contain an earlier tree. Roughly, \(T_i\) is contained in a later \(T_j\) if you can map the nodes of \(T_i\) to different nodes of \(T_j\) with the same colors, so that where two branches meet in \(T_i\), their images meet at the image of that meeting point in \(T_j\). Extra nodes may sit along the paths in \(T_j\), separate branches must stay separate, and the root of \(T_i\) need not go to the root of \(T_j\). (Technically: an injective, color-preserving map \(h\) with \(h(x \wedge y) = h(x) \wedge h(y)\), where \(x \wedge y\) is the lowest common ancestor.)

\(\text{TREE}(n)\) is the length of the longest sequence you can build with \(n\) colors.

Small Values

Colors \(n\)TREE(\(n\))Why
11The first tree (one node) is contained in every later tree
23Start with one red node; then you can only use blue, and the game ends after 3 trees
3Unimaginably largeFinite, but far beyond Graham’s number

For 2 colors: \(T_1\) is a single red node, so red can never be used again. \(T_2\) has two blue nodes. \(T_3\) is a single blue node. Any \(T_4\) would contain \(T_3\). So TREE(2) = 3.

Why It Must End: Kruskal’s Tree Theorem

In 1960, Joseph Kruskal proved that every infinite sequence of finite trees has some tree contained in a later one. So the game cannot go on forever, and \(\text{TREE}(n)\) is finite for every \(n\). But the proof gives no bound on how long the game can last.

How Big Is TREE(3)?

Harvey Friedman, who defined the TREE function in his work on finite forms of Kruskal’s theorem, showed that TREE(3) is vastly larger than anything you can build with up-arrows, including Graham’s number; even lower bounds for it are expressed using fast-growing hierarchies of functions with huge ordinal indices. No one can describe it as a tower of exponents, because no realistic tower comes close.

Why It Is Special: Hard to Prove Finite

Three different facts are easy to mix up here:

  • Kruskal’s general theorem (about all infinite sequences of trees) cannot be proved in the formal system ATR₀, a standard system for “predicative” mathematics, even though it is easy to state. This is a natural statement that needs stronger axioms, in the spirit of Gödel’s incompleteness theorems.
  • The uniform statement “TREE(\(n\)) is finite for every \(n\)” is also beyond such weak systems.
  • The single fact “TREE(3) is finite” is provable, but Friedman showed that in certain formal systems any proof of it must be unimaginably long.

So it is wrong to say that mathematics cannot prove TREE(3) is finite. What is remarkable is how much it costs.

Common Misconceptions

“TREE(3) is infinite.” No. Kruskal’s theorem proves it is a finite whole number.

“TREE(3) is the largest number in math.” No. There is no largest number; functions like the busy beaver grow even faster than TREE.

Watch: TREE(3) in Video

If you learn better by watching, these videos are worth your time.

The Enormous TREE(3) – Numberphile (Numberphile). Tony Padilla explains the tree game and its size.
TREE vs Graham’s Number – Numberphile (Numberphile). How TREE(3) compares with Graham’s number.

Check Your Understanding

Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.

Answer each question and press Submit to see your result right away.

1. What is TREE(1)?
Found a bug? Let us know!
2. What is TREE(2)?
Found a bug? Let us know!
3. Which theorem guarantees TREE(3) is finite?
Found a bug? Let us know!
4. How does TREE(3) compare with Graham’s number?
Found a bug? Let us know!
5. Who introduced the TREE function?
Found a bug? Let us know!

Frequently Asked Questions

What is TREE(3)?

The maximum length of a sequence of 3-colored trees in which the k-th tree has at most k nodes and no tree is contained in a later one.

Is TREE(3) bigger than Graham’s number?

Yes, vastly. Graham’s number can be written with up-arrows, but TREE(3) is far beyond any such expression.

Why is TREE(2) equal to 3?

After a one-node red tree, red can never be used again; with only blue you can make a two-node tree and a one-node tree, and then the game must stop.

Is TREE(3) finite?

Yes. Kruskal’s tree theorem (1960) guarantees the game always ends. The general theorem needs axioms beyond weak systems such as ATR₀, and Friedman showed that proofs of TREE(3)’s finiteness in certain formal systems must be astronomically long.

Keep Exploring

Sources and Further Reading

Related to This Article

What people say about "TREE(3) Explained: Why It’s Bigger Than Graham’s Number - Effortless Math"?

No one replied yet.

Leave a Reply