Higman's lemma is stronger for better quasi orders

2022/05/09 by Anton Freund, Freund, Anton
Computer Science · Mathematics · #03B30 #03F15 #03F35 #06A07 #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.2205.04336

openalex publication_date 2022/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that Higman's lemma is strictly stronger for better quasi orders than for well quasi orders, within the framework of reverse mathematics. In fact, we show a stronger result: the infinite Ramsey theorem (for tuples of all lengths) follows from the statement that any array [\mathbb N]ⁿ⁺¹→\mathbb Nⁿ× X for a well order X and n∈\mathbb N is good, over the base theory RCA₀.

Related

• Adjacent Ramsey theory and Higman's lemma
• Proof-Theoretic Relations between Higman's and Kruskal's theorem, and Independence Results for Tree-like Structures
• Reductions of well-ordering principles to combinatorial theorems
• Maximal order types for sequences with gap condition
• Weihrauch reducibility between Ramsey-type theorems and well-ordering principles at the level of Σ⁰₂-induction: A pilot study