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.

Categories

Keywords

Reprint years

DOI

10.1007/s11787-022-00299-4

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,227

External links

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

Through your library

My notes

Similar books and articles

Modal Definability Based on Łukasiewicz Validity Relations.Bruno Teheux - 2016 - Studia Logica 104 (2):343-363.
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.
Counting the Number of Equivalence Classes of Borel and Coanalytic Equivalence Relations.Equivalences Generated by Families of Borel Sets.A Reflection Phenomenon in Descriptive Set Theory.Equivalence Relations, Projective and Beyond.Counting Equivalence Classes for co-κ-Souslin Equivalence Relations.On Lusin's Restricted Continuum Problem. [REVIEW]Alain Louveau - 1987 - Journal of Symbolic Logic 52 (3):869-870.
Sahlqvist Formulas Unleashed in Polyadic Modal Languages.Valentin Goranko & Dimiter Vakarelov - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 221-240.
On definability in multimodal logic: On definability in multimodal logic.Joseph Y. Halpern - 2009 - Review of Symbolic Logic 2 (3):451-468.
On Σ1 1 equivalence relations over the natural numbers.Ekaterina B. Fokina & Sy-David Friedman - 2012 - Mathematical Logic Quarterly 58 (1-2):113-124.
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.
Modal languages for topology: Expressivity and definability.Balder ten Cate, David Gabelaia & Dmitry Sustretov - 2009 - Annals of Pure and Applied Logic 159 (1-2):146-170.

Analytics

Added to PP
2022-02-08

Downloads
32 (#502,492)

6 months
21 (#128,287)

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