Many-valued coalgebraic logic over semi-primal varieties. (English) Zbl 07906368
Summary: We study many-valued coalgebraic logics with semi-primal algebras of truth-degrees. We provide a systematic way to lift endofunctors defined on the variety of Boolean algebras to endofunctors on the variety generated by a semi-primal algebra. We show that this can be extended to a technique to lift classical coalgebraic logics to many-valued ones, and that (one-step) completeness and expressivity are preserved under this lifting. For specific classes of endofunctors, we also describe how to obtain an axiomatization of the lifted many-valued logic directly from an axiomatization of the original classical one. In particular, we apply all of these techniques to classical modal logic.
Keywords:
coalgebraic logic; many-valued logic; modal logic; semi-primal algebras; one-step completeness; expressivityReferences:
| [1] | J. Adámek, J. Rosický, E. M. Vitale, and F. W. Lawvere. Algebraic Theories: A Categorical Introduction to General Algebra, volume 184 of Cambridge Tracts in Mathematics. Cambridge University Press, 2010. |
| [2] | M. Baaz. Infinite-valued Gödel logics with 0-1-projections and relativizations. In P. Hájek, editor, Proc. Gödel’96, Logic Foundations of Mathematics, Computer Science and Physics -Kurt Gödel’s Legacy, Lecture Notes in Logic 6, pages 23-33, Brno, 1996. Springer. · Zbl 0862.03015 |
| [3] | G. Bezhanishvili, N. Bezhanishvili, and J. De Groot. A coalgebraic approach to dualities for neighborhood frames. Logical Methods in Computer Science, 18(3):4:1-4:39, 2022. doi:10.46298/ lmcs-18(3:4)2022. · Zbl 07577568 · doi:10.46298/lmcs-18(3:4)2022 |
| [4] | P. Baldan, F. Bonchi, H. Kerstan, and B. König. Coalgebraic behavioral metrics. Logical Methods in Computer Science, 14(3):1-61, 2018. doi:10.23638/LMCS-14(3:20)2018. · Zbl 1515.68199 · doi:10.23638/LMCS-14(3:20)2018 |
| [5] | M. Bílková and M. Dostál. Expressivity of many-valued modal logics, coalgebraically. In J. Väänänen, Å. Hirvonen, and R. de Queiroz, editors, Logic, Language, Information, and Com-putation, pages 109-124. Springer Berlin Heidelberg, 2016. doi:10.1007/978-3-662-52921-8_8. · Zbl 1478.03033 · doi:10.1007/978-3-662-52921-8_8 |
| [6] | P. Blackburn, M. de Rijke, and Y. Venema. Modal Logic, volume 53 of Cambridge Tracts in The-oretical Computer Science. Cambridge University Press, 2001. doi:10.1017/CBO9781107050884. · doi:10.1017/CBO9781107050884 |
| [7] | F. Bou, F. Esteva, L. Godo, and R. O. Rodríguez. On the minimum many-valued modal logic over a finite residuated lattice. Journal of Logic and Computation, 21(5):739-790, 2011. doi:10.1093/logcom/exp062. · Zbl 1252.03040 · doi:10.1093/logcom/exp062 |
| [8] | V. Boicescu, A. Filipoiu, G. Georgescu, and S. Rudeanu. Lukasiewicz-Moisil algebras, volume 49 of Annals of Discrete Mathematics. North-Holland, Amsterdam, 1991. · Zbl 0726.06007 |
| [9] | M. M. Bonsangue and A. Kurz. Duality for logics of transition systems. In V. Sassone, editor, Foundations of Software Science and Computational Structures, pages 455-469. Springer Berlin Heidelberg, 2005. doi:10.1007/978-3-540-31982-5_29. · Zbl 1119.03021 · doi:10.1007/978-3-540-31982-5_29 |
| [10] | M. M. Bonsangue and A. Kurz. Presenting functors by operations and equations. In L. Aceto and A. Ingólfsdóttir, editors, Foundations of Software Science and Computation Structures, pages 172-186. Springer Berlin Heidelberg, 2006. doi:10.1007/11690634_12. · Zbl 1180.68182 · doi:10.1007/11690634_12 |
| [11] | M. Bílková, A. Kurz, D. Petrişan, and J. Velebil. Relation lifting, with an application to the many-valued cover modality. Logical Methods in Computer Science, 9(4):739-790, 2013. doi:10.2168/LMCS-9(4:8)2013. · Zbl 1287.18008 · doi:10.2168/LMCS-9(4:8)2013 |
| [12] | S. Burris and H. P. Sankappanavar. A Course in Universal Algebra, volume 78 of Graduate Texts in Mathematics. Springer New York, 1981. · Zbl 0478.08001 |
| [13] | S. Burris. Boolean powers. Algebra Universalis, 5:341-360, 1975. doi:10.1007/BF02485268. · Zbl 0328.08003 · doi:10.1007/BF02485268 |
| [14] | S. Burris. Discriminator varieties and symbolic computation. Journal of Symbolic Computation, 13:175-207, 1992. doi:10.1016/S0747-7171(08)80089-2. · Zbl 0803.08002 · doi:10.1016/S0747-7171(08)80089-2 |
| [15] | D. M. Clark and B. A. Davey. Natural Dualities for the Working Algebraist, volume 57 of Cambridge studies in advanced mathematics. Cambridge University Press, 1998. · Zbl 0910.08001 |
| [16] | R. L. O. Cignoli, I. M. L. D’Ottaviano, and D. Mundici. Algebraic Foundations of Many-Valued Rea-soning, volume 7 of Trends in Logic. Springer Dordrecht, 2000. doi:10.1007/978-94-015-9480-6. · Zbl 0937.06009 · doi:10.1007/978-94-015-9480-6 |
| [17] | R. Cignoli. Proper n-valued lukasiewicz algebras as s-algebras of lukasiewicz n-valued propositional calculi. Studia Logica, 41(1):3-16, 1982. doi:10.1007/BF00373490. · Zbl 0509.03012 · doi:10.1007/BF00373490 |
| [18] | C. Cîrstea and D. Pattinson. Modular construction of modal logics. In P. Gardner and N. Yoshida, editors, CONCUR 2004 -Concurrency Theory, pages 258-275. Springer Berlin Heidelberg, 2004. doi:10.1007/978-3-540-28644-8_17. · Zbl 1099.03018 · doi:10.1007/978-3-540-28644-8_17 |
| [19] | X. Caicedo and R. Rodriguez. Standard Gödel modal logics. Studia Logica, 94:189-214, 2010. doi:10.1007/s11225-010-9230-1. · Zbl 1266.03030 · doi:10.1007/s11225-010-9230-1 |
| [20] | D. Diaconescu and G. Georgescu. Tense operators on MV-algebras and Lukasiewicz-Moisil algebras. Fundamenta Informaticae, 81(4):379-408, 2007. · Zbl 1136.03045 |
| [21] | K. Dosen. Duality between modal algebras and neighbourhood frames. Studia Logica, 48(2):219-234, 1989. doi:10.1007/BF02770513. · Zbl 0685.03013 · doi:10.1007/BF02770513 |
| [22] | B. A. Davey, V. Schumann, and H. Werner. From the subalgebras of the square to the discriminator. Algebra Universalis, 28:500-519, 1991. doi:10.1007/BF01195860. · Zbl 0745.08002 · doi:10.1007/BF01195860 |
| [23] | M. C. Fitting. Many-valued modal logics. Fundamenta Informaticae, 15(3-4):235-254, 1991. doi:10.3233/FI-1991-153-404. · Zbl 0745.03018 · doi:10.3233/FI-1991-153-404 |
| [24] | A. L. Foster. Generalized “Boolean” theory of universal algebras. Part I. Mathematische Zeitschrift, 58:306-336, 1953. doi:10.1007/BF01174150. · Zbl 0051.02201 · doi:10.1007/BF01174150 |
| [25] | A. L. Foster. Semi-primal algebras; Characterization and normal-decomposition. Mathematische Zeitschrift, 99:105-116, 1967. doi:10.1007/BF01123742. · Zbl 0158.01801 · doi:10.1007/BF01123742 |
| [26] | A. L. Foster. Generalized “Boolean” theory of universal algebras. Part II. Identities and subdirect sums of functionally complete algebras. Mathematische Zeitschrift, 59:191-199, 1953/54. doi: 10.1007/BF01180250. · Zbl 0051.26202 · doi:10.1007/BF01180250 |
| [27] | A. L. Foster and A. F. Pixley. Semi-categorical algebras. I. Semi-primal algebras. Mathematische Zeitschrift, 83:147-169, 1964. doi:10.1007/BF01111252. · Zbl 0117.26001 · doi:10.1007/BF01111252 |
| [28] | A. L. Foster and A. F. Pixley. Semi-categorical algebras. II. Mathematische Zeitschrift, 85:169-184, 1964. doi:10.1007/BF01110374. · Zbl 0121.26505 · doi:10.1007/BF01110374 |
| [29] | H. H. Hansen, C. Kupke, and E. Pacuit. Neighbourhood structures: Bisimilarity and basic model theory. Logical Methods in Computer Science, 5(2):1-38, 2009. doi:10.2168/LMCS-5(2:2)2009. · Zbl 1172.03011 · doi:10.2168/LMCS-5(2:2)2009 |
| [30] | G. Hansoul and B. Teheux. Extending Lukasiewicz logics with a modality: Algebraic approach to relational semantics. Studia Logica, 101:505-545, 2013. doi:10.1007/s11225-012-9396-9. · Zbl 1272.03100 · doi:10.1007/s11225-012-9396-9 |
| [31] | T.-K. Hu. Stone duality for primal algebra theory. Mathematische Zeitschrift, 110:180-198, 1969. doi:10.1007/BF01110209. · Zbl 0175.28903 · doi:10.1007/BF01110209 |
| [32] | T.-K. Hu. On the topological duality for primal algebra theory. Algebra Universalis, 1:152-154, 1971. doi:10.1007/BF02944971. · Zbl 0236.08005 · doi:10.1007/BF02944971 |
| [33] | P. T. Johnstone. Stone spaces, volume 3 of Cambridge studies in advanced mathematics. Cambridge University Press, 1982. · Zbl 0499.54001 |
| [34] | B. Jacobs and A. Sokolova. Exemplaric expressivity of modal logics. Journal of Logic and Computation, 20(5):1041-1068, 2009. doi:10.1093/logcom/exn093. · Zbl 1234.03009 · doi:10.1093/logcom/exn093 |
| [35] | C. Kupke, A. Kurz, and D. Pattinson. Algebraic semantics for coalgebraic logics. Electronic Notes in Theoretical Computer Science, 106:219-241, 2004. doi:10.1016/j.entcs.2004.02.037. · Zbl 1271.03031 · doi:10.1016/j.entcs.2004.02.037 |
| [36] | C. Kupke, A. Kurz, and Y. Venema. Stone coalgebras. Theoretical Computer Science, 327(1):109-134, 2003. doi:10.1016/S1571-0661(04)80638-8. · Zbl 1075.68053 · doi:10.1016/S1571-0661(04)80638-8 |
| [37] | B. Klin. Coalgebraic modal logic beyond sets. Electronic Notes in Theoretical Computer Science, 173:177-201, 2007. Proceedings of the 23rd Conference on the Mathematical Foundations of Programming Semantics (MFPS XXIII). doi:10.1016/j.entcs.2007.02.034. · Zbl 1316.03017 · doi:10.1016/j.entcs.2007.02.034 |
| [38] | T. Kowalski. Semisimplicity, edpc and discriminator varieties of residuated lattices. Studia Logica, 77:255-265, 2004. doi:10.1023/B:STUD.0000037129.58589.0c. · Zbl 1062.06006 · doi:10.1023/B:STUD.0000037129.58589.0c |
| [39] | A. Kurz and D. Petrişan. Presenting functors on many-sorted varieties and applications. Informa-tion and Computation, 208(12):1421-1446, 2010. doi:10.1016/j.ic.2009.11.007. · Zbl 1252.18009 · doi:10.1016/j.ic.2009.11.007 |
| [40] | C. Kupke and D. Pattinson. Coalgebraic semantics of modal logics: An overview. Theoretical Computer Science, 412(38):5070-5094, 2011. doi:10.1016/j.tcs.2011.04.023. · Zbl 1360.03068 · doi:10.1016/j.tcs.2011.04.023 |
| [41] | A. Kurz and W. Poiger. Many-Valued Coalgebraic Logic: From Boolean Algebras to Primal Varieties. In P. Baldan and V. de Paiva, editors, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023), volume 270 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:17, Dagstuhl, Germany, 2023. Schloss Dagstuhl -Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CALCO.2023.17. · doi:10.4230/LIPIcs.CALCO.2023.17 |
| [42] | A. Kurz, W. Poiger, and B. Teheux. New perspectives on semi-primal varieties. Journal of Pure and Applied Algebra, 228(4):107525, 2024. doi:10.1016/j.jpaa.2023.107525. · Zbl 07784733 · doi:10.1016/j.jpaa.2023.107525 |
| [43] | A. Kurz and J. Rosický. Strongly complete logics for coalgebras. Logical Methods in Computer Science, 8(3):1-32, 2012. doi:10.2168/LMCS-8(3:14)2012. · Zbl 1263.03063 · doi:10.2168/LMCS-8(3:14)2012 |
| [44] | T. Kroupa and B. Teheux. Modal extensions of Lukasiewicz logic for modelling coalitional power. Journal of Logic and Computation, 27(1):129-154, 2017. doi:10.1093/logcom/exv081. · Zbl 1361.68235 · doi:10.1093/logcom/exv081 |
| [45] | K. Keimel and H. Werner. Stone duality for varieties generated by quasi-primal algebras. Memoirs of the American Mathematical Society, 148:59-85, 1974. · Zbl 0283.08001 |
| [46] | C.-Y. Lin and C.-J. Liau. Many-valued coalgebraic modal logic: One-step completeness and finite model property. Fuzzy Sets and Systems, 467:108564, 2023. doi:10.1016/j.fss.2023.108564. · Zbl 1543.03060 · doi:10.1016/j.fss.2023.108564 |
| [47] | Y. Maruyama. Algebraic study of lattice-valued logic and lattice-valued modal logic. In R. Ra-manujam and S. Sarukkai, editors, Logic and Its Applications. ICLA, pages 170-184. Springer Berlin Heidelberg, 2009. doi:10.1007/978-3-540-92701-3_12. · Zbl 1209.03018 · doi:10.1007/978-3-540-92701-3_12 |
| [48] | Y. Maruyama. Natural duality, modality, and coalgebra. Journal of Pure and Applied Algebra, 216(3):565-580, 2012. doi:10.1016/j.jpaa.2011.07.002. · Zbl 1263.08002 · doi:10.1016/j.jpaa.2011.07.002 |
| [49] | S. Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathe-matics. Springer New York, second edition, 1997. doi:10.1007/978-1-4757-4721-8. · doi:10.1007/978-1-4757-4721-8 |
| [50] | M. Marti and G. Metcalfe. Expressivity in chain-based modal logics. Archive for Mathematical Logic, 57:361-380, 2018. doi:10.1007/s00153-017-0573-4. · Zbl 1522.03056 · doi:10.1007/s00153-017-0573-4 |
| [51] | L. S. Moss. Coalgebraic logic. Annals of Pure and Applied Logic, 96(1):277-317, 1999. doi: 10.1016/S0168-0072(98)00042-6. · Zbl 0969.03026 · doi:10.1016/S0168-0072(98)00042-6 |
| [52] | P. Niederkorn. Natural dualities for varieties of MV-algebras, I. Journal of Mathematical Analysis and Applications, 255(1):58-73, 2001. doi:10.1006/jmaa.2000.7153. · Zbl 0974.06006 · doi:10.1006/jmaa.2000.7153 |
| [53] | E. Pacuit. Neighborhood Semantics for Modal Logic. Short Textbooks in Logic. Springer Cham, 2017. doi:10.1007/978-3-319-67149-9. · Zbl 1390.03001 · doi:10.1007/978-3-319-67149-9 |
| [54] | A. Palmigiano. A coalgebraic view on positive modal logic. Theoretical Computer Science, 327(1):175-195, 2004. Selected Papers of CMCS ’03. doi:10.1016/j.tcs.2004.07.026. · Zbl 1068.03017 · doi:10.1016/j.tcs.2004.07.026 |
| [55] | D. Pattinson. Coalgebraic modal logic: Soundness, completeness and decidability of local con-sequence. Theoretical Computer Science, 309(1):177-193, 2003. doi:10.1016/S0304-3975(03) 00201-9. · Zbl 1052.03009 · doi:10.1016/S0304-3975(03)00201-9 |
| [56] | D. Pattinson. Expressive logics for coalgebras via terminal sequence induction. Notre Dame Journal of Formal Logic, 45(1):19-33, 2004. doi:10.1305/ndjfl/1094155277. · Zbl 1088.03031 · doi:10.1305/ndjfl/1094155277 |
| [57] | A. F. Pixley. The ternary discriminator function in universal algebra. Mathematische Annalen, 191:167-180, 1971. doi:10.1007/BF01578706. · Zbl 0203.31201 · doi:10.1007/BF01578706 |
| [58] | G. Priest. Many-valued modal logics: A simple approach. The Review of Symbolic Logic, 1(2):190-203, 2008. doi:10.1017/S1755020308080179. · Zbl 1206.03022 · doi:10.1017/S1755020308080179 |
| [59] | R. W. Quackenbush. Primality: The influence of Boolean algebras in universal algebra. (Appendix 5). In Grätzer, G. Universal Algebra. Second Edition, pages 401-416. Springer New York, 1979. |
| [60] | U. Rivieccio, A. Jung, and R. Jansana. Four-valued modal logic: Kripke semantics and duality. Journal of Logic and Computation, 27(1):155-199, 2017. doi:10.1093/logcom/exv038. · Zbl 1444.03073 · doi:10.1093/logcom/exv038 |
| [61] | J. J. M. M. Rutten. Universal coalgebra: A theory of systems. Theoretical Computer Science, 249(1):3-80, 2000. doi:10.1016/S0304-3975(00)00056-6. · Zbl 0951.68038 · doi:10.1016/S0304-3975(00)00056-6 |
| [62] | L. Schröder. Expressivity of coalgebraic modal logic: The limits and beyond. Theoretical Computer Science, 390(2):230-247, 2008. doi:10.1016/j.tcs.2007.09.023. · Zbl 1132.03008 · doi:10.1016/j.tcs.2007.09.023 |
| [63] | A. Schiendorfer, A. Knapp, G. Anders, and W. Reif. MiniBrass: Soft constraints for MiniZinc. Constraints, 23(4):403-450, 2018. doi:10.1007/s10601-018-9289-2. · Zbl 1430.90525 · doi:10.1007/s10601-018-9289-2 |
| [64] | B. Teheux. Propositional dynamic logic for searching games with errors. Journal of Applied Logic, 12(4):377-394, 2014. doi:10.1016/j.jal.2014.04.001. · Zbl 1395.03011 · doi:10.1016/j.jal.2014.04.001 |
| [65] | V. Trnková. Some properties of set functors. Commentationes Mathematicae Universitatis Caroli-nae, 10(2):323-352, 1969. · Zbl 0183.30401 |
| [66] | A. Vidal, F. Esteva, and L. Godo. On modal extensions of product fuzzy logic. Journal of Logic and Computation, 27(1):299-336, 2017. doi:10.1093/logcom/exv046. · Zbl 1390.03025 · doi:10.1093/logcom/exv046 |
| [67] | A. Vidal, F. Esteva, and L. Godo. Axiomatizing logics of fuzzy preferences using graded modalities. Fuzzy Sets and Systems, 401:163-188, 2020. doi:10.1016/j.fss.2020.01.002. · Zbl 1464.03028 · doi:10.1016/j.fss.2020.01.002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
