Affiliations: [a] Department of Mathematical Sciences, Appalachian State University, NC, USA. [email protected] | [b] Department of Mathematics, The University of Chicago, IL, USA. [email protected] | [c] Department of Mathematical Sciences, Appalachian State University, NC, USA. [email protected] | [d] Department of Mathematical Sciences, Appalachian State University, NC, USA. [email protected] | [e] Department of Computer Science, Swansea University, United Kingdom. [email protected] | [f] School of Information Science, Japan Advanced Institute of Science and Technology, Japan. [email protected]
Abstract: We consider two combinatorial principles, ERT and ECT. Both are easily proved in RCA0 plus Σ20 induction. We give two proofs of ERT in RCA0, using different methods to eliminate the use of Σ20 induction. Working in the weakened base system RCA0∗, we prove that ERT is equivalent to Σ10 induction and ECT is equivalent to Σ20 induction. We conclude with a Weihrauch analysis of the principles, showing ERT≡WLPO∗<WTCN∗≡WECT.
