Premium
A note on parameter free Π 1 ‐induction and restricted exponentiation
Author(s) -
CordónFranco A.,
FernándezMargarit A.,
LaraMartín F. F.
Publication year - 2011
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201010013
Subject(s) - exponentiation , mathematics , sigma , combinatorics , discrete mathematics , physics , mathematical analysis , quantum mechanics
We characterize the sets of all Π 2 and all \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathcal {B}(\Sigma _{1})$\end{document} (= 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 to n > 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 \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathcal {B}(\Sigma _{n+1})$\end{document} sentences cannot be extended to Π n + 2 sentences. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim