pith. sign in

arxiv: 1812.09943 · v1 · pith:TGTI7A2Bnew · submitted 2018-12-24 · 🧮 math.LO

Combinatorial principles equivalent to weak induction

classification 🧮 math.LO
keywords inductionsigmaequivalentprinciplescombinatorialequivanalysisbase
0
0 comments X
read the original abstract

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}}$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.