Modal Definability: Two Commuting Equivalence Relations

Logica Universalis 16 (1):177-194 (2022)
  Copy   BIBTEX

Abstract

We prove that modal definability with respect to the class of all structures with two commuting equivalence relations is an undecidable problem. The construction used in the proof shows that the same is true for the subclass of all finite structures. For that reason we prove that the first-order theories of these classes are undecidable and reduce the latter problem to the former.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,635

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On Definability in Multimodal Logic.Joseph Y. Halpern, Dov Samet & Ella Segev - 2009 - Review of Symbolic Logic 2 (3):451-468.
Elementary Definability and Completeness in General and Positive Modal Logic.Ernst Zimmermann - 2003 - Journal of Logic, Language and Information 12 (1):99-117.
Definability in the Class of All -Frames – Computability and Complexity.D. T. Georgiev - 2017 - Journal of Applied Non-Classical Logics 27 (1-2):1-26.
Second-Order Logic on Equivalence Relations.Georgi Georgiev & Tinko Tinchev - 2008 - Journal of Applied Non-Classical Logics 18 (2-3):229-246.
? 0 N -Equivalence Relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351-358.
Definability and Computability for PRSPDL.Philippe Balbiani & Tinko Tinchev - 2014 - In Rajeev Goré, Barteld Kooi & Agi Kurucz (eds.), Advances in Modal Logic, Volume 10. CSLI Publications. pp. 16-33.
Maximal R.E. Equivalence Relations.Jeffrey S. Carroll - 1990 - Journal of Symbolic Logic 55 (3):1048-1058.
Sahlqvist Formulas Unleashed in Polyadic Modal Languages.Valentin Goranko & Dimiter Vakarelov - 2002 - In Frank Wolter, Heinrich Wansing, Maarten de Rijke & Michael Zakharyaschev (eds.), Advances in Modal Logic, Volume 3. World Scientific. pp. 221-240.
Superrigidity and Countable Borel Equivalence Relations.Simon Thomas - 2003 - Annals of Pure and Applied Logic 120 (1-3):237-262.
$\sum_{0}^{N}$ -Equivalence Relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351 - 358.

Analytics

Added to PP
2022-02-08

Downloads
7 (#1,036,207)

6 months
2 (#278,853)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Add more citations

References found in this work

Modal Logic.Yde Venema, Alexander Chagrov & Michael Zakharyaschev - 2000 - Philosophical Review 109 (2):286.
Finite Model Theory.Heinz-Dieter Ebbinghaus & Torg Flum - 1997 - Studia Logica 58 (2):332-335.
Second-Order Logic on Equivalence Relations.Georgi Georgiev & Tinko Tinchev - 2008 - Journal of Applied Non-Classical Logics 18 (2-3):229-246.

Add more references