Provable better quasi orders

2023/05/01 by Anton Freund, Freund, Anton, Alberto Marcone +5 · 1 citation
Computer Science · Mathematics · #03B30 #03F35 #06A06 #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2305.01066

openalex publication_date 2023/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

It has recently been shown that fairly strong axiom systems such as ACA₀ cannot prove that the antichain with three elements is a better quasi order (bqo). In the present paper, we give a complete characterization of the finite partial orders that are provably bqo in such axiom systems. The result will also be extended to infinite orders. As an application, we derive that a version of the minimal bad array lemma is weak over ACA₀. In sharp contrast, a recent result shows that the same version is equivalent to Π¹₂-comprehension over the stronger base theory ATR₀.

Cited by

• Generalized Higman's Theorem and iterated ideals

Related

• The logical strength of minimal bad arrays
• On the existence of small antichains for definable quasi-orders
• On the logical strength of the better quasi order with three elements
• On the existence of large antichains for definable quasi-orders
• On partial orderings having precalibre-ℵ₁ and fragments of Martin's axiom