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

DOI10.1090/TRAN/8966arXiv2206.11132OpenAlexW4367055849MaRDI QIDQ6135847FDOQ6135847

Anton Freund

Publication date: 28 August 2023

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

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.

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)

Cites Work

• Graph minors. XX: Wagner's conjecture
• Graph minors. XIII: The disjoint paths problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Fraissé's order type conjecture
• Reverse mathematics and the equivalence of definitions for well and better quasi-orders
• Title not available (Why is that?)
• Title not available (Why is that?)
• The theory of well-quasi-ordering: a frequently discovered concept
• Open Questions in Reverse Mathematics
• Title not available (Why is that?)
• Reverse mathematics and well-ordering principles
• Title not available (Why is that?)
• The Veblen functions for computability theorists
• Reverse mathematics and ordinal exponentiation
• Title not available (Why is that?)
• On Fraïssé's conjecture for linear orders of finite Hausdorff rank
• Equivalence between Fraïssé's conjecture and Jullien's theorem
• Reverse mathematics and well-ordering principles: a pilot study
• Title not available (Why is that?)
• Better-quasi-orderings and coinduction
• Fraïssé’s conjecture in Π11-comprehension
• 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)