A theorem about trees produces a number that dwarfs Graham's number
In short: 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.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Kruskal's tree theorem
To cite this card, link to https://intellectplus.co.uk/app/science-kruskal-s-tree-theorem.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Calculus and analysis · More in Science · Latest · A–Z · All topics