Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-28T15:44:30.107Z Has data issue: false hasContentIssue false
  • English
  • Français

An inside view of EXP; or, The closed fragment of the provability logic of IΔ0 + Ω1 with a prepositional constant for EXP

Published online by Cambridge University Press:  12 March 2014

Albert Visser
Albert Visser*
Affiliation:
Department of Philosophy, University of Utrecht, 3508 TC Utrecht, The Netherlands
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper I give a characterization of the closed fragment of the provability logic of I Δ0 + EXP with a propositional constant for EXP. In three appendices many details on arithmetization are provided.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 57 , Issue 1 , March 1992 , pp. 131 - 165
Copyright
Copyright © Association for Symbolic Logic 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Artemov, S. N. [80], Arithmetically complete modal theories, Semiotika i Informatika, vol. 14, pp. 115–133; English translation, American Mathematical Society Translations, ser. 2, vol. 135 (1987), pp. 39–54.Google Scholar
Artemov, S. N. [85], On modal logics axiomatizing provability, Izvestiya Akademii Nauk SSSR Seriya Matematicheskaya, vol. 49, pp. 1123–1154; English translation, Mathematics of the USSR Izvestiya, vol. 27 (1986), pp. 401–429.Google Scholar
Barendregt, H. P.et al. [86], Term graph rewriting, Internal Report No. 87, Department of Computer Science, University of Nijmegen, Nijmegen; also Report SYS-C87-01, School of Information Systems, University of East Anglia, Norwich.CrossRefGoogle Scholar
Bennet, H. J. [62], On spectra, Ph.D. thesis, Princeton University, Princeton, New Jersey.Google Scholar
Berarducci, A. [90], The interpretability logic of Peano arithmetic, this Journal, vol. 55, pp. 1059–1089.Google Scholar
Boolos, G. [76], On deciding the truth of certain statements involving the notion of consistency, this Journal, vol. 41, pp. 779–781.Google Scholar
Boolos, G. [79], The unprovability of consistency, Cambridge University Press, London.Google Scholar
Buss, S. [85], Bounded arithmetic, Ph.D. thesis, Princeton University, Princeton, New Jersey; reprint, Bibliopolis, Napoli, 1986.Google Scholar
Feferman, S. [60], Arithmetization of metamathematics in a general setting, Fundamenta Mathematicae, vol. 49, pp. 33–92.Google Scholar
Gaifman, H. and Dimitracopoulos, C. [82], Fragments of Peano's arithmetic and the MRDP theorem, Logic and algorithmic, Monographies de l'Enseignement Mathématique, vol. 30, Université de Genève, Genève, pp. 187–206.Google Scholar
Hájek, P. and Montagna, F. [90], The logic of Π1-conservativity, Archive for Mathematical Logic, vol. 30, pp. 113–123.CrossRefGoogle Scholar
Hájek, P. and Svejdar, V. [9?], A note on the normal form of closed formulas of interpretability logic, manuscript.Google Scholar
de Jongh, D. H. J. and Veltman, F. [90], Provability logics for relative interpretability, Mathematical logic (Petkov, P. P., editor), Plenum Press, New York, pp. 31–42.Google Scholar
de Jongh, D. H. J. and Visser, A. [89], Explicit fixed points in interpretability logic, Logic Group Preprint Series, no. 44, Department of Philosophy, University of Utrecht, Utrecht.CrossRefGoogle Scholar
Kalsbeek, M. B. [88], An Orey sentence for predicative arithmetic, ITLI Prepublication Series, no. X-88-01, Department of Mathematics and Computer Science, University of Amsterdam, Amsterdam.Google Scholar
Magari, R. [75], The diagonalizable algebras, Bolletino dell'Unione Matematica Italiana B, ser. 7, vol. 66, pp. 117–125.Google Scholar
Parikh, R. [71], Existence and feasibility in arithmetic, this Journal, vol. 36, pp. 494–508.Google Scholar
Paris, J. B. and Dimitracopoulos, C. [83], A note on the undefinability of cuts, this Journal, vol. 48, pp. 564–569.Google Scholar
Paris, J. and Wilkie, A. [87], On the scheme of induction for bounded arithmetic formulas, Annals of Pure and Applied Logic, vol. 35, pp. 261–302.Google Scholar
Pudlák, P. [83], Some prime elements in the lattice of interpretability types, Transactions of the American Mathematical Society, vol. 280, pp. 255–275.CrossRefGoogle Scholar
Pudlák, P.[85], Cuts, consistency statements and interpretability, this Journal, vol. 50, pp. 423–441.Google Scholar
Pudlák, P.[86], On the length of proofs of finitistic consistency statements in finitistic theories, Logic Colloquium '84 (Paris, J. B.et al., editors), North-Holland, Amsterdam, pp. 165–196.Google Scholar
Schwichtenberg, H. [77], Proof theory: some applications of cut-elimination, Handbook of Mathematical Logic (Barwise, J., editor), North-Holland, Amsterdam, pp. 867–895.Google Scholar
Shavrukov, V. Yu. [88], The logic of relative interpretability over Peano arithmetic, Preprint No. 5, Steklov Mathematical Institute, Academy of Sciences of the USSR, Moscow. (Russian)Google Scholar
Smoryński, C. [85], Self-reference and modal logic, Springer-Verlag, Berlin.Google Scholar
Svejdar, V. [83], Modal analysis of generalized Rosser sentences, this Journal, vol. 48, pp. 986–999.Google Scholar
Svejdar, V.[89], Some independence results in interpretability logic, manuscript.Google Scholar
Takeuti, G. [88], Bounded arithmetic and truth definition, Annals of Pure and Applied Logic, vol. 36, pp. 75–104.Google Scholar
Verbrugge, L. C. [88], Does Solovay's completeness theorem extend to bounded arithmetic? Master's thesis, Department of Mathematics and Computer Science, University of Amsterdam, Amsterdam.Google Scholar
Verbrugge, L. C. [89], Σ-completeness and bounded arithmetic, ITLI Prepublication Series, no. ML-89-05, Department of Mathematics and Computer Science, University of Amsterdam, Amsterdam.Google Scholar
Visser, A. [85], Evaluation, provably deductive equivalence in Heyting's arithmetic of substitution instances of prepositional formulas, Logic Group Preprint Series, no. 4, Department of Philosophy, University of Utrecht, Utrecht.Google Scholar
Visser, A. [88], Preliminary notes on interpretability logic, Logic Group Preprint Series, no. 29, Department of Philosophy, University of Utrecht, Utrecht.Google Scholar
Visser, A.[89], The formalization of interpretability, Logic Group Preprint Series, no. 47, Department of Philosophy, University of Utrecht, Utrecht (to appear in Studia Logica).CrossRefGoogle Scholar
Visser, A.[90], Interpretability logic, Mathematical logic (Petkov, P. P., editor), Plenum Press, New York, pp. 175–208.Google Scholar