Interpreting reflexive theories in finitely many axioms

V. Shavrukov

Fundamenta Mathematicae (1997)

  • Volume: 152, Issue: 2, page 99-116
  • ISSN: 0016-2736

Abstract

top
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 Σ 3 0 -complete.

How to cite

top

Shavrukov, V.. "Interpreting reflexive theories in finitely many axioms." Fundamenta Mathematicae 152.2 (1997): 99-116. <http://eudml.org/doc/212206>.

@article{Shavrukov1997,
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.},
author = {Shavrukov, V.},
journal = {Fundamenta Mathematicae},
keywords = {relative interpretability; finitely axiomatized sequential theories; reflexive theories; provability of restricted consistency statements on cuts},
language = {eng},
number = {2},
pages = {99-116},
title = {Interpreting reflexive theories in finitely many axioms},
url = {http://eudml.org/doc/212206},
volume = {152},
year = {1997},
}

TY - JOUR
AU - Shavrukov, V.
TI - Interpreting reflexive theories in finitely many axioms
JO - Fundamenta Mathematicae
PY - 1997
VL - 152
IS - 2
SP - 99
EP - 116
AB - 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.
LA - eng
KW - relative interpretability; finitely axiomatized sequential theories; reflexive theories; provability of restricted consistency statements on cuts
UR - http://eudml.org/doc/212206
ER -

References

top
  1. [1] A. Berarducci and P. D’Aquino, Δ 0 -complexity of the relation y = i n F ( i ) , Ann. Pure Appl. Logic 75 (1995), 49-56. 
  2. [2] A. Berarducci and R. Verbrugge, On the provability logic of bounded arithmetic, ibid. 61 (1993), 75-93. Zbl0803.03037
  3. [3] B S. R. Buss, Bounded Arithmetic, Bibliopolis, Napoli, 1986. 
  4. [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. [5] P. Hájek and P. Pudlák, Metamathematics of First-Order Arithmetic, Springer, Berlin, 1993. Zbl0781.03047
  6. [6] J R. G. Jeroslow, Non-effectiveness in S. Orey's arithmetical compactness theorem, Z. Math. Logic Grundlangen Math. 17 (1971), 285-289. Zbl0234.02036
  7. [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. [8] P. Lindström, On partially conservative sentences and interpretability, Proc. Amer. Math. Soc. 91 (1984), 436-443. Zbl0577.03028
  9. [9] J. Paris and A. Wilkie, Counting Δ 0 sets, Fund. Math. 127 (1986), 67-76. Zbl0627.03018
  10. [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. Zbl0688.03042
  11. [11] P. Pudlák, Cuts, consistency statements and interpretations, J. Symbolic Logic 50 (1985), 423-441. Zbl0569.03024
  12. [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. [13] W. Sieg, Fragments of arithmetic, Ann. Pure Appl. Logic 28 (1985), 33-71. Zbl0558.03029
  14. [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. [15] V. Švejdar, A sentence that is difficult to interpret, Comment. Math. Univ. Carolin 22 (1981), 661-666. Zbl0484.03032
  16. [16] A. Visser, Interpretability logic, in: Mathematical Logic, P. P. Petkov (ed.), Plenum Press, New York, 1990, 175-209. Zbl0793.03064
  17. [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. Zbl0785.03008
  18. [18] A. Visser, The unprovability of small inconsistency, A study of local and global interpretability, Arch. Math. Logic 32 (1993), 275-298. Zbl0795.03080
  19. [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. [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. Zbl0647.03046

NotesEmbed ?

top

You must be logged in to post comments.