Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-24T03:40:53.794Z Has data issue: false hasContentIssue false
  • English
  • Français

INTERPRETABILITY LOGICS AND GENERALISED VELTMAN SEMANTICS

Part of: Proof theory and constructive mathematics General logic

Published online by Cambridge University Press:  18 June 2020

LUKA MIKEC  and
MLADEN VUKOVIĆ
LUKA MIKEC
Affiliation:
DEPARTMENT OF MATHEMATICS FACULTY OF SCIENCE, UNIVERSITY OF ZAGREB BIJENIčKA 30, ZAGREB, CROATIAE-mail: [email protected]: [email protected]
MLADEN VUKOVIĆ
Affiliation:
DEPARTMENT OF MATHEMATICS FACULTY OF SCIENCE, UNIVERSITY OF ZAGREB BIJENIčKA 30, ZAGREB, CROATIAE-mail: [email protected]: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We obtain modal completeness of the interpretability logics IL $\!\!\textsf {P}_{\textsf {0}}$ and ILR w.r.t. generalised Veltman semantics. Our proofs are based on the notion of full labels [2]. We also give shorter proofs of completeness w.r.t. the generalised semantics for many classical interpretability logics. We obtain decidability and finite model property w.r.t. the generalised semantics for IL $\textsf {P}_{\textsf {0}}$ and ILR. Finally, we develop a construction that might be useful for proofs of completeness of extensions of ILW w.r.t. the generalised semantics in the future, and demonstrate its usage with $\textbf {IL}\textsf {W}^\ast = \textbf {IL}\textsf {WM}_{\textsf {0}}$ .

Keywords

interpretability logicVeltman semanticscompletenessfinite model propertydecidability

MSC classification

Primary: 03B45: Modal logic (including the logic of norms)
Secondary: 03B60: Other nonclassical logic 03F45: Provability logics and related algebras (e.g., diagonalizable algebras)
Type
Articles
Information
The Journal of Symbolic Logic , Volume 85 , Issue 2 , June 2020 , pp. 749 - 772
Copyright
© The Association for Symbolic Logic 2020

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
Bílková, M., Goris, E., and Joosten, J.J.. Smart labels, Liber Amicorum for Dick de Jongh (Afanasiev, L. and Marx, M., editors), Institute for Logic, Language and Computation, Amsterdam, 2004.Google Scholar
de Jongh, D.H.J. and Veltman, F.J.M.M.. 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., Modal matters for interpretability logics . Logic Journal of the IGPL, vol. 16 (2008), no. 4, pp. 371–412.CrossRefGoogle 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. 1–17.CrossRefGoogle Scholar
Goris, E. and Joosten, J. J., Two new series of principles in the interpretability logic of all reasonable arithmetical theories , this Journal, vol. 85 (2020), pp. 1–26.Google Scholar
de Jongh, D.H.J. and Veltman, F.J.M.M., Modal completeness of ILW , Essays Dedicated to Johan van Benthem on the Occasion of His 50th Birthday (Gerbrandy, J., Marx, M., de Rijke, M., and Venema, Y., editors), Amsterdam University Press, Amsterdam, 1999.Google Scholar
Mikec, L., Perkov, T., and Vuković, M., Decidability of interpretability logics ILM 0 and ILW* . Logic Journal of the IGPL, vol. 25 (2017), no. 5, pp. 758–772.CrossRefGoogle Scholar
Perkov, T. and Vuković, M., Filtrations of generalized Veltman models . Mathematical Logic Quarterly, vol. 62 (2016), no. 4–5, pp. 412–419.CrossRefGoogle Scholar
Shavrukov, V., The Logic of Relative Interpretability Over Peano Arithmetic, Steklov Mathematical Institute, Moscow, 1988.Google Scholar
Solovay, R. M., Provability interpretations of modal logic . Israel Journal of Mathematics, vol. 25 (1976), no. 3, pp. 287–304.CrossRefGoogle Scholar
Verbrugge, L.C., Verzamelingen-Veltman frames en modellen (set Veltman frames and models). Unpublished manuscript, Amsterdam, 1992.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., An overview of interpretability logic , Advances in Modal Logic, vol. 1 (Kracht, M., de Rijke, M., Wansing, H., and Zakharyaschev, M., editors), CSLI Publications, Stanford, CA, 1998, pp. 307–359.Google Scholar
Vrgoč, D. and Vuković, M., Bisimulations and bisimulation quotients of generalized Veltman models . Logic Journal of the IGPL, vol. 18 (2010), no. 6, pp. 870–880.CrossRefGoogle Scholar
Vuković, M., The principles of interpretability . Notre Dame Journal of Formal Logic, vol. 40 (1999), no. 2, pp. 227–235.CrossRefGoogle Scholar
Vuković, M., Bisimulations between generalized Veltman models and Veltman models . Mathematical Logic Quarterly, vol. 54 (2008), no. 4, pp. 368–373.CrossRefGoogle Scholar