Proceedings of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6826(e) ISSN 0002-9939(p)

$\Sigma_n$ -bounding and $\Delta_n$ -induction

Author(s): Theodore A. Slaman
Journal: Proc. Amer. Math. Soc. 132 (2004), 2449-2456.
MSC (2000): Primary 03F30, 03H15
Posted: March 25, 2004
MathSciNet review: 2052424
Retrieve article in: PDF
This article is available free of charge

Abstract | References | Similar articles | Additional information

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:

1.: Peter Clote and Jan Krajícek, Open problems, Arithmetic, Proof Theory, and Computational Complexity (Prague, 1991), Oxford Logic Guides, vol. 23, Oxford Univ. Press, New York, 1993, pp. 1-19.
2.: Petr Hájek and Pavel Pudlák, Metamathematics of first-order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1998, Second printing. MR 2000m:03003
3.: Richard Kaye, Models of Peano arithmetic, Oxford Logic Guides, vol. 15, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1991. MR 92k:03034
4.: 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), Springer, Berlin, 1977, pp. 211-226. Lecture Notes in Math., Vol. 619. MR 58:10423
5.: 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 43:6050

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
Email: slaman@math.berkeley.edu

DOI: 10.1090/S0002-9939-04-07294-6
PII: S 0002-9939(04)07294-6
Keywords: $\Sigma_n$-bounding, $\Delta_n$-induction
Received by editor(s): November 20, 2002
Received by editor(s) in revised form: February 20, 2003
Posted: 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ícek for reading a preliminary version of this paper and suggesting improvements to it.
Communicated by: Carl G. Jockusch, Jr.
Copyright of article: Copyright 2004, American Mathematical Society

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|