A theorem about trees produces a number that dwarfs Graham's number
Kruskal's tree theorem sounds modest: it is about how finite branching diagrams fit inside one another. Yet a finite version of it gives rise to TREE(3), one of the largest numbers anyone has defined simply, so vast that Graham's number and a googolplex look tiny beside it.
The theorem says that if you label the points of finite trees using a well-behaved set of labels, then in any endless list of such trees, some earlier tree will always embed inside a later one. Mathematicians call this property being well-quasi-ordered. Andrew Vázsonyi conjectured it, Joseph Kruskal proved it in 1960, and Crispin Nash-Williams found a short proof in 1963, including a direct argument for plain unlabelled trees.
The surprise came in the early 1980s, when Harvey Friedman noticed that simple special cases of the theorem can be stated in weak logical systems but cannot be proved in them. Even the unlabelled case is unprovable in a system known as ATR0, which made it the first example of a predicative result whose proof is necessarily impredicative. This was an early triumph for reverse mathematics, the field that asks exactly which axioms a theorem needs. By adding a gap condition, Friedman produced a natural variant beyond the reach of a considerably stronger system.
Friedman then turned the theorem into fast-growing functions. Ask how long a sequence of trees can be under certain size limits and the answers start small, then abruptly explode. Proving that even his weaker function takes a particular value requires an absurdly long proof in ordinary Peano arithmetic, though a stronger system can do it in at most 10,000 symbols. Adding labels gives the TREE function, which eventually outgrows every function that a powerful system of analysis can prove to be computable.
The tree result was later generalised from trees to graphs. The Robertson–Seymour theorem, completed in 2004, plays a similar role in reverse mathematics and spawns the SSCG function, which grows faster still and leaves even TREE behind.
Source: Kruskal's tree theorem
