Skip to main content
Log in

Modal Definability: Two Commuting Equivalence Relations

  • Published:
Logica Universalis Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Balbiani, Ph., Tinchev, T.: Decidability and complexity of definability within the class of all partitions. In: Proceedings of the 5th Panhellenic Logic Symposium, July 25-28, 2005, Athens, Greece, p. 26–33.

  2. Balbiani, Ph., Tinchev, T.: Undecidable problems for modal definability. J. Logic Comput. 27(3), 901–920 (2017)

    MathSciNet  MATH  Google Scholar 

  3. Chagrov, A., Zakharyaschev, M.: Modal Logic. Oxford Logic Guides, Clarendon Press, Oxford (1997)

    MATH  Google Scholar 

  4. Ebbinghaus, H., Flum, J.: Finite Model Theory. Springer-Verlag, Berlin Heidelberg (1995)

    Book  Google Scholar 

  5. Ershov, Yu.L.: Problems of decidability and constructive models (in Russian). Nauka, Moscow (1980)

    Google Scholar 

  6. Ershov, Y.L., Lavrov, I.A., Taimanov, A.D., Taitslin, M.A.: Elementary theories. Uspekhi Mat. Nauk 20(4), 35 (1965)

    MathSciNet  MATH  Google Scholar 

  7. Georgiev, G., Tinchev, T.: Second-order logic on equivalence relations. J. Appl. Non-Classical Logics 18(2–3), 229–246 (2008)

    Article  MathSciNet  Google Scholar 

  8. Rogers, Jr. H.: Certain logical reduction and decision problems. Ann. Math. Second Ser. 64(2), 264–284 (1956)

    Article  MathSciNet  Google Scholar 

  9. Hodges, W.: Model Theory. Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge (2008)

    MATH  Google Scholar 

  10. Janiczak, A.: Undecidability of some simple formalized theories. Fundamenta Mathematicae 40(2), 131–139 (1953)

    Article  MathSciNet  Google Scholar 

  11. Kurucz, Agi, Wolter, Frank, Zakharyaschev, Michael, Gabbay, D.M.: Many-dimensional modal logics: theory and applications. Elsevier, London (2003)

    MATH  Google Scholar 

  12. Lavrov, I.A.: The effective non-separability of the set of identically true formulae and the set of finitely refutable formulae for certain elementary theories. Algebra i Logika. Sem. 2(1), 5–18 (1963)

    MathSciNet  Google Scholar 

  13. Yana Rumenova. Modal definability: two commuting equivalence relations. Master’s thesis, Sofia University St. Kliment Ohridski, 2021

  14. Shoenfield, J.R.: Addison-Wesley Series in Logic. Mathematical logic, Addison-Wesley Publishing Company, Boston (1967)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Yana Rumenova.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Yana Rumenova is the winner of the Ivan Soskov Logic Prize 2021 (Bulgaria) and contestant in the 2nd World Logic Prizes Contest, UNILOG’2022, Crete.

Tinko Tinchev is supported by contract DN 02-15/19.12.2016 with Bulgarian Science Fund.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Rumenova, Y., Tinchev, T. Modal Definability: Two Commuting Equivalence Relations. Log. Univers. 16, 177–194 (2022). https://doi.org/10.1007/s11787-022-00299-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11787-022-00299-4

Keywords

Mathematics Subject Classification

Navigation