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

Abstract

The notion of better quasi order ($\mathsf{BQO}$), 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 $3$ be the discrete order with three elements. We show that arithmetical recursion along the natural numbers (${\mathsf{ACA}}_0^{+}$) follows from $3$ being $\mathsf{BQO}$, over the base theory $\mathsf{RC}{\mathsf{A}}_0$ from reverse mathematics. Also over the latter, we deduce arithmetical transfinite recursion (${\mathsf{ATR}}_0$) from the assumption that $3$ is ${\Delta }_2^0\text{-}\mathsf{BQO}$, which plays a role in work of Montalbán.

arXiv commentThe results in the current version are significantly stronger than those in the previous one, and the title has been changed