A coalgebraic approach to dualities for neighborhood frames. (English) Zbl 07577568
Summary: We develop a uniform coalgebraic approach to Jónsson-Tarski and Thomason type dualities for various classes of neighborhood frames and neighborhood algebras. In the first part of the paper we construct an endofunctor on the category of complete and atomic Boolean algebras that is dual to the double powerset functor on Set. This allows us to show that Thomason duality for neighborhood frames can be viewed as an algebra-coalgebra duality. We generalize this approach to any class of algebras for an endofunctor presented by one-step axioms in the language of infinitary modal logic. As a consequence, we obtain a uniform approach to dualities for various classes of neighborhood frames, including monotone neighborhood frames, pretopological spaces, and topological spaces.
In the second part of the paper we develop a coalgebraic approach to Jónsson-Tarski duality for neighborhood algebras and descriptive neighborhood frames. We introduce an analogue of the Vietoris endofunctor on the category of Stone spaces and show that descriptive neighborhood frames are isomorphic to coalgebras for this endofunctor. This allows us to obtain a coalgebraic proof of the duality between descriptive neighborhood frames and neighborhood algebras. Using one-step axioms in the language of finitary modal logic, we restrict this duality to other classes of neighborhood algebras studied in the literature, including monotone modal algebras and contingency algebras.
We conclude the paper by connecting the two types of dualities via canonical extensions, and discuss when these extensions are functorial.
In the second part of the paper we develop a coalgebraic approach to Jónsson-Tarski duality for neighborhood algebras and descriptive neighborhood frames. We introduce an analogue of the Vietoris endofunctor on the category of Stone spaces and show that descriptive neighborhood frames are isomorphic to coalgebras for this endofunctor. This allows us to obtain a coalgebraic proof of the duality between descriptive neighborhood frames and neighborhood algebras. Using one-step axioms in the language of finitary modal logic, we restrict this duality to other classes of neighborhood algebras studied in the literature, including monotone modal algebras and contingency algebras.
We conclude the paper by connecting the two types of dualities via canonical extensions, and discuss when these extensions are functorial.
References:
| [1] | G. Bezhanishvili, N. Bezhanishvili, and J. de Groot Vol. 18:3 |
| [2] | G. Bezhanishvili, N. Bezhanishvili, and J. de Groot Vol. 18:3 |
| [3] | G. Bezhanishvili, N. Bezhanishvili, and J. de Groot Vol. 18:3 |
| [4] | S. Abramsky. A Cook’s tour of the finitary non-well-founded sets. Invited Lecture at BCTCS 1988. arxiv:1111.7148, 1988. |
| [5] | S. Abramsky. Domain theory in logical form. Annals of Pure and Applied Logic, 51(1-2):1-77, 1991. doi:10.1016/0168-0072(91)90065-t. · Zbl 0737.03006 · doi:10.1016/0168-0072(91)90065-t |
| [6] | J. Adámek, H. Herrlich, and G. E. Strecker. Abstract and Concrete Categories. Wiley, New York, 1990. URL: http://katmat.math.uni-bremen.de/acc/. · Zbl 0695.18001 |
| [7] | A. Baltag. A Structural Theory of Sets. PhD thesis, Indiana University, 1998. |
| [8] | A. Baltag. STS: A structural theory of sets. In M. Zakharyaschev, K. Segerberg, M. de Rijke, and H. Wansing, editors, Proc. AIML 1998, pages 1-34. CSLI Publications, 2000. · Zbl 0993.03065 |
| [9] | + 14] F. Bonchi, M. Bonsangue, H. H. Hansen, P. Panangaden, J. Rutten, and A. Silva. Algebra-coalgebra duality in Brzozowski’s minimization algorithm. ACM Transactions on Computational Logic, 15:3:1-3:29, 2014. doi:10.1145/2490818. · Zbl 1288.68174 · doi:10.1145/2490818 |
| [10] | + 20] N. Bezhanishvili, M. Bonsangue, D. Hansen, H. H.and Kozen, C. Kupke, P. Panangaden, and A. Silva. Minimisation in logical form. To appear in Outstanding Contributions to Logic volume dedicated to Samson Abramsky. arxiv:2205.11551, 2020. |
| [11] | G. Bezhanishvili, N. Bezhanishvili, and R. Iemhoff. Stable canonical rules. Journal of Symbolic Logic, 81(1):284-315, 2016. doi:10.1017/jsl.2015.54. · Zbl 1345.03034 · doi:10.1017/jsl.2015.54 |
| [12] | G. Bezhanishvili, N. Bezhanishvili, and J. Ilin. Stable modal logics. Review of Symbolic Logic, 11(3):436-469, 2018. doi:10.1017/S1755020317000375. · Zbl 1522.03048 · doi:10.1017/S1755020317000375 |
| [13] | G. Bezhanishvili, L. Carai, and P. J. Morandi. Duality for powerset coalgebras. Logical Methods in Computer Science, 18, 2022. doi:10.46298/lmcs-18(1:27)2022. · Zbl 07471716 · doi:10.46298/lmcs-18(1:27)2022 |
| [14] | J. L. Bell. Infinitary logic. In E. N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, winter 2016 edition, 2016. |
| [15] | J. Barwise and S. Feferman. Model-Theoretic Logics. Springer-Verlag, Berlin, Heidelberg, 1985. doi:10.1017/9781316717158. · doi:10.1017/9781316717158 |
| [16] | G. Bezhanishvili and J. Harding. Raney algebras and duality for T0-spaces. Applied Categorical Structures, 28(6):963-973, 2020. doi:10.1007/s10485-020-09606-w. · Zbl 1464.54016 · doi:10.1007/s10485-020-09606-w |
| [17] | N. Bezhanishvili, C. Kupke, and P. Panangaden. Minimization via duality. In Logic, Language, Information and Computation, WoLLIC 2012, Proceedings, pages 191-205, 2012. · Zbl 1361.68157 |
| [18] | W. Blok. Varieties of Interior Algebras. PhD thesis, University of Amsterdam, 1976. URL: https://eprints.illc.uva.nl/id/eprint/1833/2/HDS-01-Wim_Blok.text.pdf. |
| [19] | G. Bezhanishvili, R. Mines, and P. Morandi. Topo-canonical completions of closure algebras and Heyting algebras. Algebra Universalis, 58(1):1-34, 2008. doi:10.1007/s00012-007-2032-2. · Zbl 1135.06009 · doi:10.1007/s00012-007-2032-2 |
| [20] | G. Bezhanishvili, P. J. Morandi, and B. Olberding. An extension of de Vries duality to completely regular spaces and compactifications. Topology and Its Applications, 257:85-105, 2019. doi: 10.1016/j.topol.2019.02.007. · Zbl 1412.54034 · doi:10.1016/j.topol.2019.02.007 |
| [21] | P. Blackburn, M. de Rijke, and Y. Venema. Modal Logic. Cambridge University Press, Cambridge, 2001. doi:10.1017/CBO9781107050884. · Zbl 0988.03006 · doi:10.1017/CBO9781107050884 |
| [22] | Z. Bakhtiari, H. van Ditmarsch, and H. H. Hansen. Neighbourhood contingency bisimulation. In S. Ghosh and S Prasad, editors, Proc. ICLA 2017, pages 48-63, Berlin, Heidelberg, 2017. Springer. doi:10.1007/978-3-662-54069-5_5. · Zbl 1485.03063 · doi:10.1007/978-3-662-54069-5_5 |
| [23] | C. C. Chang. Some remarks on the model theory of infinitary languages. In J. Barwise, editor, The Syntax and Semantics of Infinitary Languages, pages 36-63, Berlin, Heidelberg, 1968. Springer-Verlag. · Zbl 0175.26802 |
| [24] | B. F. Chellas. Modal Logic: An Introduction. Cambridge University Press, Cambridge, 1980. · Zbl 0431.03009 |
| [25] | Á. Császár. Generalized topology, generalized continuity. Acta Mathematica Hungarica, 96(4):351-357, 2002. · Zbl 1006.54003 |
| [26] | K Došen. Duality between modal algebras and neighbourhood frames. Studia Logica, 48:219-234, 1989. doi:10.1007/BF02770513. · Zbl 0685.03013 · doi:10.1007/BF02770513 |
| [27] | L. L. Esakia. Topological Kripke models. Soviet Mathematics Doklady, 15:147-151, 1974. · Zbl 0296.02030 |
| [28] | J. Fan. Neighborhood contingency logic: A new perspective. Studies in Logic, 11:37-55, 2018. arxiv:1802.02291. |
| [29] | J. Fan and H. van Ditmarsch. Neighborhood contingency logic. In M. Banerjee and S. N. Krishna, editors, Proc. ICLA 2015, pages 88-99, Berlin, Heidelberg, 2015. Springer-Verlag. doi:10.1007/ 978-3-662-45824-2_6. · Zbl 1304.03049 · doi:10.1007/978-3-662-45824-2_6 |
| [30] | + 17] R. Furber, D. Kozen, K. G. Larsen, R. Mardare, and P. Panangaden. Unrestricted Stone duality for Markov processes. In Proc. LICS 2017, pages 1-9, 2017. doi:10.1109/LICS.2017.8005152. · doi:10.1109/LICS.2017.8005152 |
| [31] | H. Gaifman. Infinite Boolean polynomials. I. Fundamenta Mathematicae, 54:229-250, 1964. doi:10.4064/fm-54-3-229-250. · Zbl 0126.26404 · doi:10.4064/fm-54-3-229-250 |
| [32] | M. Gehrke. Duality in computer science. In Proc. LICS 2016, pages 1-15, 2016. doi:10.1145/ 2933575.2934575. · Zbl 1392.68268 · doi:10.1145/2933575.2934575 |
| [33] | M. Gehrke. Stone duality, topological algebra, and recognition. Journal of Pure and Applied Algebra, 220(7):2711-2747, 2016. doi:j.jpaa.2015.12.007. · Zbl 1339.06012 |
| [34] | M. Gehrke, S. Grigorieff, and J-É. Pin. Duality and equational theory of regular languages. In Proc. ICAPL 2008, pages 246-257. Springer, 2008. · Zbl 1165.68049 |
| [35] | M. Gehrke and J. Harding. Bounded lattice expansions. Journal of Algebra, 238:345-371, 2001. doi:10.1006/jabr.2000.8622. · Zbl 0988.06003 · doi:10.1006/jabr.2000.8622 |
| [36] | S. Ghilardi. An algebraic theory of normal forms. Annals of Pure and Applied Logic, 71(3):189-245, 1995. doi:10.1016/0168-0072(93)E0084-2. · Zbl 0815.03010 · doi:10.1016/0168-0072(93)E0084-2 |
| [37] | + 80] G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, and M. W. Mislove. A compendium of continuous lattices. Springer, 1980. doi:10.1007/978-3-642-67678-9. · Zbl 0452.06001 · doi:10.1007/978-3-642-67678-9 |
| [38] | M. Gehrke and B. Jónsson. Bounded distributive lattices with operators. Mathematica Japonica, 40(2):207-215, 1994. · Zbl 0855.06009 |
| [39] | M. Gehrke and B. Jónsson. Bounded distributive lattice expansions. Mathematica Scandinavica, 94(1):13-45, 2004. · Zbl 1077.06008 |
| [40] | M. Gehrke, R. Jansana, and A. Palmigiano. ∆1-completions of a poset. Order, 30(1):39-64, 2013. doi:10.1007/s11083-011-9226-0. · Zbl 1317.06002 · doi:10.1007/s11083-011-9226-0 |
| [41] | R. I. Goldblatt. Metamathematics of modal logic I. Reports on Mathematical Logic, 6:41-78, 1976. 4:38 |
| [42] | G. Bezhanishvili, N. Bezhanishvili, and J. de Groot Vol. 18:3 |
| [43] | M. Gehrke and H. A. Priestley. Canonical extensions and completions of posets and lattices. Reports on Mathematical Logic, 43:133-152, 2008. · Zbl 1147.06005 |
| [44] | P. R. Halmos. The basic concepts of algebraic logic. The American Mathematical Monthly, 63:363-387, 1956. · Zbl 0070.24506 |
| [45] | A. W. Hales. On the non-existence of free complete Boolean algebras. Fundamenta Mathematicae, 54:45-66, 1964. doi:10.4064/fm-54-1-45-66. · Zbl 0119.26003 · doi:10.4064/fm-54-1-45-66 |
| [46] | H. H. Hansen. Monotonic modal logics. Master’s thesis, Institute for Logic, Language and Computation, University of Amsterdam, 2003. URL: https://eprints.illc.uva.nl/id/eprint/ 108/2/PP-2003-24.text.pdf. |
| [47] | H. H. Hansen and C. Kupke. A coalgebraic perspective on monotone modal logic. Electronic Notes in Theoretical Computer Science, 106:121-143, 2004. doi:https://doi.org/10.1016/j. entcs.2004.02.028. · Zbl 1271.03029 · doi:10.1016/j.entcs.2004.02.028 |
| [48] | B. Jacobs. Introduction to Coalgebra: Towards Mathematics of States and Observation. Cambridge University Press, Cambridge, 2016. doi:10.1017/CBO9781316823187. · Zbl 1364.68001 · doi:10.1017/CBO9781316823187 |
| [49] | P. T. Johnstone. Stone Spaces. Cambridge University Press, 1982. · Zbl 0499.54001 |
| [50] | B. Jónsson and A. Tarski. Boolean algebras with operators. Part I. American Journal of Mathe-matics, 73(4):891-939, 1951. doi:10.2307/2372123. · Zbl 0045.31505 · doi:10.2307/2372123 |
| [51] | C. Kupke, A. Kurz, and D. Pattinson. Ultrafilter extensions for coalgebras. In J. Luiz Fiadeiro, N. Harman, M. Roggenbach, and J. Rutten, editors, Proc. CALCO 2005, pages 263-277, Berlin, Heidelberg, 2005. Springer. doi:10.1007/11548133_17. · Zbl 1151.03357 · doi:10.1007/11548133_17 |
| [52] | C. Kupke, A. Kurz, and Y. Venema. Stone coalgebras. Theoretical Computer Science, 327(1):109-134, 2004. · Zbl 1075.68053 |
| [53] | D. Kozen, K. G. Larsen, R. Mardare, and P. Panangaden. Stone duality for Markov processes. In Proc. LICS 2013, pages 321-330, 2013. doi:10.1109/LICS.2013.38. · Zbl 1433.06006 · doi:10.1109/LICS.2013.38 |
| [54] | 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 |
| [55] | D. Lewis. Counterfactuals. Harvard University Press, 1973. |
| [56] | R. Montague. Universal grammar. Theoria, 36(3):373-398, 1970. · Zbl 0243.02002 |
| [57] | J. C. C. McKinsey and A. Tarski. The algebra of topology. Annals of Mathematics, 45:141-191, 1944. doi:10.2307/1969080. · Zbl 0060.06206 · doi:10.2307/1969080 |
| [58] | 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 |
| [59] | P. Panangaden. Duality in logic and computation. In Proc. LICS 2013, pages 4-11, 2013. doi: 10.1109/LICS.2013.64. · Zbl 1433.06005 · doi:10.1109/LICS.2013.64 |
| [60] | G. Plotkin. Domains, 1983. The “Pisa Notes”. URL: https://homepages.inf.ed.ac.uk/gdp/ publications/Domains_a4.ps. |
| [61] | H. Rasiowa and R. Sikorski. The Mathematics of Metamathematics. Monografie Matematyczne, Tom 41. Państwowe Wydawnictwo Naukowe, Warsaw, 1963. |
| [62] | J. J. M. M. Rutten. Universal coalgebra: a theory of systems. Theoretical Computer Science, 249:3-80, 2000. doi:10.1016/S0304-3975(00)00056-6. · Zbl 0951.68038 · doi:10.1016/S0304-3975(00)00056-6 |
| [63] | D. Scott. Advice in modal logic. In K. Lambert, editor, Philosophical Problems in Logic, pages 143-173, Dordrecht, 1970. · Zbl 0295.02013 |
| [64] | M. Smyth. Power domains and predicate transformers: A topological view. In J. Diaz, editor, Proc. ICALP 1983, pages 662-675, Berlin, Heidelberg, 1983. doi:10.1007/BFb0036946. · Zbl 0533.68018 · doi:10.1007/BFb0036946 |
| [65] | B. Stadler, P. Stadler, M. Shpak, and G. Wagner. Recombination spaces, metrics, and pretopologies. Zeitschrift für physikalische Chemie, 216(2):217-234, 2002. |
| [66] | D. Scott and A. Tarski. The sentential calculus with infinitely long expressions. Colloquium Mathematicum, 16:165-170, 1958. doi:10.4064/cm-6-1-165-170. · Zbl 0119.25002 · doi:10.4064/cm-6-1-165-170 |
| [67] | M. H. Stone. The theory of representations for Boolean algebras. Transactions of the American Mathematical Society, 40:37-111, 1936. doi:10.2307/1989664. · Zbl 0014.34002 · doi:10.2307/1989664 |
| [68] | M. H. Stone. Topological representations of distributive lattices and Brouwerian logics.Časopis pro pěstování matematiky a fysiky, 67:1-25, 1938. · JFM 63.0830.01 |
| [69] | G. Sambin and V. Vaccaro. A new proof of Sahlqvist’s theorem on modal definability and completeness. Journal of Symbolic Logic, 54(3):992-999, 1989. doi:10.2307/2274758. · Zbl 0682.03009 · doi:10.2307/2274758 |
| [70] | Y. Tanaka. Duality for κ-additive complete atomic modal algebras. Algebra universalis, 82(31), 2021. doi:10.1007/s00012-021-00724-7. · Zbl 1535.06018 · doi:10.1007/s00012-021-00724-7 |
| [71] | A. Tarski. Zur Grundleging der Bool’schen Algebra. I. Fundamenta Mathematicae, 25:177-198, 1935. doi:10.4064/fm-24-1-177-198. · JFM 61.0054.02 · doi:10.4064/fm-24-1-177-198 |
| [72] | A. Tarski. Remarks on predicate logic with infinitely long expressions. Colloquium Mathematicum, 16:171-176, 1958. doi:10.4064/cm-6-1-171-176. · Zbl 0119.25003 · doi:10.4064/cm-6-1-171-176 |
| [73] | P. Taylor. Subspaces in abstract Stone duality. Theory and Applications of Categories, 10(13):301-368, 2002. · Zbl 1008.18005 |
| [74] | S. K. Thomason. Categories of frames for modal logic. Journal of Symbolic Logic, 40(3), 1975. doi:10.2307/2272167. · Zbl 0317.02012 · doi:10.2307/2272167 |
| [75] | Y. Venema. Algebras and coalgebras. In P. Blackburn, J. F. A. K. van Benthem, and F. Wolter, editors, Handbook of Modal Logic: Volume 3, pages 331-426. Elsevier, 2007. doi:10.1016/ S1570-2464(07)80009-7. · doi:10.1016/S1570-2464(07)80009-7 |
| [76] | E.Čech, Z. Frolík, and M. Katětov. Topological Spaces. Interscience Publishers, A division of John Wiley & Sons, London, New York, Sydney, 1966. · Zbl 0141.39401 |
| [77] | S. Willard. General Topology. Addison-Wesley series in mathematics. Dover Publications, 2004. This work is licensed under the Creative Commons Attribution License. To view a copy of this license, visit https://creativecommons.org/licenses/by/4.0/ or send a letter to Creative Commons, 171 Second St, Suite 300, San Francisco, CA 94105, USA, or Eisenacher Strasse 2, 10777 Berlin, Germany |
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.
