Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

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



A conservation result concerning bounded theories and the collection axiom

Author: Samuel R. Buss
Journal: Proc. Amer. Math. Soc. 100 (1987), 709-715
MSC: Primary 03F30; Secondary 03C62
MathSciNet review: 894442
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present two proofs, one proof-theoretic and one model-theoretic, showing that adding the $ B\Sigma _1^0$-collection axioms to any bounded first-order theory $ R$ of arithmetic yields an extension which is $ \forall \Sigma _1^0$-conservative over $ R$.

References [Enhancements On Off] (What's this?)

  • [1] S. R. Buss, Bounded arithmetic, Bibliopolis, Naples, 1986. Revision of Ph. D. dissertation, Princeton University, 1985. MR 880863 (89h:03104)
  • [2] R. Parikh, Existence and feasibility in arithmetic, J. Symbolic Logic 36 (1971), 494-508. MR 0304152 (46:3287)
  • [3] J. B. Paris, Some conservation results for fragments of arithmetic, Model Theory and Arithmetic, Lecture Notes in Math., vol. 890, Springer-Verlag, Berlin and New York, 1980, pp. 251-262. MR 645006 (83f:03060)
  • [4] J. B. Paris and L. A. S. Kirby, $ {\Sigma _n}$-collection schemes in arithmetic, Logic Colloquium '77, North-Holland, Amsterdam, 1978, pp. 199-209. MR 519815 (81e:03056)
  • [5] J. P. Ressayre, A conservation result for systems of bounded arithmetic, handwritten notes, 1985.
  • [6] G. Takeuti, Proof theory, North-Holland, Amsterdam, 1975. MR 882549 (89a:03115)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03F30, 03C62

Retrieve articles in all journals with MSC: 03F30, 03C62

Additional Information

Keywords: Bounded arithmetic, collection axioms, cut elimination, resplendency
Article copyright: © Copyright 1987 American Mathematical Society

American Mathematical Society