Reductions of Well-Ordering Principles to Combinatorial Theorems
Lorenzo Carlucci, Leonardo Mainardi, Konrad Zdanowski · Notre Dame Journal of Formal Logic · 2026
A well-ordering principle is a principle of the following form: if X is well-ordered, then F(X) is well-ordered, where X is a linear order and F is an operator transforming linear orders into linear orders. Many important subsystems of second-order arithmetic of interest in reverse mathematics are known to be equivalent to well-ordering principles for rather natural operators F. In particular, this is the case for the systems ACA0, ACA0′, and ACA0+. These systems are also equivalent to various forms of Ramsey-theoretic theorems. We present an approach for proving that the instance-solution problems naturally associated with the well-ordering principles corresponding to the systems ACA0, ACA0′, and ACA0+ are reducible to the problems associated to the Ramsey-theoretic principle at the corresponding level of logical strength by Weihrauch reductions (that is, uniform computable reductions). As a by-product we give new direct proofs of known implications over RCA0 from Ramsey-type theorems to well-ordering principles.