Download PDF - Interpreting reflexive theories in finitely many axiomsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Interpreting reflexive theories in finitely many axioms

Authors 1

Affiliations

  1. Department of Philosophy, Utrecht University, Heidelberglaan 8, 3584 CS Utrecht, The Netherlands

Abstract

For finitely axiomatized sequential theories F and reflexive theories R, we give a characterization of the relation 'F interprets R' in terms of provability of restricted consistency statements on cuts. This characterization is used in a proof that the set of ∏1 (as well as ∑1) sentences π such that GB interprets ZF+π is Σ0_3-complete.

Bibliography

  1. A. Berarducci and P. D'Aquino, Δ0-complexity of the relation y=∏i≤nF(i), Ann. Pure Appl. Logic 75 (1995), 49-56.
  2. A. Berarducci and R. Verbrugge, On the provability logic of bounded arithmetic, ibid. 61 (1993), 75-93.
  3. B S. R. Buss, Bounded Arithmetic, Bibliopolis, Napoli, 1986.
  4. D P. D'Aquino, A sharpened version of McAloon's theorem on initial segments of models of IΔ0, Ann. Pure Appl. Logic 61 (1993), 49-62.
  5. P. Hájek and P. Pudlák, Metamathematics of First-Order Arithmetic, Springer, Berlin, 1993.
  6. J R. G. Jeroslow, Non-effectiveness in S. Orey's arithmetical compactness theorem, Z. Math. Logic Grundlangen Math. 17 (1971), 285-289.
  7. P. Lindström, Some results on interpretability, in: Proc. 5th Scandinavian Logic Sympos., F. V. Jensen, B. H. Mayoh and K. K. Møller (eds.), Aalborg Univ. Press, 1979, 329-361.
  8. P. Lindström, On partially conservative sentences and interpretability, Proc. Amer. Math. Soc. 91 (1984), 436-443.
  9. J. Paris and A. Wilkie, Counting Δ0 sets, Fund. Math. 127 (1986), 67-76.
  10. J. B. Paris, A. J. Wilkie and A. R. Woods, Provability of the pigeonhole principle and the existence of infinitely many primes, J. Symbolic Logic 53 (1988), 1235-1244.
  11. P. Pudlák, Cuts, consistency statements and interpretations, J. Symbolic Logic 50 (1985), 423-441.
  12. P. Pudlák, On the length of proofs of finitistic consistency statements in first order theories, in: Logic Colloquium '84, J. B. Paris, A. J. Wilkie and G. M. Wilmers (eds.), North-Holland, Amsterdam, 1986, 165-196.
  13. W. Sieg, Fragments of arithmetic, Ann. Pure Appl. Logic 28 (1985), 33-71.
  14. C. Smoryński, Nonstandard models and related developments, in: Harvey Friedman's Research on the Foundations of Mathematics, L. A. Harrington, M. D. Morley, A. Ščedrov and S. G. Simpson (eds.), North-Holland, Amsterdam, 1985, 179-229.
  15. V. Švejdar, A sentence that is difficult to interpret, Comment. Math. Univ. Carolin 22 (1981), 661-666.
  16. A. Visser, Interpretability logic, in: Mathematical Logic, P. P. Petkov (ed.), Plenum Press, New York, 1990, 175-209.
  17. A. Visser, An inside view of EXP; or, the closed fragment of the provability logic of IΔ0+Ω1 with a propositional constant for EXP, J. Symbolic Logic 57 (1992), 131-165.
  18. A. Visser, The unprovability of small inconsistency, A study of local and global interpretability, Arch. Math. Logic 32 (1993), 275-298.
  19. W A. J. Wilkie, On sentences interpretable in systems of arithmetic, in: Logic Colloquium '84, J. B. Paris, A. J. Wilkie and G. M. Wilmers (eds.), North-Holland, Amsterdam, 1986, 329-342.
  20. A. J. Wilkie and J. B. Paris, On the scheme of induction for bounded arithmetic formulas, Ann. Pure Appl. Logic 35 (1987), 261-302.
Fundamenta Mathematicae
1997/152/2
Export to PBN, Opens in new tab
Pages:
99-116
Main language of publication
English
Received
1995-08-15
Accepted
1996-10-22
Published
1997
Exact and natural sciences