Induction rules in bounded arithmetic

0523579 - MÚ 2021 RIV DE eng J - Journal Article
Jeřábek, Emil
Induction rules in bounded arithmetic.
Archive for Mathematical Logic. Roč. 59, č. 3-4 (2020), s. 461-501. ISSN 0933-5846. E-ISSN 1432-0665
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : bounded arithmetic * parameter-free induction
OECD category: Pure mathematics
Impact factor: 0.287, year: 2020
Method of publishing: Limited access
https://link.springer.com/article/10.1007%2Fs00153-019-00702-w

We study variants of Buss's theories of bounded arithmetic axiomatized by induction schemes disallowing the use of parameters, and closely related induction inference rules. We put particular emphasis on Pi^b_i induction schemes, which were so far neglected in the literature. We present inclusions and conservation results between the systems (including a witnessing theorem for T^2_i and S^2_i of a new form), results on numbers of instances of the axioms or rules, connections to reflection principles for quantified propositional calculi, and separations between the systems.
Permanent Link: http://hdl.handle.net/11104/0307919