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