Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITP.2022.19
URN: urn:nbn:de:0030-drops-167280
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16728/
Hostert, Johannes ; Dudenhefner, Andrej ; Kirst, Dominik
Undecidability of Dyadic First-Order Logic in Coq
| pdf-format: |
|
Abstract
We develop and mechanize compact proofs of the undecidability of various problems for dyadic first-order logic over a small logical fragment. In this fragment, formulas are restricted to only a single binary relation, and a minimal set of logical connectives. We show that validity, satisfiability, and provability, along with finite satisfiability and finite validity are undecidable, by directly reducing from a suitable binary variant of Diophantine constraints satisfiability. Our results improve upon existing work in two ways: First, the reductions are direct and significantly more compact than existing ones. Secondly, the undecidability of the small logic fragment of dyadic first-order logic was not mechanized before. We contribute our mechanization to the Coq Library of Undecidability Proofs, utilizing its synthetic approach to computability theory.
BibTeX - Entry
@InProceedings{hostert_et_al:LIPIcs.ITP.2022.19,
author = {Hostert, Johannes and Dudenhefner, Andrej and Kirst, Dominik},
title = {{Undecidability of Dyadic First-Order Logic in Coq}},
booktitle = {13th International Conference on Interactive Theorem Proving (ITP 2022)},
pages = {19:1--19:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-252-5},
ISSN = {1868-8969},
year = {2022},
volume = {237},
editor = {Andronick, June and de Moura, Leonardo},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16728},
URN = {urn:nbn:de:0030-drops-167280},
doi = {10.4230/LIPIcs.ITP.2022.19},
annote = {Keywords: undecidability, synthetic computability, first-order logic, Coq}
}
| Keywords: | undecidability, synthetic computability, first-order logic, Coq | |
| Seminar: | 13th International Conference on Interactive Theorem Proving (ITP 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 03.08.2022 | |
| Supplementary Material: | https://www.ps.uni-saarland.de/extras/fol-dyadic |
