The Modelwise Interpolation Property of Semantic Logics

Gyenis, Zalán  ; Molnár, Zalán ; Öztürk, Övge

Bulletin of the Section of Logic, Tome 52 (2023) no. 1, pp. 59-83.

Résumé

In this paper we introduce the modelwise interpolation property of a logic that states that whenever ϕ→ψ holds for two formulas ϕ and ψ, then for every model 𝔐 there is an interpolant formula χ formulated in the intersection of the vocabularies of ϕ and ψ, such that 𝔐ϕ→χ and 𝔐χ→ψ, that is, the interpolant formula in Craig interpolation may vary from model to model. We compare the modelwise interpolation property with the standard Craig interpolation and with the local interpolation property by discussing examples, most notably the finite variable fragments of first order logic, and difference logic. As an application we connect the modelwise interpolation property with the local Beth definability, and we prove that the modelwise interpolation property of an algebraizable logic can be characterized by a weak form of the superamalgamation property of the class of algebras corresponding to the models of the logic.

Détail

Keywords: interpolation, algebraic logic, amalgamation, superamalgamation

Bibliographie

[1] H. Andréka, Z. Gyenis, I. Németi, I. Sain, Universal Algebraic Logic, Birkhauser (2022) | DOI

[2] H. Andréka, J. X. Madarász, I. Németi, Logic of Space-Time and Relativity Theory, [in:] M. Aiello, I. Pratt-Hartmann, J. Van Benthem (eds.), Handbook of Spatial Logics, Springer Netherlands, Dordrecht (2007), pp. 607–711 | DOI

[3] H. Andréka, I. Németi, I. Sain, Algebraic logic, [in:] Handbook of Philosophical Logic, vol. 2, Kluwer Academic Publishers, Dordrecht (2001), pp. 133–247.

[4] H. Andréka, I. Németi, J. van Benthem, Interpolation and Definability Properties of Finite Variable Fragments, Reports of the Mathematical Institute, Hungarian Academy of Sciences, (1993).

[5] H. Andréka, I. Németi, J. van Benthem, Modal languages and bounded fragments of predicate logic, Journal of Philosophical Logic, vol. 27(3) (1998), pp. 217–274 | DOI

[6] J. Barwise, On Moschovakis closure ordinals, Journal of Symbolic Logic, vol. 42(2) (1977), p. 292–296 | DOI

[7] P. Blackburn, M. d. Rijke, Y. Venema, Modal Logic, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press (2001) | DOI

[8] W. J. Blok, D. Pigozzi, Algebraizable logics, Memoirs of the American Mathematical Society, vol. 77(396) (1989), pp. vi+78 | DOI

[9] W. J. Blok, D. Pigozzi, Abstract Algebraic Logic, Lecture Notes of the Summer School “Algebraic Logic and the Methodology of Applying it”, Budapest, (1994).

[10] W. J. Blok, D. L. Pigozzi, Local deduction theorems in algebraic logic, [in:] Algebraic logic (Budapest, 1988), vol. 54 of Colloquia Mathematica Societatis János Bolyai, North-Holland, Amsterdam (1991), pp. 75–109.

[11] W. Conradie, Definability and changing perspectives, Master’s thesis, University of Amsterdam (2002).

[12] J. Czelakowski, Logical matrices and the amalgamation property, Studia Logica, vol. 41(4) (1982), pp. 329–341 (1983) | DOI

[13] J. Czelakowski, D. Pigozzi, Amalgamation and interpolation in abstract algebraic logic, [in:] Models, algebras, and proofs (Bogotá, 1995), vol. 203 of Lecture Notes in Pure and Applied Mathematics, Dekker, New York (1999), pp. 187–265 | DOI

[14] J. Czelakowski, D. Pigozzi, Fregean logics, Annals of Pure and Applied Logic, vol. 127(1-3) (2004), pp. 17–76 | DOI

[15] Z. Gyenis, Interpolation property and homogeneous structures, Logic Journal of the IGPL, vol. 22(4) (2014), pp. 597–607 | DOI

[16] Z. Gyenis, Algebraic characterization of the local Craig interpolation property, Bulletin of the Section of Logic, vol. 47(1) (2018), pp. 45–58 | DOI

[17] E. Hoogland, Algebraic characterizations of two Beth definability properties, Master’s thesis, Universiteit van Amsterdam (1996).

[18] E. Hoogland, Definability and Interpolation, model-theoretic investigations, Ph.D. thesis, Institute for Logic, Language and Computation, Universiteit van Amsterdam (2001).

[19] P. Krzystek, S. Zachorowski, Lukasiewicz logics have not the interpolation property, Reports on Mathematical Logic, vol. 9 (1977), pp. 39–40.

[20] J. X. Madarász, Interpolation and amalgamation; pushing the limits. I, Studia Logica, vol. 61(3) (1998), pp. 311–345 | DOI

[21] J. X. Madarász, I. Németi, G. Székely, First-Order Logic Foundation of Relativity Theories, [in:] D. M. Gabbay, M. Zakharyaschev, S. S. Goncharov (eds.), Mathematical Problems from Applied Logic II: Logics for the XXIst Century, Springer New York, New York, NY (2007), pp. 217–252 | DOI

[22] L. Maksimova, Amalgamation and interpolation in normal modal logic, Studia Logica, vol. 50(3-4) (1991), pp. 457–471, algebraic logic. | DOI

[23] L. L. Maksimova, Interpolation theorems in modal logics and amalgamable varieties of topological Boolean algebras, Algebra i Logika, vol. 18(5) (1979), pp. 556–586, 632.

[24] P. Mancosu, Introduction: Interpolations—essays in honor of William Craig, Synthese, vol. 164(3) (2008), pp. 313–319 | DOI

[25] G. Metcalfe, F. Montagna, C. Tsinakis, Amalgamation and interpolation in ordered algebras, Journal of Algebra, vol. 402 (2014), pp. 21–82 | DOI

[26] D. Mundici, Consequence and Interpolation in Lukasiewicz Logic, Studia Logica, vol. 99(1/3) (2011), pp. 269–278, URL: http://www.jstor.org/stable/41475204

[27] D. Nyiri, The Robinson property and amalgamations of higher arities, Mathematical Logic Quarterly, vol. 62(4–5) (2016), pp. 427–433 | DOI

[28] D. Pigozzi, Amalgamation, congruence-extension, and interpolation properties in algebras, Algebra Universalis, vol. 1 (1971/72), pp. 269–349 | DOI

[29] D. J. Pigozzi, Fregean algebraic logic, [in:] Algebraic logic (Budapest, 1988), vol. 54 of Colloquia Mathematica Societatis János Bolyai, North-Holland, Amsterdam (1991), pp. 473–502.

[30] G. Priest, An Introduction to Non-Classical Logic: From If to Is, Cambridge University Press (2008).

[31] D. Roorda, Resource Logics. Proof-Theoretical Investigations, Ph.D. thesis, Institute for Logic, Language and Computation, University of Amsterdam (1991).

[32] G. Sági, S. Shelah, On weak and strong interpolation in algebraic logics, The Journal of Symbolic Logic, vol. 71(1) (2006), pp. 104–118 | DOI

[33] I. Sain, Successor axioms for time increase the program verifying power of full computational induction, Mathematical Institute if the Hungarian Academy of Sciences, vol. 23 (1983).

[34] I. Sain, Is “some-other-time” sometimes better than “sometime” for proving partial correctness of programs?, Studia Logica, vol. 47(3) (1988), pp. 279–301 | DOI

[35] I. Sain, Beth’s and Craig’s properties via epimorphisms and amalgamation in algebraic logic, [in:] Algebraic Logic and Universal Algebra in Computer Science (Ames, IA, 1988), vol. 425 of Lecture Notes in Computer Science, Springer, Berlin (1990), pp. 209–225 | DOI

[36] K. Segerberg, “Somewhere else” and “Some other time”, [in:] Wright and Wrong — Mini essays in honor of Georg Henrik von Wright, vol. 3 of Publications, Group in Logic and Methodology of Real Finland (1976), pp. 61–64.

[37] S. J. van Gool, G. Metcalfe, C. Tsinakis, Uniform interpolation and compact congruences, Annals of Pure and Applied Logic, vol. 168(10) (2017), pp. 1927–1948 | DOI

[38] Y. Venema, Many-dimensional Modal Logic, Ph.D. thesis, Institute for Logic, Language and Computation, University of Amsterdam (1992).