A Note on Induction Schemas in Bounded Arithmetic

Abstract

As is well known, Buss' theory of bounded arithmetic $S_2^1$ proves ${\Sigma }_0^b({\Sigma }_1^b)-LIND$; however, we show that Allen's $D_2^1$ does not prove ${\Sigma }_0^b({\Sigma }_1^b)-LLIND$ unless $P=NC$. We also give some interesting alternative axiomatisations of $S_2^1$.