[Proof Complexity] preprint

[Emil Jerabek]

Dear colleagues,

A new preprint "Induction rules in bounded arithmetic" is available on
my web page (http://math.cas.cz/~jerabek/index.html). Suggestions,
corrections, and comments are welcome.

Best regards,
Emil Jerabek

Abstract:
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^i_2 and S^i_2 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.