$\Sigma _n$-bounding and $\Delta _n$-induction
HTML articles powered by AMS MathViewer
- by Theodore A. Slaman
- Proc. Amer. Math. Soc. 132 (2004), 2449-2456
- DOI: https://doi.org/10.1090/S0002-9939-04-07294-6
- Published electronically: March 25, 2004
- PDF | Request permission
Abstract:
Working in the base theory of $\mathrm {PA}^- + \mathrm {I}\Sigma _0 +\exp$, we show that for all $n\in \omega$, the bounding principle for $\Sigma _n$-formulas ($\mathrm {B}\Sigma _n$) is equivalent to the induction principle for $\Delta _n$-formulas ($\mathrm {I}\Delta _n$). This partially answers a question of J. Paris.References
- Peter Clote and Jan Krajíček, Open problems, Arithmetic, Proof Theory, and Computational Complexity (Prague, 1991), Oxford Logic Guides, vol. 23, Oxford Univ. Press, New York, 1993, pp. 1–19.
- Petr Hájek and Pavel Pudlák, Metamathematics of first-order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1998. Second printing. MR 1748522
- Richard Kaye, Models of Peano arithmetic, Oxford Logic Guides, vol. 15, The Clarendon Press, Oxford University Press, New York, 1991. Oxford Science Publications. MR 1098499
- L. A. S. Kirby and J. B. Paris, Initial segments of models of Peano’s axioms, Set theory and hierarchy theory, V (Proc. Third Conf., Bierutowice, 1976) Lecture Notes in Math., Vol. 619, Springer, Berlin, 1977, pp. 211–226. MR 0491157
- Charles Parsons, On a number theoretic choice schema and its relation to induction, Intuitionism and Proof Theory (Proc. Conf., Buffalo, N.Y., 1968) North-Holland, Amsterdam, 1970, pp. 459–473. MR 0280330
Bibliographic Information
- Theodore A. Slaman
- Affiliation: Department of Mathematics, University of California Berkeley, Berkeley, California 94720-3840
- MR Author ID: 163530
- Email: slaman@math.berkeley.edu
- Received by editor(s): November 20, 2002
- Received by editor(s) in revised form: February 20, 2003
- Published electronically: March 25, 2004
- Additional Notes: During the preparation of this paper, the author was partially supported by the Alexander von Humboldt Foundation and by the National Science Foundation Grant DMS-9988644. The author is grateful to Jan Krajíček for reading a preliminary version of this paper and suggesting improvements to it.
- Communicated by: Carl G. Jockusch, Jr.
- © Copyright 2004 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 132 (2004), 2449-2456
- MSC (2000): Primary 03F30, 03H15
- DOI: https://doi.org/10.1090/S0002-9939-04-07294-6
- MathSciNet review: 2052424