Combinatorial principles equivalent to weak induction

Abstract

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