-bounding and -induction

Author:
Theodore A. Slaman

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

Published electronically:
March 25, 2004

MathSciNet review:
2052424

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Working in the base theory of , we show that for all , the bounding principle for -formulas ( ) is equivalent to the induction principle for -formulas ( ). This partially answers a question of J. Paris.

**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**

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:
https://doi.org/10.1090/S0002-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

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.

Article copyright:
© Copyright 2004
American Mathematical Society