|
 -bounding and  -induction
Author(s):
Theodore
A.
Slaman
Journal:
Proc. Amer. Math. Soc.
132
(2004),
2449-2456.
MSC (2000):
Primary 03F30, 03H15
Posted:
March 25, 2004
Retrieve article in:
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.
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
|
Comments: webmaster@ams.org