Undecidability in Relevant Logic
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913170554093568 |
|---|---|
| author | Knudstorp, Søren Brinck |
| author_facet | Knudstorp, Søren Brinck |
| contents | 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_{\mathrm{fin}}(\mathbb{N}), \cup, \varnothing)$.
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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_29880 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Undecidability in Relevant Logic Knudstorp, Søren Brinck Logic 03B47, 03B25, 03D10 F.4.1; F.1.1 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_{\mathrm{fin}}(\mathbb{N}), \cup, \varnothing)$. 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. |
| title | Undecidability in Relevant Logic |
| topic | Logic 03B47, 03B25, 03D10 F.4.1; F.1.1 |
| url | https://arxiv.org/abs/2605.29880 |