Kruskal's Tree Theorem states that in any infinite sequence of finite trees whose vertices carry labels from a fixed finite set, there always exist two trees, earlier and later in the sequence, such that the earlier tree embeds into the later one respecting both the tree structure and the labels. Named for Joseph Kruskal, it is a landmark result in the theory of well-quasi-orderings, notable also because a finite strengthening of the statement is known to be unprovable within certain strong systems used to formalize predicative mathematics.
Facts
StatementThe set of finite trees whose vertices are labeled from a well-quasi-ordered set is itself well-quasi-ordered under homeomorphic embedding. 1 Proof YearConjectured by Andrew Vazsonyi; proved by Joseph Kruskal in 1960. A shorter proof was given by Crispin Nash-Williams in 1963. Classification
Statement FormCharacterization Theorem 1 Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Sources
1. Kruskal's Tree Theorem (Wikipedia)
Wikimedia FoundationLead paragraph, statement sentence
In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding.
History section, first sentence
The theorem was conjectured by Andrew Vazsonyi and proved by Joseph Kruskal (1960); a short proof was given by Crispin Nash-Williams (1963).
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.