CS Paper Radar

Complete Heyting Algebra Semantics for an Intuitionistic Version of Matching Logic (Extended Abstract)

Horaţiu Cheval

cs.LO ·submitted 2026-09-28 11:00 UTC · v1
publishedtheory

Abstract

We present work in progress towards an intuitionistic version of Applicative Matching Logic. We introduce a semantics based on complete Heyting algebras, and propose a proof system which we prove to be sound relative to this semantics.

Comment
In Proceedings FROM 2026, arXiv:2609.30324
Journal ref
EPTCS 452, 2026, pp. 217-224
DOI
10.4204/EPTCS.452.14

Closest papers

Nearest neighbours by meaning across the whole index.

Two applications of the point-free coderivative

cs.LO math.LOmath.CT ·2026-09-24 ·Zoltan A. Kocsis
similarity 0.66
Abstract · 23 pages, 1 figure

We present two new applications of Simmons' point-free Cantor-Bendixson coderivative operator in intuitionistic logic. First, we use it to give a simplified proof of the recent result of Xu and Ye that the free Heyting algebra on two generators does not occur as the Heyting algebra of subterminal objects in any elementary topos. Then we use it to prove that complete Heyting algebra semantics is not strongly complete for intuitionistic second-order propositional logic: semantic consequence from an arbitrary set of assumptions does not coincide with ordinary syntactic consequence.

0.33

Dependently Typed Model Composition for Matching Logic

cs.LO ·2026-09-28 ·Ádám Kurucz, Péter Bereczky, Dániel Horpácsi
published similarity 0.62
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

This paper investigates model composition—often referred to as "gluing"—within the framework of matching logic. Specifically, we examine the systematic combination of existing signatures, variable valuations, theories, and their corresponding models. Our primary objective is to ensure that this composition preserves satisfaction proofs; that is, any theory validated by the individual constituent models is also validated by the resulting composite model. Our definitions are based on a polyadic, sorted variant of matching logic, which has also been expressed in the Rocq proof assistant. Therefore, we outline our definitions with dependent types for this work to serve as a direct blueprint for the mechanization in the short-term future.

0.29

Matching-Logic-Based Understanding of Polynomial Functors and their Initial/Final Models Revisited

cs.LO cs.PL ·2026-11-18 ·Dorel Lucanu
theory similarity 0.61
Abstract · 44 pages. Revised and substantially extended version of arXiv:2309.13798 (EPTCS 389, FROM 2023); Appendix C lists the changes

Many data types used in programming are initial algebras or final coalgebras of polynomial functors. We show how to specify them uniformly in matching logic, using the representation of polynomial functors as unary container functors $X\mapsto\sum_{a:A}X^{B[a]}$. For each container functor, we give a matching logic theory of its initial algebra and one of its final coalgebra. Besides the no-junk and no-confusion axioms and their duals, these theories include axioms about the elements that represent functions, for the initial algebra, and a bisimilarity axiom and a realisation axiom, for the final coalgebra; the existence axioms use free set variables to range over all subsets of a model. We prove that, in every model, the algebra extracted from the model is an initial algebra (a W-type) and the extracted coalgebra is a final coalgebra (an M-type) of the container extracted from the model, i.e., the one given by the model's interpretation of the shapes and positions, and that such models exist. So the data types are captured relative to the interpretation of the sorts of shapes and positions, and absolutely whenever these sorts are fixed by auxiliary specifications, which we show for finite sets, products, dependent sums, and (co)inductive sorts built from them. We derive the induction, coinduction, and bisimulation principles as theorems, and illustrate the approach on lists and on Moore machines. This paper revises and substantially extends a paper published in EPTCS 389 (FROM 2023): several axioms are corrected, and the adequacy and satisfiability proofs are new.

0.43

Completeness and incompleteness of basic matching logic

cs.LO ·2026-08-13 ·Xiaohong Chen, Grigore Rosu
theory similarity 0.60
Abstract

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} ($Γ\vDash\varphi$ iff $Γ\vdash\varphi$, for arbitrary, possibly infinite $Γ$) and, as a corollary, conservativity of the definedness extension. The proof localizes $Γ$ to a theory $Δ_Γ$ and reduces semantic consequence and derivability to the same local relation: $Γ\vDash\varphi$ iff $Δ_Γ\vDash_\text{loc}\varphi$ iff $Γ\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 $Γ$. 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.

0.04

Logics vs doctrines, a mirror symmetry

cs.LO math.CTmath.LO ·2026-10-21 ·Ivan Di Liberti, Umberto Tarantino, Lingyuan Ye
theory similarity 0.59
Abstract · Corrected typo in title and reworded abstract

We study the relationship between doctrines, encoding 2-categories of theories in predicate logic, and fragments of geometric logic, defined through Kan injectivity in the 2-category of topoi. After a brief historical account of the notion of doctrine, we propose our working definition. Our main result then establishes a Galois connection between doctrines and subgeometric logics. This connection suggests a mirror symmetry between the world of doctrines and the world of logics, in which constructions and results on either side admit counterparts on the other. We develop this symmetry through constructions of syntactic categories and classifying topoi in both settings, recovering the familiar examples from categorical logic. We prove paired Diaconescu-type theorems and give symmetric universal characterisations of the two closure operators induced by the Galois connection. Finally, we show that passing from a doctrine to its closure induces a reflection between the corresponding 2-categories of algebras, and we relate this reflection to conceptual completeness.

0.29

Restricted Peirce's Law and Natural Deduction

cs.LO ·2026-10-29 ·Satoru Niki
publishedtheoryhot direction similarity 0.59
Abstract · In Proceedings NCL'26, arXiv:2610.34489

The constructive logic JP' is known to be the weakest logic between intuitionistic and minimal logic that satisfies Glivenko's theorem. In spite of this natural and desirable formal property, the motivation for its notion of negation remains rather elusive: it can be characterised by a restriction of Peirce's law or by the double negation of ex falso quodlibet, neither of which is very intuitive. In order to have an alternative perspective on this negation, we study in this paper a couple of natural deduction systems for JP'. We first present a system that is normalisable and satisfies a restricted form of the subformula property. Then a modification of this system is introduced, whose rules satisfy the separation of connectives and the full subformula property. Afterwards we turn our attention to a typed lambda-calculus, with respect to which our natural deduction enjoys the Curry-Howard correspondence, followed by a concluding discussion.

0.40

Arrow Operations in Categories of Lattice-valued Relations

cs.DM math.CT ·2026-08-17 ·Fatemeh Jowkar, Michael Winter
similarity 0.58
Abstract

Arrow allegories provide a convenient abstract framework to work with lattice-valued relations, or more precisely, relations that use the elements of a given Heyting algebra as truth values. One characteristic of arrow allegories is that all relations of the given arrow allegory use the same Heyting algebra ${\mathcal H}$. In this paper we want to extend this approach to allegories where relations between different objects may use different lattices of truth values and even further to relations that use a different lattice of truth values for every pair in the relation. Therefore, we define three concrete allegories, $\mathrm{Rel}({\mathcal H})$, $\mathrm{Rel}^u({\mathcal H})$ and ${\mathcal H}{\rm-Rel}$, where the allegory listed later is a full suballegory of the previous ones. These three allegories capture the three different situations mentioned above. In particular, ${\mathcal H}{\rm-Rel}$ is the standard example of an arrow category. We investigate these allegories and provide suitable categorical definitions for these structures.

0.23

The Metacomplexity Structure of Search Problems

cs.CC ·2026-11-18 ·Shalev Ben-David, M. H. Ebtehaj
similarity 0.58
Abstract · 48 pages

We study the metacomplexity tasks of refuting an algorithm for a given search problem or refuting a mapping reduction between two search problems. We show that these tasks are deeply related to the structure of the lattice of search problems under mapping reductions: the "refutation of a reduction" task amounts to a certain Heyting-type arrow in this lattice. We then give several structural complexity results about search problems and show they have implications for metacomplexity. First, by relating metacomplexity to a Heyting algebra structure, we are able to translate results from intuitionistic logic into complexity theoretic consequences. For example, the propositional logic identity $x\wedge \neg x=\bot$ translates to the following complexity-theoretic fact: if a search problem $R$ reduces to both $S$ and to the refutation task of $S$, then $R$ is in $\mathsf{FP}$. All such logical identities that hold in intuitionistic logic translate to complexity in a black box way. We find prime ideals of the reducibility lattice of search problems; as a consequence, we show that for any verifiable search problem $S$, either $S$ is in $(\mathsf{FP/poly})_{io}$ or else the refutation task of $S$ is in $(\mathsf{FP/poly})_{io}$. Similarly, either $S$ has infinitely-often heuristic algorithms or else the refutation task of $S$ has infinitely often heuristic algorithms. Finally, we give a structural result that may be of independent interest: any "tamely semantic" class of search problems (one which can be enumerated using a Halting oracle) is characterized by its decidably verifiable hard problems.

0.41