A note on parameter free Π_1-induction and restricted exponentiation

摘要

We characterize the sets of all Π_2 and all B(Σ_1) (=Boolean combinations of Σ_1 ) theorems of IΠ_1~- in terms of restricted exponentiation, and use these characterizations to prove that both sets are not deductively equivalent. We also discuss how these results generalize ton > 0. As an application, we prove that a conservation theorem of Beklemishev stating that IΠ_(n+1)~- is conservative over IΣ_n~- with respect to B(Σ_(n+1)) sentences cannot be extended to Π_(n+2) sentences.