Skip to content
DraconiticResearch
Search Sources API
186,123 studies31 sourcesUpdated 42 min ago
PreprintCC BY 4.0arXiv

The Undecidability of FO3 and the Calculus of Relations with Just One Binary Relation

  • Yoshiki Nakamura
Open at sourcePDFDOICite

Abstract

The validity problem for first-order logic is a well-known undecidable problem. The undecidability also holds even for FO3 and (equational formulas of) the calculus of relations. In this paper we tighten these undecidability results to the following: (1) FO3 with just one binary relation is undecidable even without equality; and (2) the calculus of relations with just one character and with only composition, union, and complement is undecidable. Additionally we prove that the finite validity problem is also undecidable for the above two classes.

Versions

Related

  1. Todd's relation conjecture and binary relations for multiple zeta values in positive characteristic
    Jinyuan Hu
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  2. OFFER (One-Formula-Facilitates-Every-Relation) for Calculus
    Samuel S. P. Shen
    arXivPreprintCC BY-NC-SA 4.0Full textGeneral mathematicsarXiv
  3. A Catalogue of Properties of Binary Relations: Entailments, Incompatibilities, and Independence Results
    Magnus Boman
    arXivPreprintCC BY 4.0Full textLogic & foundationsarXiv
  4. Generalized Ordered Rough Set Models via Minimal and Maximal Neighborhoods Induced by Binary Relations
    Salama H. Shalil, Mostafa K. El-Bably, Mostafa A. El-Gayar +1
    AxiomsPeer-reviewedCC BY 4.0General mathematicsCrossref
  5. A Note on Binary Quadratic Systems and their relation to complexity theory
    Gabriele Radici, Massimiliano Sala
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{nakamura2026undecidability,
  title = {{The Undecidability of FO3 and the Calculus of Relations with Just One Binary Relation}},
  author = {Yoshiki Nakamura},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.35770},
  eprint = {2610.35770},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.35770},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Undecidability of FO3 and the Calculus of Relations with Just One Binary Relation
AU  - Yoshiki Nakamura
PY  - 2026
DA  - 2026/10/26
PB  - arXiv
DO  - 10.48550/arxiv.2610.35770
UR  - https://arxiv.org/abs/2610.35770
AB  - The validity problem for first-order logic is a well-known undecidable problem. The undecidability also holds even for FO3 and (equational formulas of) the calculus of relations. In this paper we tighten these undecidability results to the following: (1) FO3 with just one binary relation is undecidable even without equality; and (2) the calculus of relations with just one character and with only composition, union, and complement is undecidable. Additionally we prove that the finite validity problem is also undecidable for the above two classes.
ER  -