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] Samuel R. Buss, Bounded arithmetic, Studies in Proof Theory. Lecture Notes, vol. 3, Bibliopolis, Naples, 1986. MR 880863
  • [2] Rohit Parikh, Existence and feasibility in arithmetic, J. Symbolic Logic 36 (1971), 494–508. MR 0304152,
  • [3] J. B. Paris, Some conservation results for fragments of arithmetic, Model theory and arithmetic (Paris, 1979–1980) Lecture Notes in Math., vol. 890, Springer, Berlin-New York, 1981, pp. 251–262. MR 645006
  • [4] J. B. Paris and L. A. S. Kirby, Σ_{𝑛}-collection schemas in arithmetic, Logic Colloquium ’77 (Proc. Conf., Wrocław, 1977) Stud. Logic Foundations Math., vol. 96, North-Holland, Amsterdam-New York, 1978, pp. 199–209. MR 519815
  • [5] J. P. Ressayre, A conservation result for systems of bounded arithmetic, handwritten notes, 1985.
  • [6] Gaisi Takeuti, Proof theory, 2nd ed., Studies in Logic and the Foundations of Mathematics, vol. 81, North-Holland Publishing Co., Amsterdam, 1987. With an appendix containing contributions by Georg Kreisel, Wolfram Pohlers, Stephen G. Simpson and Solomon Feferman. MR 882549

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