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:
- Tree \(T_k\) has at most \(k\) nodes.
- 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 |
|---|---|---|
| 1 | 1 | The first tree (one node) is contained in every later tree |
| 2 | 3 | Start with one red node; then you can only use blue, and the game ends after 3 trees |
| 3 | Unimaginably large | Finite, 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.
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.
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
- Graham’s Number Explained: How Big Is It Really?
- Busy Beaver Explained: BB(5) Solved, BB(6) Still Open
- Gödel’s Incompleteness Theorems Explained Simply
Sources and Further Reading
Related to This Article
More math articles
- Gain Access to the Answers: Explore the Solution Manual for “CHSPE Math for Beginners”
- The Best Algebra 1 Book for Kansas Students
- How to Prepare for the CBEST Math Test?
- Environment, Resources, and Sustainability
- 10 Most Common ACCUPLACER Math Questions
- Group Types, Boundaries, Dyads, and Triads
- Fifth-Grade Math in Missouri (MAP): 49 Free Printable Worksheets, One Concept Per Page
- 8th Grade M-STEP Math Worksheets: FREE & Printable
- How to Use Matrices to Represent Data
- How Is the ACCUPLACER Test Scored?


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