Abstract
The paper studies two-dimensional modal logics with additional connectives (so-called Segerberg squares) and can be regarded as a continuation of Shehtman (Russian Mathematical Surveys, 67(4):721–778, 2012). It gives a new simpler proof of the finite model property of minimal Segerberg squares using bisimulation games. It proves the square finite model property for Segerberg squares of polymodal \(\mathbf{T}\) and \(\mathbf{D}\). It also constructs a faithful embedding of Segerberg squares in the equational theory of relation algebras.
Similar content being viewed by others
Notes
- 1.
The choice of 8, 9 is arbitrary; they are used only as markers for two halves of the disjoint union.
- 2.
In this case we say that \(\varGamma \) is controlled by \(\sigma \).
- 3.
In Shehtman (2012) there is a misprint in the definition of \(\Theta \).
References
Andréka, H., Givant, V., & Németi, I. (1997). Decision problems for equational theories of relation algebras (Vol. 126), Memoirs of the American Mathematical Society. Providence: American Mathematical Society.
Gabbay, D., & Shehtman, V. (1998). Products of modal logics, part 1. Logic Journal of the IGPL, 6, 73–146.
Gabbay, D., & Shehtman, V. (2000). Products of modal logics, part 2: Relativised quantifiers in classical logic. Logic Journal of the IGPL, 8, 165–210.
Gabbay, D., & Shehtman, V. (2002). Products of modal logics, part 3: Products of modal and temporal logics. Studia Logica, 72, 157–183.
Gabbay, D. M., Kurucz, A., Wolter, F., & Zakharyaschev, M. (2003). Many-dimensional modal logics: Theory and applications. Amsterdam: Elsevier.
Goranko, V., & Otto, M. (2007). Model theory of modal logic. In P. Blackburn, J. Van Benthem, & F. Wolter (Eds.), Handbook of modal logic (pp. 249–329). Amsterdam: Elsevier.
Hirsch, R., & Hodkinson, I. (2002). Relation algebras by games. Amsterdam: Elsevier.
Maksimova, L. L. (1975). Modal logics of finite slices. Algebra and logic, 14(3), 304–319.
Maksimova, L. L. (1981). O lokalno konechnykh mnogoobraziyakh psevdobulevykh algebr. In 6th All-Union Algebraical Conference (abstracts), No. 1, Leningrad, pp. 99–100, [On locally finite varieties of pseudoboolean algebras].
Malcev, A. I. (1973). Algebraic systems. Berlin: Springer.
Monk, D. (1964). On representable relation algebras. Michigan Mathematical Journal, 11, 207–210.
Segerberg, K. (1967). On the logic of tomorrow. Theoria, 33, 45–52.
Segerberg, K. (1973). Two-dimensional modal logic. Journal of Philosophical Logic, 2, 77–96.
Shehtman, V. B. (1978). Two-dimensional modal logics. Mathematical Notes, 23, 417–424.
Shehtman, V. (2011). O kvadratakh modalnykh logik s dopolnitelnymi svyazkami. Works of Steklov Mathematical Institute (Trudy), 274, 343–351. [On squares of modal logics with additional connectives].
Shehtman, V. B. (2012). Squares of modal logics with additional connectives. Russian Mathematical Surveys, 67(4), 721–778.
Shehtman, V. B. (2018). Bisimulation games in modal and intuitionistic logic, in preparation.
Tarski, A. (1941). On the calculus of relations. Journal of Symbolic Logic, 6, 73–89.
Acknowledgements
I would like to thank the anonymous referee for useful comments on the first version of the manuscript.
The research presented in this paper was done in part within the framework of the Basic Research Program at National Research University Higher School of Economics and was partially supported within the framework of a subsidy by the Russian Academic Excellence Project 5-100. It was also supported by the RFBR project 16-01-00615 and by the Russian president project NSh-9091.2016.1.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendix
Appendix
In this part we prove a simple syntactic fact from modal logic and recall the proof of some standard identities in relation algebras (for the readers who are less familiar with the subject).
Proposition 1
\(\mathbf{K}+\Diamond ^2p\,{\leftrightarrow }\, p\vdash \square p\,{\leftrightarrow }\,\Diamond p\), and thus
\(\mathbf{K}+\Diamond ^2p\,{\leftrightarrow }\, p\vdash \lnot \Diamond p\,{\leftrightarrow }\,\Diamond \lnot p\).
Proof
In this logic we have \(\Diamond ^2\top \,{\leftrightarrow }\, \top \), i.e., \(\Diamond ^2\top \). So it contains \(\mathbf{D}\) and proves \(\square p\rightarrow \Diamond p\).
For the converse we first obtain \(\square ^2p\,{\leftrightarrow }\, p\) (by substituting \(\lnot p\) for p in the axiom). So \(p\rightarrow \square ^2p\), and by substitution, \(\Diamond p\rightarrow \square ^2\Diamond p\). From \(\square p\rightarrow \Diamond p\) by substitution and monotonicity we have \(\square ^2\Diamond p\rightarrow \square \Diamond ^2 p\). Thus \(\Diamond p\rightarrow \square \Diamond ^2 p\), and by applying the axiom, \(\Diamond p\rightarrow \square p\). \(\boxtimes \)
Proposition 2
The following identities and quasiidentities hold in \(\mathbf{R}{} \mathbf{A}\):
-
(1)
\(x\leqslant y\Rightarrow x^{-1}\leqslant y^{-1}\),
-
(2)
\(\mathbf{1}^{-1}=\mathbf{1}\),
-
(3)
\(z\circ (x\cup y)=(z\circ x)\cup (z\circ y)\),
-
(4)
\({\delta }^{-1}={\delta }\),
-
(5)
\({\delta }\circ x=x\),
-
(6)
\(x\leqslant y\Rightarrow z\circ x\leqslant z\circ y\),
-
(7)
\(x\circ \mathbf{0}=\mathbf{0}\),
-
(8)
\(x\cap (\mathbf{1}\circ y)\leqslant x\circ y^{-1}\circ y\),
-
(9)
\(x\leqslant y\Rightarrow x\circ z\leqslant y\circ z\),
-
(10)
\(x\leqslant {\delta }\Rightarrow x=x^{-1}\).
Proof
(1) \(x\leqslant y\) implies \(y=x\cup y\), and so \(y^{-1}=(x\cup y)^{-1}=x^{-1}\cup y^{-1}\) by (RA2). Hence \(x^{-1}\leqslant y^{-1}\).
(2) \(\mathbf{1}^{-1}\leqslant \mathbf{1}\) implies \((\mathbf{1}^{-1})^{-1}\leqslant \mathbf{1}^{-1}\) by (1), and so \(\mathbf{1}\leqslant \mathbf{1}^{-1}\) by (RA5).
(3) From (RA1), (RA2), (RA6) we have:
Now replace x, y, z by their converses and use (RA5).
(4) \({\delta }^{-1}\circ {\delta }={\delta }^{-1}\) by (RA4); hence
and so
by (RA6) and (RA5). Thus \({\delta }^{-1}={\delta }\).
(5) (RA5) and (RA6) imply \({\delta }^{-1}\circ x^{-1}=x^{-1}\). Then replace x by \(x^{-1}\) and use (4) and (RA5).
(6) Replace y by \(x\cup y\) and apply (3).
(7) Obviously,
Hence by (6) and (RA7)
Now replace x by \(x^{-1}\).
(8) As mentioned in the proof of Lemma 12.8.6, this is a translation of the \(\mathbf{K.t}\)-theorem
To prove the latter, we first obtain
from a temporal axiom, and then apply the \(\mathbf{K}\)-theorem
(9) Similar to (6)
(10) Apply (5), (9) and (8) for \(y={\delta }\):
So for \(x\leqslant {\delta }\) we have by monotonicity and (6), (9)
Hence by taking the converses we obtain
and thus \(x^{-1}= x\). \(\boxtimes \)
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this chapter
Cite this chapter
Shehtman, V. (2018). Segerberg Squares of Modal Logics and Theories of Relation Algebras. In: Odintsov, S. (eds) Larisa Maksimova on Implication, Interpolation, and Definability. Outstanding Contributions to Logic, vol 15. Springer, Cham. https://doi.org/10.1007/978-3-319-69917-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-69917-2_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-69916-5
Online ISBN: 978-3-319-69917-2
eBook Packages: Religion and PhilosophyPhilosophy and Religion (R0)