Research article:

    Samuel R. Buss.
    "Axiomatizations and conservation results for fragments of bounded arithmetic."
    In Logic and Computation, Proceedings of a Workshop held at Carnegie Mellon University, June 30-July 2, 1987. AMS Contemporary Mathematics 106 (1990) 57-84.

    Download article: postscript or PDF

    Abstract: This paper presents new results on axiomatizations for fragments of Bounded Arithmetic which improve upon the author's dissertation. It is shown that $(\Sigma_{i+1}^b \cap \Pi_{i+1}^b)$-PIND and strong $\Sigma_i^b$-replacement are consequences of $S_2^i$. Also $\Delta_{i+1}^b$-IND is a consequence of $T_2^i$. The latter result is proved by showing that $S_2^{i+1}$ is $\forall\exists\Sigma_{i+1}^b$-conservative over $T_2^i$. Furthermore, $S_2^{i+1}$ is conservative over $T_2^i + \Sigma_{i+1}^b\mbox{-replacement}$ with respect to Boolean combinations of $\Sigma_{i+1}^b$-formulas.

Back to Sam Buss's publications page.