Rad HAZU, Matematičke znanosti, Vol. 18 (2014), 1-5.

INTERPRETABILITY LOGIC IL DOES NOT HAVE FINITE SUBTREE PROPERTY

Vedran Čačić and Mladen Vuković

Abstract.   Usually, when a logic has finite model property (fmp), it also has a stronger, finite submodel property: every model can be reduced to a finite submodel. Or, at least, it has a finite subtree property, which is restricted to models that are trees. We prove that interpretability logic IL does not have finite subtree property.

2010 Mathematics Subject Classification.   03F45.

Key words and phrases.   Interpretability logic, Veltman models, finite model property.

References:

1. A. Berarducci, The interpretability logic of Peano arithmetic, J. Symbolic Logic 55 (1990), 1059-1089.
   MathSciNet     CrossRef

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

3. D. de Jongh and F. Veltman, Provability logics for relative interpretability, in: Mathematical Logic, Proceedings of the 1988 Heyting Conference (ed. P. P. Petkov), Plenum Press, New York, 1990, 31-42.
   MathSciNet

4. D. de Jongh and F. Veltman, Modal completeness of ILW, in: Essays Dedicated to Johan van Benthem on the Occasion of His 50th Birthday (eds. J. Gerbrandy, M. Marx, M. Rijke and Y. Venema), Amsterdam University Press, Amsterdam, 1999.

5. E. Goris and J. Joosten, Modal matters in interpretability logics, Log. J. IGPL, 16 (2008), 371-412.
   MathSciNet     CrossRef

6. G. Japaridze and D. de Jongh, The logic of provability, in: Handbook of Proof Theory, (ed. S. R. Buss), Elsevier, 1998, pp. 475-546.
   MathSciNet     CrossRef

7. A. Visser, An overview of interpretability logic, in: Advances in modal logic. Vol. 1. Selected papers from the 1st international workshop (AiML'96), Berlin, Germany, October 1996 (eds. Kracht, Marcus et al.), Stanford, CA: CSLI Publications, CSLI Lect. Notes. 87 (1998), pp. 307-359.
   MathSciNet