The logical strength of minimal bad arrays

2023/04/01 by Freund, Anton, Pakhomov, Fedor, Soldà, Giovanni
#03B30 #03F35 #06A06 #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2304.00278

Abstract

This paper studies logical aspects of the notion of better quasi order, which has been introduced by C. Nash-Williams (Mathematical Proceedings of the Cambridge Philosophical Society 1965 & 1968). A central tool in the theory of better quasi orders is the minimal bad array lemma. We show that this lemma is exceptionally strong from the viewpoint of reverse mathematics, a framework from mathematical logic. Specifically, it is equivalent to the set existence principle of Π¹₂-comprehension, over the base theory ATR₀.

Related

• Provable better quasi orders
• Minimal bad sequences are necessary for a uniform Kruskal theorem
• On the logical strength of the better quasi order with three elements
• The Biggest Five of Reverse Mathematics
• Well quasi-orders and the functional interpretation