Combinatorial principles equivalent to weak induction


Abstract in English

We consider two combinatorial principles, ${sf{ERT}}$ and ${sf{ECT}}$. Both are easily proved in ${sf{RCA}}_0$ plus ${Sigma^0_2}$ induction. We give two proofs of ${sf{ERT}}$ in ${sf{RCA}}_0$, using different methods to eliminate the use of ${Sigma^0_2}$ induction. Working in the weakened base system ${sf{RCA}}_0^*$, we prove that ${sf{ERT}}$ is equivalent to ${Sigma^0_1}$ induction and ${sf{ECT}}$ is equivalent to ${Sigma^0_2}$ induction. We conclude with a Weihrauch analysis of the principles, showing ${sf{ERT}} {equiv_{rm W}} {sf{LPO}}^* {<_{rm W}}{{sf{TC}}_{mathbb N}}^* {equiv_{rm W}} {sf{ECT}}$.

Download