Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-05T16:28:47.070Z Has data issue: false hasContentIssue false
  • English
  • Français

The interpretability logic of Peano arithmetic

Published online by Cambridge University Press:  12 March 2014

Alessandro Berarducci
Alessandro Berarducci*
Affiliation:
Via Stibbert 33-A, 50134 Firenze, Italy
Get access Rights & Permissions [Opens in a new window]

Abstract

PA is Peano arithmetic. The formula InterpPA(α, β) is a formalization of the assertion that the theory PA + α interprets the theory PA + β (the variables α and β are intended to range over codes of sentences of PA). We extend Solovay's modal analysis of the formalized provability predicate of PA, PrPA(x), to the case of the formalized interpretability relation InterpPA(x, y). The relevant modal logic, in addition to the usual provability operator ‘□’, has a binary operator ‘⊳’ to be interpreted as the formalized interpretability relation. We give an axiomatization and a decision procedure for the class of those modal formulas that express valid interpretability principles (for every assignment of the atomic modal formulas to sentences of PA). Our results continue to hold if we replace the base theory PA with Zermelo-Fraenkel set theory, but not with Gödel-Bernays set theory. This sensitivity to the base theory shows that the language is quite expressive. Our proof uses in an essential way earlier work done by A. Visser, D. de Jongh, and F. Veltman on this problem.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 55 , Issue 3 , September 1990 , pp. 1059 - 1089
Copyright
Copyright © Association for Symbolic Logic 1990

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

[1]Artemov, S. N., Nonarithmeticity of truth predicate logics of provability, Doklady Akademii Nauk SSSR, vol. 284 (1985), pp. 270–271; English translation, Soviet Mathematics Doklady, vol. 32 (1985), pp. 403–405.Google Scholar
[2]Berarducci, Alessandro, The interpretability logic of Peano arithmetic (preliminary version), Manuscript, 1988.Google Scholar
[3]Berarducci, Alessandro, Σn0 interpretations of modal logic, Bollettino dell'Unione Matematica Italiana, ser. 7, vol. 3-A (1989), pp. 177–184.Google Scholar
[4]Boolos, George, The unprovability of consistency, Cambridge University Press, Cambridge, 1979.Google Scholar
[5]de Jongh, Dick and Veltman, Frank, Provability logics for relative interpretability, Proceedings of Heyting '88 (to appear).Google Scholar
[6]Feferman, Solomon, Arithmetization of metamathematics in a general setting, Fundamenta Mathematicae, vol. 49 (1960), pp. 33–92.CrossRefGoogle Scholar
[7]Friedman, Harvey, Translatability and relative consistency. II, manuscript.Google Scholar
[8]Lindström, Per, Some results on interpretability, Proceedings from 5th Scandinavian logic symposium (Jensen, F. V.et al., editors), Aalborg University Press, Aalborg, 1979, pp. 329–361.Google Scholar
[9]Lindström, Per, Provability and interpretability in theories containing arithmetic, Atti degli incontri di logica matematica (Siena, 1983, 1984; Bernardi, C. and Pagli, P., editors), Vol. 2, Università di Siena, Siena, 1985, pp. 431–451.Google Scholar
[10]Montague, Richard, Semantical closure and non-finite axiomatizability. I, Infinitistic methods (proceedings of the symposium on foundations of mathematics, Warsaw, 1959), PWN, Warsaw, and Pergamon Press, Oxford, 1961, pp. 45–69.Google Scholar
[11]Pudlák, Pavel, Cuts, consistency statements and interpretability, this Journal, vol. 50 (1985), pp. 423–441.Google Scholar
[12]Schwichtenberg, Helmut, Some applications of cut-elimination, Handbook of mathematical logic, North-Holland, Amsterdam, 1977, pp. 867–895.CrossRefGoogle Scholar
[13]Shavrukov, V. Yu., Logic of relative interpretability over Peano arithmetic, Preprint No. 5, Steklov Mathematical Institute, Academy of Sciences of the USSR, Moscow, 12 1988.Google Scholar
[14]Smoryński, C., Nonstandard models and related developments in the work of Harvey Friedman, Harvey Friedman's research on the foundations of mathematics, North-Holland, Amsterdam, 1985, pp. 212–229.Google Scholar
[15]Smoryński, C., Self-reference and modal logic, Springer-Verlag, Berlin, 1985.CrossRefGoogle Scholar
[16]Solovay, Robert M., Provability interpretations of modal logic, Israel Journal of Mathematics, vol. 25(1976), pp. 287–304.CrossRefGoogle Scholar
[17]Vardanyan, V. A., Arithmetic complexity of predicate logics of provability and their fragments, Doklady Akademii Nauk SSSR, vol. 288 (1986), pp. 11–14; English translation in Soviet Mathematics Doklady, vol. 33 (1986), pp. 569–572.Google Scholar
[18]Visser, Albert, Preliminary notes on interpretability logic, Logic group preprint series, no. 29, Department of Philosophy, University of Utrecht, Utrecht, 1988.Google Scholar
[19]Visser, Albert, Interpretability logic, Logic group preprint series, no. 40, Department of Philosophy, University of Utrecht, Utrecht, 1988.Google Scholar