The Modelwise Interpolation Property of Semantic Logics

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

doi:10.18778/0138-0680.2023.09

Authors

Zalán Gyenis Jagiellonian University, Institute of Philosophy, ul. Grodzka 52, 31-044 Kraków, Poland https://orcid.org/0000-0003-2058-1255
Zalán Molnár Eötvös Loránd University, Department of Logic, Múzeum krt. 4., 1088 Budapest, Hungary
Övge Öztürk Eötvös Loránd University, Department of Logic, Múzeum krt. 4., 1088 Budapest, Hungary

DOI:

https://doi.org/10.18778/0138-0680.2023.09

Keywords:

interpolation, algebraic logic, amalgamation, superamalgamation

Abstract

In this paper we introduce the modelwise interpolation property of a logic that states that whenever \(\models\phi\to\psi\) holds for two formulas \(\phi\) and \(\psi\), then for every model \(\mathfrak{M}\) there is an interpolant formula \(\chi\) formulated in the intersection of the vocabularies of \(\phi\) and \(\psi\), such that \(\mathfrak{M}\models\phi\to\chi\) and \(\mathfrak{M}\models\chi\to\psi\), 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.

References

H. Andréka, Z. Gyenis, I. Németi, I. Sain, Universal Algebraic Logic, Birkhauser (2022), DOI: https://doi.org/10.1007/978-3-031-14887-3
Google Scholar DOI: https://doi.org/10.1007/978-3-031-14887-3

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: https://doi.org/10.1007/978-1-4020-5587-4_11
Google Scholar DOI: https://doi.org/10.1007/978-1-4020-5587-4_11

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.
Google Scholar DOI: https://doi.org/10.1007/978-94-017-0452-6_3

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).
Google Scholar

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: https://doi.org/10.1023/A:1004275029985
Google Scholar DOI: https://doi.org/10.1023/A:1004275029985

J. Barwise, On Moschovakis closure ordinals, Journal of Symbolic Logic, vol. 42(2) (1977), p. 292–296, DOI: https://doi.org/10.2307/2272133
Google Scholar DOI: https://doi.org/10.2307/2272133

P. Blackburn, M. d. Rijke, Y. Venema, Modal Logic, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press (2001), DOI: https://doi.org/10.1017/CBO9781107050884
Google Scholar DOI: https://doi.org/10.1017/CBO9781107050884

W. J. Blok, D. Pigozzi, Algebraizable logics, Memoirs of the American Mathematical Society, vol. 77(396) (1989), pp. vi+78, DOI: https://doi.org/10.1090/memo/0396
Google Scholar DOI: https://doi.org/10.1090/memo/0396

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

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.
Google Scholar

W. Conradie, Definability and changing perspectives, Master’s thesis, University of Amsterdam (2002).
Google Scholar

J. Czelakowski, Logical matrices and the amalgamation property, Studia Logica, vol. 41(4) (1982), pp. 329–341 (1983), DOI: https://doi.org/10.1007/BF00403332
Google Scholar DOI: https://doi.org/10.1007/BF00403332

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: https://doi.org/10.1201/9780429332890
Google Scholar DOI: https://doi.org/10.1201/9780429332890

J. Czelakowski, D. Pigozzi, Fregean logics, Annals of Pure and Applied Logic, vol. 127(1-3) (2004), pp. 17–76, DOI: https://doi.org/10.1016/j.apal.2003.11.008
Google Scholar DOI: https://doi.org/10.1016/j.apal.2003.11.008

Z. Gyenis, Interpolation property and homogeneous structures, Logic Journal of the IGPL, vol. 22(4) (2014), pp. 597–607, DOI: https://doi.org/10.1093/jigpal/jzt051
Google Scholar DOI: https://doi.org/10.1093/jigpal/jzt051

Z. Gyenis, Algebraic characterization of the local Craig interpolation property, Bulletin of the Section of Logic, vol. 47(1) (2018), pp. 45–58, DOI: https://doi.org/10.18778/0138-0680.47.1.04
Google Scholar DOI: https://doi.org/10.18778/0138-0680.47.1.04

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

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

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

J. X. Madarász, Interpolation and amalgamation; pushing the limits. I, Studia Logica, vol. 61(3) (1998), pp. 311–345, DOI: https://doi.org/10.1023/A:1005064504044
Google Scholar DOI: https://doi.org/10.1023/A:1005064504044

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: https://doi.org/10.1007/978-0-387-69245-6_4
Google Scholar DOI: https://doi.org/10.1007/978-0-387-69245-6_4

L. Maksimova, Amalgamation and interpolation in normal modal logic, Studia Logica, vol. 50(3-4) (1991), pp. 457–471, DOI: https://doi.org/10.1007/BF00370682 algebraic logic.
Google Scholar DOI: https://doi.org/10.1007/BF00370682

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.
Google Scholar DOI: https://doi.org/10.1007/BF01673502

P. Mancosu, Introduction: Interpolations—essays in honor of William Craig, Synthese, vol. 164(3) (2008), pp. 313–319, DOI: https://doi.org/10.1007/s11229-008-9350-6
Google Scholar DOI: https://doi.org/10.1007/s11229-008-9350-6

G. Metcalfe, F. Montagna, C. Tsinakis, Amalgamation and interpolation in ordered algebras, Journal of Algebra, vol. 402 (2014), pp. 21–82, DOI: https://doi.org/10.1016/j.jalgebra.2013.11.019
Google Scholar DOI: https://doi.org/10.1016/j.jalgebra.2013.11.019

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
Google Scholar DOI: https://doi.org/10.1007/s11225-011-9352-0

D. Nyiri, The Robinson property and amalgamations of higher arities, Mathematical Logic Quarterly, vol. 62(4–5) (2016), pp. 427–433, DOI: https://doi.org/10.1002/malq.201500027
Google Scholar DOI: https://doi.org/10.1002/malq.201500027

D. Pigozzi, Amalgamation, congruence-extension, and interpolation properties in algebras, Algebra Universalis, vol. 1 (1971/72), pp. 269–349, DOI: https://doi.org/10.1007/BF02944991
Google Scholar DOI: https://doi.org/10.1007/BF02944991

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.
Google Scholar

G. Priest, An Introduction to Non-Classical Logic: From If to Is, Cambridge University Press (2008).
Google Scholar DOI: https://doi.org/10.1017/CBO9780511801174

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

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: https://doi.org/10.2178/jsl/1140641164
Google Scholar DOI: https://doi.org/10.2178/jsl/1140641164

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).
Google Scholar

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: https://doi.org/10.1007/BF00370557
Google Scholar DOI: https://doi.org/10.1007/BF00370557

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: https://doi.org/10.1007/BFb0043086
Google Scholar DOI: https://doi.org/10.1007/BFb0043086

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.
Google Scholar

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: https://doi.org/10.1016/j.apal.2017.05.001
Google Scholar DOI: https://doi.org/10.1016/j.apal.2017.05.001

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