The interpretability logic of peano arithmetic

Journal of Symbolic Logic 55 (3):1059-1089 (1990)
  Copy   BIBTEX

Abstract

PA is Peano arithmetic. The formula $\operatorname{Interp}_\mathrm{PA}(\alpha, \beta)$ 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, Pr PA (x), to the case of the formalized interpretability relation $\operatorname{Interp}_\mathrm{PA}(x, y)$ . The relevant modal logic, in addition to the usual provability operator `□', has a binary operator ` $\triangleright$ ' 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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,429

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Model-Theoretic Properties Characterizing Peano Arithmetic.Richard Kaye - 1991 - Journal of Symbolic Logic 56 (3):949-963.
Modal Analysis of Generalized Rosser Sentences.Vítězslav Švejdar - 1983 - Journal of Symbolic Logic 48 (4):986-999.
On First-Order Theories with Provability Operator.Sergei Artëmov & Franco Montagna - 1994 - Journal of Symbolic Logic 59 (4):1139-1153.
Quantum Mathematics.J. Michael Dunn - 1980 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1980:512 - 531.
Interpretability Over Peano Arithmetic.Claes Strannegård - 1999 - Journal of Symbolic Logic 64 (4):1407-1425.

Analytics

Added to PP
2009-01-28

Downloads
31 (#373,845)

6 months
1 (#417,143)

Historical graph of downloads
How can I increase my downloads?

References found in this work

The Unprovability of Consistency. An Essay in Modal Logic.C. Smoryński - 1979 - Journal of Symbolic Logic 46 (4):871-873.

Add more references