On the logical strength of the better quasi order with three elements

DOI10.1090/TRAN/8966MaRDI QIDQ6135847OpenAlexFDO

Authors Anton Freund

Publication date 28 August 2023

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.11132

zbMATH Keywords

reverse mathematicsbetter quasi order3 is BQO

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35) Recursive ordinals and ordinal notations (03F15)

Abstract: The notion of better quasi order ($mathsfBQO$), due to Nash-Williams, is very fruitful mathematically and intriguing from the standpoint of logic, due to several long-standing open problems. In the present paper, we make a significant step towards one of these: Let $mathbf3$ be the discrete order with three elements. We show that arithmetical recursion along the natural numbers ($mathsf{ACA}_0^{+}$) follows from $mathbf3$ being $mathsfBQO$, over the base theory $mathsfRC{A}_0$ from reverse mathematics. Also over the latter, we deduce arithmetical transfinite recursion ($mathsf{ATR}_0$) from the assumption that $mathbf3$ is $Delt{a}_2^{0}ext-mathsfBQO$, which plays a role in work of Montalb'an.

Recommendations

• Foundations of BQO Theory
• Towards better: a motivated introduction to better-quasi-orders
• scientific article; zbMATH DE number 956479
• Well, better and in-between
• Higman's lemma is stronger for better quasi orders

Cites work

• scientific article; zbMATH DE number 4033738 (Why is no real title available?)
• scientific article; zbMATH DE number 4068856 (Why is no real title available?)
• scientific article; zbMATH DE number 3232673 (Why is no real title available?)
• scientific article; zbMATH DE number 3248824 (Why is no real title available?)
• scientific article; zbMATH DE number 3333259 (Why is no real title available?)
• scientific article; zbMATH DE number 2236642 (Why is no real title available?)
• scientific article; zbMATH DE number 3030933 (Why is no real title available?)
• Better-quasi-orderings and coinduction
• Equivalence between Fraïssé's conjecture and Jullien's theorem
• Fraïssé's conjecture in \(\Pi_1^1\)-comprehension
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• On Fraissé's order type conjecture
• On Fraïssé's conjecture for linear orders of finite Hausdorff rank
• Open questions in reverse mathematics
• Reverse mathematics and ordinal exponentiation
• Reverse mathematics and the equivalence of definitions for well and better quasi-orders
• Reverse mathematics and well-ordering principles
• Reverse mathematics and well-ordering principles: a pilot study
• Subsystems of second order arithmetic
• The Veblen functions for computability theorists
• The theory of well-quasi-ordering: a frequently discovered concept
• Towards better: a motivated introduction to better-quasi-orders

Cited in

(1)

• Higman's lemma is stronger for better quasi orders

This page was built for publication: On the logical strength of the better quasi order with three elements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135847)