z-logo
open-access-imgOpen Access
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}}$.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom