A Note on Induction Schemas in Bounded Arithmetic

الأصل · EN

As is well known, Buss' theory of bounded arithmetic S¹₂ proves Σ₀ᵇ(Σ₁ᵇ)-LIND; however, we show that Allen's D₂¹ does not prove Σ₀ᵇ(Σ₁ᵇ)-LLIND unless P = NC. We also give some interesting alternative axiomatisations of S¹₂.