Journal article:

    Samuel R. Buss and Aleksandar Ignjatović.
    "Unprovability of Consistency Statements in Fragments of Bounded Arithmetic."
    Annals of Pure and Applied Logic 74 (1995) 221-244.

    Download article: postscript or PDF

    Abstract: This paper deals with the weak fragments of arithmetic $PV$ and $S^i_2$ and their induction-free fragments $PV^-$ and $S^{-1}_2$. We improve the bootstrapping of $S^1_2$, which allows us to show that the theory $S^1_2$ can be axiomatized by the set of axioms $\BASIC$ together with any of the following induction schemas: $\Sigma^b_1\PIND$, $\Sigma^b_1\LIND$, $\Pi^b_1\PIND$ or $\Pi^b_1\LIND$. We improve prior results of Pudlak, Buss and Takeuti establishing the unprovability of bounded consistency of $S^{-1}_2$ in $S_2$ by showing that, if $S^i_2$ proves $\forall x \varphi (x)$ with $\varphi$ a $\Sigma^b_0(\Sigma^b_i)$-formula, then $S^1_2$~proves that each instance of~$\varphi(x)$ has a $S^{-1}_2$-proof in which only $\Sigma^b_0(\Sigma^b_i)$-formulas occur. Finally, we show that the consistency of the induction free fragment $PV^-$ of $PV$ is not provable in $PV$..

Back to Sam Buss's publications page.