Categorical Abstract Logic: Hidden Multi-Sorted Logics as Multi-Term π-Institutions

George Voutsadakis

doi:10.18778/0138-0680.45.2.04

Authors

George Voutsadakis Lake Superior State University, School of Mathematics and Computer Science

DOI:

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

Keywords:

Behavioral Equivalence, Hidden Logic, Multi-Sorted Logic, Multi-term π-Institutions, Interpretability, Deductive Equivalence

Abstract

Babenyshev and Martins proved that two hidden multi-sorted deductive systems are deductively equivalent if and only if there exists an isomorphism between their corresponding lattices of theories that commutes with substitutions. We show that the π-institutions corresponding to the hidden multi-sorted deductive systems studied by Babenyshev and Martins satisfy the multi-term condition of Gil-F´erez. This provides a proof of the result of Babenyshev and Martins by appealing to the general result of Gil-F´erez pertaining to arbitrary multi-term π-institutions. The approach places hidden multi-sorted deductive systems in a more general framework and bypasses the laborious reuse of well-known proof techniques from traditional abstract algebraic logic by using “off the shelf” tools.

References

[1] S. Babenyshev and M. A. Martins, Behavioral Equivalence of Hidden k-Logics: An Abstract Algebraic Approach, Journal of Applied Logic, Vol. 16 (2016), pp. 72–91.
Google Scholar

[2] M. Barr and C. Wells, Category Theory for Computing Science, Third Edition, Les Publications CRM, Montréal, 1999.
Google Scholar

[3] W. J. Blok and B. Jónsson, Equivalence of Consequence Operations, Studia Logica, Vol. 83, No. 1/3 (2006), pp. 91–110.
Google Scholar

[4] W. J. Blok and D. Pigozzi, Algebraizable Logics, Memoirs of the American Mathematical Society, Vol. 77, No. 396 (1989).
Google Scholar

[5] C. Caleiro, R. Gon calves and M. Martins, Behavioral Algebraization of Logics, Studia Logica, Vol. 91, No. 1 (2009), pp. 63–111.
Google Scholar

[6] J. M. Font and T. Moraschini, M-Sets and the Representation Problem, Studia Logica, Vol. 103, No. 1 (2015), pp. 21–51.
Google Scholar

[7] Galatos, N., and N. Galatos, J. Gil-Férez, Modules over Quantaloids: Applications to the Isomorphism Problem in Algebraic Logic and -institutions, Journal of Pure and Applied Algebra, Vol. 221, No. 1 (2017), pp. 1–24.
Google Scholar

[8] N. Galatos and C. Tsinakis, Equivalence of Closure Operators: an Order-Theoretic and Categorical Perspective, The Journal of Symbolic Logic, Vol. 74, No. 3 (2009), pp. 780–810.
Google Scholar

[9] J. Gil-Férez, Multi-term -Institutions and their Equivalence, Mathematical Logic Quarterly, Vol. 52, No. 5 (2006), pp. 505–526.
Google Scholar

[10] M. A. Martins, Behavioral Reasoning in Generalized Hidden Logics, Ph.D. Thesis, Faculdade de Ciências, University of Lisbon, 2004.
Google Scholar

[11] M. A. Martins and D. Pigozzi, Behavioural Reasoning for Conditional Equations, Mathematical Structures in Computer Science, Vol. 17 (2007), pp. 1075–1113.
Google Scholar

[12] D. Sannella and A. Tarlecki, Foundations of Algebraic Specification and Formal Software Development, EATCS Monographs in Theoretical Computer Science, Springer 2012.
Google Scholar

[13] G. Voutsadakis, Categorical Abstract Algebraic Logic: Equivalent Institutions, Studia Logica, Vol. 74 (2003), pp. 275–311.
Google Scholar

[14] G. Voutsadakis, Categorical Abstract Algebraic Logic: Behavioral -Institutions, Studia Logica, Vol. 102, No. 3 (2014), pp. 617–646.
Google Scholar