2021/12/16 by Anton Freund, ANTON FREUND, Freund, Anton · 1 citation
Computer Science · Mathematics · #03B30 #03F15 #03F35 #05C83 #06A07 #Advanced Topology and Set Theory #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO)
paper · pdf · doi:10.48550/arxiv.2112.08727
openalex publication_date 2021/12/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Kruskal-Friedman theorem asserts: in any infinite sequence of finite trees with ordinal labels, some tree can be embedded into a later one, by an embedding that respects a certain gap condition. This strengthening of the original Kruskal theorem has been proved by I. Kříž (Ann. Math. 1989), in confirmation of a conjecture due to H. Friedman, who had established the result for finitely many labels. It provides one of the strongest mathematical examples for the independence phenomenon from Gödel's theorems. The gap condition is particularly relevant due to its connection with the graph minor theorem of N. Robertson and P. Seymour. In the present paper, we consider a uniform version of the Kruskal-Friedman theorem, which extends the result from trees to general recursive data types. Our main theorem shows that this uniform version is equivalent both to Π11-transfinite recursion and to a minimal bad sequence principle of Kříž, over the base theory RCA0 from reverse mathematics. This sheds new light on the role of infinity in finite combinatorics.