Abstract
Modal logic enjoys topological semantics that may be traced back to McKinsey and Tarski, and the classification of topological spaces via modal axioms is a lively area of research. In the past two decades, there has been interest in extending topological modal logic to the language of the \(\mu \)-calculus, but previously no class of topological spaces was known to be \(\mu \)-calculus definable that was not already modally definable. In this paper we show that the full \(\mu \)-calculus is indeed more expressive than standard modal logic, in the sense that there are classes of topological spaces (and weakly transitive Kripke frames) which are \(\mu \)-definable, but not modally definable. The classes we exhibit satisfy a modally definable property outside of their perfect core, and thus we dub them imperfect spaces. We show that the \(\mu \)-calculus is sound and complete for these classes. Our examples are minimal in the sense that they use a single instance of a greatest fixed point.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Recall that the derivative \(\textsf{d}_{}(A)\) of a set A consists of all limit points of A.
- 2.
Note that a stronger notion of expressivity is also considered in the literature: namely, \(\mathcal L'\) is at least as expressive as \(\mathcal L\) if for every \(\varphi \in \mathcal L \) there is a logically equivalent \(\varphi '\in \mathcal L'\). To avoid confusion we may call the latter local expressivity, and the notion we are concerned with axiomatic expressivity. With this terminology in mind, while it was known that \(\mu \)-calculus is locally more expressive than the basic modal language over topological spaces (see e.g. [10]), here we will show that it is also axiomatically more expressive.
- 3.
Later we will see that the same result with \(\mathfrak F_{n,w}^{\textsf{spine}},r_n\) and \(\mathfrak F_{n,w}^{\textsf{cycle}},r_n\) follows for free.
References
Afshari, B., Leigh, G.: Cut-free completeness for modal mu-calculus. In: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science LICS, pp. 1–12. IEEE Press (2017)
Aleksandroff, P.: Diskrete räume. Matematicheskii Sbornik 2, 501–518 (1937)
Baltag, A., Bezhanishvili, N., Fernández-Duque, D.: The topological mu-calculus: completeness and decidability. In: 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, 29 June–2 July 2021, pp. 1–13. IEEE (2021). https://doi.org/10.1109/LICS52264.2021.9470560
van Benthem, J., Bezhanishvili, G.: Modal logics of space. In: Aiello, M., Pratt-Hartmann, I., Van Benthem, J. (eds.) Handbook of Spatial Logics, pp. 217–298. Springer, Dordrecht (2007). https://doi.org/10.1007/978-1-4020-5587-4_5
Bezhanishvili, G., Ghilardi, S., Jibladze, M.: An algebraic approach to subframe logics. Modal case. Notre Dame J. Formal Logic 52(2), 187–202 (2011)
Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. Cambridge Tracts in Theoretical Computer Science, Cambridge University Press (2001)
Chagrov, A.V., Zakharyaschev, M.: Modal Logic, Oxford Logic Guides, vol. 35. Clarendon Press. Consecutive, Oxford (1997)
Esakia, L.: Intuitionistic logic and modality via topology. Ann. Pure Appl. Log. 127(1–3), 155–170 (2004). Provinces of logic determined
Esakia, L.: Weak transitivity-a restitution. Logical Invest. 8, 244–245 (2001)
Fernández-Duque, D.: On the modal definability of simulability by finite transitive models. Stud. Logica. 98(3), 347–373 (2011). https://doi.org/10.1007/s11225-011-9339-x
Fernández-Duque, D.: Tangled modal logic for spatial reasoning. In: Twenty-Second International Joint Conference on Artificial Intelligence (2011)
Fernández-Duque, D., Iliev, P.: Succinctness in subsystems of the spatial \(\mu \)-calculus. FLAP 5(4), 827–874 (2018). https://www.collegepublications.co.uk/downloads/ifcolog00024.pdf
Goldblatt, R., Hodkinson, I.: Spatial logic of tangled closure operators and modal mu-calculus. Ann. Pure Appl. Log. 168(5), 1032–1090 (2017)
Goldblatt, R., Hodkinson, I.: The finite model property for logics with the tangle modality. Stud. Logica. 106(1), 131–166 (2017). https://doi.org/10.1007/s11225-017-9732-1
Kozen, D.: Results on the propositional \(\mu \)-calculus. Theor. Comput. Sci. 27(3), 333–354 (1983)
Kudinov, A., Shehtman, V.: Derivational modal logics with the difference modality. In: Bezhanishvili, G. (ed.) Leo Esakia on Duality in Modal and Intuitionistic Logics. OCL, vol. 4, pp. 291–334. Springer, Dordrecht (2014). https://doi.org/10.1007/978-94-017-8860-1_11
McKinsey, J.C.C., Tarski, A.: The algebra of topology. Ann. Math. 141–191 (1944)
Santocanale, L., Venema, Y.: Completeness for flat modal fixpoint logics. Ann. Pure Appl. Log. 162(1), 55–82 (2010)
Santocanale, L.: Completions of \(\mu \)-algebras. Ann. Pure Appl. Log. 154(1), 27–50 (2008)
Shehtman, V.: “Everywhere” and “here”. J. Appl. Non Class. Logics 9(2-3), 369–379 (1999). https://doi.org/10.1080/11663081.1999.10510972
Walukiewicz, I.: Completeness of Kozen’s axiomatisation of the propositional \(\mu \)-calculus. Inf. Comput. 157(1-2), 142–182 (2000). https://doi.org/10.1006/inco.1999.2836
Acknowledgements
We are grateful to Nick Bezhanishvili for his involvement in this project as a co-supervisor. We are also indebted to a number of anonymous referees who provided us with helpful feedback on an earlier version of this paper. DFD was partially supported by the FWO-FWF Lead Agency Grant G030620N.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Fernández-Duque, D., Gougeon, Q. (2022). Fixed Point Logics and Definable Topological Properties. In: Ciabattoni, A., Pimentel, E., de Queiroz, R.J.G.B. (eds) Logic, Language, Information, and Computation. WoLLIC 2022. Lecture Notes in Computer Science, vol 13468. Springer, Cham. https://doi.org/10.1007/978-3-031-15298-6_3
Download citation
DOI: https://doi.org/10.1007/978-3-031-15298-6_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-15297-9
Online ISBN: 978-3-031-15298-6
eBook Packages: Computer ScienceComputer Science (R0)
