A Note on Induction Schemas in Bounded Arithmetic
<|reference_start|>A Note on Induction Schemas in Bounded Arithmetic: As is well known, Buss' theory of bounded arithmetic $S^{1}_{2}$ 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^{1}_{2}$.<|reference_end|>
@article{ignjatovic2002a,
    title={A Note on Induction Schemas in Bounded Arithmetic},
    author={Aleksandar Ignjatovic},
    journal={arXiv preprint arXiv:cs/0210011},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0210011},
    primaryClass={cs.LO cs.CC}
}