Combinatorial principles equivalent to weak induction

摘要

We consider two combinatorial principles, ERT and ECT. Both are easily proved in RCA(0) plus Sigma(0)(2) induction. We give two proofs of ERT in RCA(0), using different methods to eliminate the use of Sigma(0)(2) induction. Working in the weakened base system RCA*0, we prove that ERT is equivalent to Sigma(0)(1) induction and ECT is equivalent to Sigma(0)(2) induction. We conclude with a Weihrauch analysis of the principles, showing ERT = W LPO* < W TCN* = W ECT.