Rad HAZU, Matematičke znanosti, Vol. 29 (2025), 23-35.

SELECTION METHOD FOR INTERPRETABILITY LOGIC IL WITH RESPECT TO VERBRUGGE SEMANTICS

Sebastijan Horvat and Tin Perkov

University of Zagreb, Faculty of Teacher Education, Savska c. 77, 10 000 Zagreb, Croatia
e-mail: tin.perkov@ufzg.hr

Abstract.   Interpretability logic is a modal logic which formalizes the notion of relative interpretability between first-order arithmetical theories. Veltman semantics is the basic semantics for interpretability logic. Verbrugge semantics is a generalization of Veltman semantics. Selection is one of the methods to establish finite model property of a logical system, as a step towards showing that the system is decidable. In this paper we show that selection method can be applied to Verbrugge models, by adapting techniques used for Kripke models to this more complex setting.

2020 Mathematics Subject Classification.   03F45.

Key words and phrases.   Interpretability logic, Verbrugge models, finite model property, selection method.

DOI: https://doi.org/10.21857/moxpjhzdem

References:

1. P. Blackburn, M. de Rijke and Y. Venema, Modal Logic, Cambridge University Press, 2001.
   MathSciNet     CrossRef

2. V. Čačić and M. Vuković, Interpretability logic IL does not have finite subtree property, Rad Hrvat. Akad. Znan. Umjet. Mat. Znan. 18 (2014), 1-5.
   MathSciNet

3. V. Goranko and M. Otto, Model theory for modal logic, in: Handbook of Modal Logic (eds. P. Blackburn, J. van Benthem and F. Wolter), Elsevier, 2007, 249-329.
   MathSciNet

4. S. Horvat, T. Perkov and M. Vuković, Bisimulations and bisimulation games between Verbrugge models, MLQ Math. Log. Q. 69 (2023), 231-243.
   MathSciNet     CrossRef

5. L. Mikec, T. Perkov and M. Vuković, Decidability of interpretability logics ILM₀ and ILW^*, Log. J. IGPL 25 (2017), 758-772.
   MathSciNet     CrossRef

6. L. Mikec and M. Vuković, Interpretability logics and generalized Veltman semantics, J. Symb. Log. 85 (2020), 749-772.
   MathSciNet     CrossRef

7. T. Perkov and M. Vuković, Filtrations of generalized Veltman models, MLQ Math. Log. Q. 62 (2016), 412-419
   MathSciNet     CrossRef

8. A. Visser, An overview of interpretability logic, in: Advances in Modal Logic (ed. M. Kracht), Volume 1, CSLI Publications 87, Stanford, 1998, 307-359.
   MathSciNet

9. D. Vrgoč and M. Vuković, Bisimulations and bisimulation quotients of generalized Veltman models, Log. J. IGPL 18 (2010), 870-880.
   MathSciNet     CrossRef