Combinatorial principles equivalent to weak induction
Author(s) -
Caleb Davis,
Denis R. Hirschfeldt,
Jeffry L. Hirst,
Jake Pardo,
Arno Pauly,
Keita Yokoyama
Publication year - 2019
Publication title -
computability
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.136
H-Index - 12
eISSN - 2211-3576
pISSN - 2211-3568
DOI - 10.3233/com-180244
Subject(s) - combinatorial principles , mathematical proof , mathematical induction , mathematics , algebra over a field , pure mathematics , discrete mathematics , combinatorics , combinatorial explosion , geometry
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}}$.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom