Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-22T20:29:03.415Z Has data issue: false hasContentIssue false
  • English
  • Français

TWO NEW SERIES OF PRINCIPLES IN THE INTERPRETABILITY LOGIC OF ALL REASONABLE ARITHMETICAL THEORIES

Published online by Cambridge University Press:  12 December 2019

EVAN GORIS  and
JOOST J. JOOSTEN
EVAN GORIS
Affiliation:
INDEPENDENT SCHOLAR E-mail: [email protected]
JOOST J. JOOSTEN
Affiliation:
DEPARTMENT OF PHILOSOPHY UNIVERSITY OF BARCELONA C. MONTALEGRE 6 08001 BARCELONA CATALONIA, SPAIN E-mail: [email protected]: http://www.phil.uu.nl/~jjoosten/
Get access Rights & Permissions [Opens in a new window]

Abstract

The provability logic of a theory T captures the structural behavior of formalized provability in T as provable in T itself. Like provability, one can formalize the notion of relative interpretability giving rise to interpretability logics. Where provability logics are the same for all moderately sound theories of some minimal strength, interpretability logics do show variations.

The logic IL (All) is defined as the collection of modal principles that are provable in any moderately sound theory of some minimal strength. In this article we raise the previously known lower bound of IL (All) by exhibiting two series of principles which are shown to be provable in any such theory. Moreover, we compute the collection of frame conditions for both series.

Keywords

03B4503B6003F3003F4003F45interpretability logicsinterpretationsdefinable cutsweak arithmeticsformal provability
Type
Articles
Information
The Journal of Symbolic Logic , Volume 85 , Issue 1 , March 2020 , pp. 1 - 25
Copyright
Copyright © The Association for Symbolic Logic 2019 

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

Berarducci, A., The interpretability logic of peano arithmetic, this Journal, vol. 55 (1990), no. 3, pp. 1059–1089.Google Scholar
Buss, S., Bounded Arithmetic, Bibliopolis, Napoli, 1986.Google Scholar
de Jongh, D. H. J. and Veltman, F., Provability logics for relative interpretability, Mathematical Logic, Proceedings of the Heyting 1988 Summer School in Varna, Bulgaria (Petkov, P. P., editor), Plenum Press, Boston, 1990, pp. 31–42.Google Scholar
Goris, E. and Joosten, J. J., A new principle in the interpretability logic of all reasonable arithmetical theories. Logic Journal of the IGPL, vol. 19 (2011), no. 1, pp. 14–17.Google Scholar
Hájek, P. and Pudlák, P., Metamathematics of First Order Arithmetic, Springer-Verlag, Berlin, 1993.Google Scholar
Joosten, J. J., Towards the interpretability logic of all reasonable arithmetical theories, Master’s thesis, University of Amsterdam, 1998.Google Scholar
Joosten, J. J., On formalizations of the Orey-Hájek characterization for interpretability, Studies in Weak Arithmetics (Cegielski, P., Enayat, A., and Kossak, R., editors), CSLI Publications, Stanford, CA, 2016, pp. 57–90.Google Scholar
Joosten, J. J. and Visser, A., The interpretability logic of all reasonable arithmetical theories. The new conjecture, Erkenntnis, vol. 53 (2000), no. 1–2, pp. 3–26.CrossRefGoogle Scholar
Joosten, J. J. and Visser, A., How to derive principles of interpretability logic, A toolkit, Liber amicorum for Dick de Jongh (van Benthem, J., Troelstra, F., Veltman, A., and Visser, A., editors), Intitute for Logic, Language and Computation, 2004.Google Scholar
Mycielski, J., Pudlák, P., and Stern, A.S., A Lattice of Chapters of Mathematics (Interpretations between Theorems), Memoirs of the American Mathematical Society, vol. 426, AMS, Providence, RI, 1990.Google Scholar
Shavrukov, V. Y., The logic of relative interpretability over Peano arithmetic. Steklov Mathematical Institute, Moscow, preprint, 1988, In Russian.Google Scholar
Tarski, A., Mostowski, A., and Robinson, R., Undecidable Theories, North-Holland, Amsterdam, 1953.Google Scholar
Visser, A., Preliminary notes on interpretability logic, Technical report LGPS 29, Department of Philosophy, Utrecht University, 1988.Google Scholar
Visser, A., Interpretability logic, Mathematical Logic, Proceedings of the Heyting 1988 Summer School in Varna, Bulgaria (Petkov, P. P., editor), Plenum Press, Boston, 1990, pp. 175–209.Google Scholar
Visser, A., The formalization of interpretability. Studia Logica, vol. 50 (1991), no. 1, pp. 81–106.CrossRefGoogle Scholar
Visser, A., An overview of interpretability logic, Advances in Modal Logic ’96 (Kracht, M., de Rijke, M., and Wansing, H., editors), CSLI Publications, Stanford, CA, 1997, pp. 307–359.Google Scholar
Visser, A., The arithmetics of a theory. Notre Dame Journal of Formal Logic, vol. 56 (2015), no. 1, pp. 81–119.CrossRefGoogle Scholar