Kruskal's tree theorem
Teorema del árbol de Kruskal
- Date
- 1960 · confidence low
- Place
- United States
- Credited to
- Joseph Kruskal
- Field
- Knowledge & symbols
What was discovered
Theorem stating that the set of finite trees labeled over a well-quasi-ordered set is itself well-quasi-ordered under homeomorphic embedding; it gives rise to the fast-growing TREE function.
What it led to
- Results on the limits of axiomatic systems (proof theory)
- TREE(3) as an example of an extraordinarily fast-growing number
- Applications in computability theory
- Studies of well-founded orders in combinatorics