Induction rules in bounded arithmetic

0523579 - MÚ 2021 RIV DE eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GBP202/12/G061
Institucionální podpora: RVO:67985840
Klíčová slova: bounded arithmetic * parameter-free induction
Obor OECD: Pure mathematics
Impakt faktor: 0.287, rok: 2020
Způsob publikování: Omezený přístup
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.
Trvalý link: http://hdl.handle.net/11104/0307919