Research Library

open-access-imgOpen AccessReductions of well-ordering principles to combinatorial theorems
Author(s)
Lorenzo Carlucci,
Leonardo Mainardi,
Konrad Zdanowski
Publication year2024
A well-ordering principle is a principle of the form: If $X$ is well-orderedthen $F(X)$ is well-ordered, where $F$ is some natural operator transforminglinear orders into linear orders. Many important subsystems of Second-orderArithmetic of interest in Reverse Mathematics are known to be equivalent towell-ordering principles. We give a unified treatment for proving lower bounds on the logical strengthof various Ramsey-theoretic principles relations using characterizations of thecorresponding formal systems in terms of well-ordering principles. Our implications (over $RCA_0$) from combinatorial theorems to $ACA_0$ and$ACA_0^+$ also establish uniform computable reductions of the correspondingwell-ordering principles to the corresponding Ramsey-type theorems.
Language(s)English

Seeing content that should not be on Zendy? Contact us.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here