Abstract
This paper develops the philosophy and technology needed for adding a supremum operator to the interpretability logic \(\mathsf {ILM}\) of Peano Arithmetic (\(\mathsf {PA}\)). It is well-known that any theories extending \(\mathsf {PA}\) have a supremum in the interpretability ordering. While provable in \(\mathsf {PA}\), this fact is not reflected in the theorems of the modal system \(\mathsf {ILM}\), due to limited expressive power. Our goal is to enrich the language of \(\mathsf {ILM}\) by adding to it a new modality for the interpretability supremum. We explore different options for specifying the exact meaning of the new modality. Our final proposal involves a unary operator, the dual of which can be seen as a (nonstandard) provability predicate satisfying the axioms of the provability logic \(\mathsf {GL}\).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Berarducci, A.: The interpretability logic of Peano arithmetic. J. Symb. Logic 55, 1059–1089 (1990)
Boolos, G.: The Logic of Provability. Cambridge University Press, Cambridge (1993)
Ehrenfeucht, A., Feferman, S.: Representability op recursively enumerable sets in formal theories. Archiv für mathematische Logik und Grundlagenforschung 5(1), 37–41 (1961). doi:10.1007/BF01977641
Feferman, S.: Arithmetization of metamathematics in a general setting. Fundam. Math. 49, 35–92 (1960)
Guaspari, D.: Partially conservative extensions of arithmetic. Trans. Am. Math. Soc. 254, 47–68 (1979)
Hájek, P.: On interpretability in set theories I. Commun. Math. Univ. Carolinae 12, 73–79 (1971)
Hájek, P., Pudlák, P.: Metamathematics of First-Order Arithmetic. Springer, Berlin (1998)
Hájková, M., Hájek, P.: On interpretability in theories containing arithmetic. Fundam. Math. 76(2), 131–137 (1972). http://eudml.org/doc/214455
Henk, P., Pakhomov, F.: Slow and Ordinary Provability for Peano Arithmetic. ArXiv e-prints (2016)
Henk, P., Shavrukov, V. Yu.: A Solovay function for the least 1-inconsistent subtheory of PA. Prepublication Series. Report No. PP-2016-31. ILLC, University of Amsterdam (2016)
Hilbert, D., Bernays, P.: Grundlagen der Mathematik II. Springer, Berlin (1939). Second edition: 1970
Jeroslow, R.G.: Consistency statements in formal theories. Fundam. Math. 72, 17–40 (1971)
de Jongh, D., Jumelet, M., Montagna, F.: On the proof of Solovay’s theorem. Stud. Log. 50, 51–70 (1991)
de Jongh, D., Veltman, F.: Provability logics for relative interpretability. In: Mathematical logic, Proceedings of the Heyting 1988 summer school in Varna, Bulgaria, pp. 31–42. Plenum Press, Boston (1990)
Lindström, P.: On certain lattices of degrees of interpretability. Notre Dame J. Formal Logic 25(2), 127–140 (1984). doi:10.1305/ndjfl/1093870573
Lindström, P.: Some results on interpretability. In: F. Jensen, M. B.H., M. K.K. (eds.) Proceedings of the 5th Scandinavian Logic Symposium 1979, pp. 329–361. Aalborg University Press, Aalborg (1979)
Lindström, P.: On Parikh provability—an exercise in modal logic. In: H. Lagerlund, S. Lindström, R. Sliwinski (eds.) Modality Matters: Twenty-Five Essays in Honour of Krister Segerberg, Uppsala Philosophical Studies 53, pp. 279–288 (2006)
Löb, M.: Solution of a problem of Leon Henkin. J. Symb. Logic 20, 115–118 (1955)
Montagna, F.: On the algebraization of a Feferman’s predicate. Stud. Log. 37, 221–236 (1978)
Montague, R.: Theories incomparable with respect to relative interpretability. J. Symb. Logic 27(2), 195–211 (1962). http://projecteuclid.org/euclid.jsl/1183734432
Ono, H.: Reflection principles in fragments of Peano arithmetic. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 33, 317–333 (1987)
Orey, S.: Relative interpretations. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 7, 146–153 (1961)
Parikh, R.: Existence and feasibility in arithmetic. J. Symb. Logic 36(3), 494–508 (1971). http://www.jstor.org/stable/2269958
Shavrukov, V.: The logic of relative interpretability over Peano arithmetic (in Russian). Tech. Rep. No.5, Steklov Mathematical Institute, Moscow (1988)
Shavrukov, V.: A smart child of Peano’s. Notre Dame J. Formal Logic 35, 161–185 (1994)
Smoryński, C.: Arithmetic analogues of McAloon’s unique Rosser sentences. Arch. Math. Logic 28, 1–21 (1989)
Solovay, R.: Provability interpretations of modal logic. Israel J. Math. 25, 287–304 (1976)
Švejdar, V.: Degrees of interpretability. Comment. Math. Univ. Carolinae 19, 789–813 (1978)
Tarski, A., Mostowski, A., Robinson, R.: Undecidable Theories. North-Holland, Amsterdam (1953)
Visser, A.: Peano’s smart children: A provability logical study of systems with built-in consistency. Notre Dame J. Formal Logic 30, 161–196 (1989)
Visser, A.: An inside view of EXP. J. Symb. Logic 57, 131–165 (1992)
Visser, A.: An Overview of Interpretability Logic. In: M. Kracht, M. de Rijke, H. Wansing, M. Zakharyaschev (eds.) Advances in Modal Logic, vol 1, CSLI Lecture Notes, no. 87, pp. 307–359. Center for the Study of Language and Information, Stanford (1998)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Henk, P., Visser, A. Interpretability suprema in Peano Arithmetic. Arch. Math. Logic 56, 555–584 (2017). https://doi.org/10.1007/s00153-017-0557-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-017-0557-4