Open AccessReductions of well-ordering principles to combinatorial theoremsOpen Access
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.
To access your conversation history and unlimited prompts, please
Prompt 0/10