Metraipolis › archive › dc_c66a0368ca67

Completeness and incompleteness of basic matching logic — arXiv:2608.13306

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.13306
License (as archived)
CC0-1.0
Archived
2026-10-19T04:57:17.408Z
SHA-256 of the archived text
1a2581d71f39b2184d50129004309acff3f3807b6dffdee4a1eec14cfd4445ae
Stable URL of this page
https://metraipolis.com/documento/dc_c66a0368ca67

How to cite

Completeness and incompleteness of basic matching logic — arXiv:2608.13306 — arXiv (en), https://arxiv.org/abs/2608.13306 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c66a0368ca67 (Metraipolis archive dc_c66a0368ca67, sha256 1a2581d71f39b2184d50129004309acff3f3807b6dffdee4a1eec14cfd4445ae)
BibTeX
@misc{dcc66a0368ca67,
  title = {Completeness and incompleteness of basic matching logic — arXiv:2608.13306},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.13306},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c66a0368ca67; sha256 1a2581d71f39b2184d50129004309acff3f3807b6dffdee4a1eec14cfd4445ae},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.13306. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Basic matching logic is matching logic without definedness. Symbols are interpreted as set-valued operations, element variables denote singletons and are bound by $\exists$, and no connective uniformly internalizes totality. For basic matching logic without fixpoints over an arbitrary one-sorted finitary signature, we prove \emph{global completeness} ($\Gamma\vDash\varphi$ iff $\Gamma\vdash\varphi$, for arbitrary, possibly infinite $\Gamma$) and, as a corollary, conservativity of the definedness extension. The proof localizes $\Gamma$ to a theory $\Delta_\Gamma$ and reduces semantic consequence and derivability to the same local relation: $\Gamma\vDash\varphi$ iff $\Delta_\Gamma\vDash_\text{loc}\varphi$ iff $\Gamma\vdash\varphi$. A double-cover construction establishes the semantic equivalence. Least fixpoints destroy effective axiomatizability. Over a signature with one unary and two binary symbols and no constants, validity is not recursively enumerable; hence no sound calculus with a recursively enumerable proof relation is even weakly complete, already for the empty theory and without definedness. The positive result is also sharp in the number of sorts. Global completeness fails with three sorts for a satisfiable $\Gamma$. Thus the completeness conjecture holds for one sort and fails in general. The negative results arise from sort flow, fixpoint effectivity, and, for hybrid logic, an obstruction to every well-founded calculus whose leaves are hypotheses or valid patterns and whose rules respect localization. This yields a matching-logic-independent dichotomy: the language with state variables bound by $\exists$ and $\forall$ over modalities of arbitrary arity is globally complete without nominals, while no calculus in that well-founded class is globally complete once nominals are added.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-14 in cs.LO).
Categorie arXiv: Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2608.13306 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T04:53:04.875Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-08-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).