PreprintarXiv licencearXiv
Undecidability in Relevant Logic
Abstract
We prove undecidability for every positive relevant logic extending the system axiomatized by hypothetical syllogism, prefixing, and suffixing and contained in the logic of the semilattice frame (Pfin(ℕ), ∪, ∅). This settles the longstanding decision problem for the semilattice relevant logic S in the negative, contrary to prevailing expectations of decidability. It also provides a new proof of Urquhart's (1984) undecidability theorem for R, E, and T, now by reduction from the Wang tiling problem for arbitrarily large finite isosceles right triangular regions of the plane.
Related
- Non-finite Axiomatizability and Undecidability of Cheq
- Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism
- The Undecidability of FO3 and the Calculus of Relations with Just One Binary Relation
- Definability and undecidability via the torsion subgroup of units
- Possibilistic Logic over a Logic of Formal Inconsistency
BibTeX
@misc{knudstorp2026undecidability,
title = {{Undecidability in Relevant Logic}},
author = {Søren Brinck Knudstorp},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.29880},
eprint = {2605.29880},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.29880},
}
RIS
TY - UNPB
TI - Undecidability in Relevant Logic
AU - Søren Brinck Knudstorp
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2605.29880
UR - https://arxiv.org/abs/2605.29880
AB - We prove undecidability for every positive relevant logic extending the system axiomatized by hypothetical syllogism, prefixing, and suffixing and contained in the logic of the semilattice frame (P_fin(ℕ), ∪, ∅). This settles the longstanding decision problem for the semilattice relevant logic S in the negative, contrary to prevailing expectations of decidability. It also provides a new proof of Urquhart's (1984) undecidability theorem for R, E, and T, now by reduction from the Wang tiling problem for arbitrarily large finite isosceles right triangular regions of the plane.
ER -