Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society since 1950, Proceedings of the American Mathematical Society is devoted to shorter research articles in all areas of pure and applied mathematics.

ISSN 1088-6826 (online) ISSN 0002-9939 (print)

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

$\Sigma _n$-bounding and $\Delta _n$-induction
HTML articles powered by AMS MathViewer

by Theodore A. Slaman PDF
Proc. Amer. Math. Soc. 132 (2004), 2449-2456 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
Similar Articles
  • Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03F30, 03H15
  • Retrieve articles in all journals with MSC (2000): 03F30, 03H15
Additional 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