CS Paper Radar

Arrow Operations in Categories of Lattice-valued Relations

Fatemeh Jowkar, Michael Winter

cs.DM math.CT ·submitted 2026-08-17 16:25 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

From Zero-Dimensional to Continuous Dualities: A Double-Categorical Account

cs.LO math.CTmath.GNmath.LO ·2026-10-06 ·Alexander Kurz, M. Andrew Moshier, Achim Jung
similarity 0.63
Abstract

We investigate how to systematically construct continuous dualities from zero-dimensional dualities, employing well-known methods from algebra, topology, category theory, and domain theory. While our method is general, this paper focusses on the move from Stone spaces to compact Hausdorff spaces and the move from Priestley spaces to compact ordered Hausdorff spaces. The engine of our approach is Stone duality for relations: on the space side quotienting by a preorder turns zero-dimensional spaces into continuous ones, while distributive lattices with a proximity relation are their algebraic duals. Our duality for relations is inherently order-enriched. Double categories organise both functional and relational morphism in the same structure. The move from zero-dimensional to continuous dualities is then a three-step construction: extend a duality from functional to relational morphism, split idempotents, restrict to maps.

0.17

Wreath products of distributive quasi relation algebra frames and their application to representability

cs.LO ·2026-10-28 ·Wilmari Morton, Claudette Robinson
similarity 0.59
Abstract · 36 pages, 14 figures

We adapt a construction by Comer (1983) for polygroups to define the wreath product of the dual frames of two distributive quasi relation algebras satisfying certain conditions and show that it is itself a frame. Frames play a role analogous to that of atom structures for relation algebras. After introducing the notion of a frame network, we establish a correspondence between frame networks satisfying certain conditions and representability of finite distributive quasi relation algebras. Next we describe a frame network for the wreath product of two finite representable distributive quasi relation algebras that satisfies the aforementioned conditions, as well as additional conditions, and use this to conclude that the complex algebra of the wreath product is a representable distributive quasi relation algebra. Thus, our construction provides a method for obtaining representable DqRAs from certain finite DqRAs that are already known to be representable.

0.29

On the semantics of conditional branching

cs.LO cs.PL ·2026-11-19 ·Fredrik Dahlqvist
similarity 0.59
Abstract · 31 pages, proofs in the Appendix

Motivated by the non-standard interpretations of if-then-else in probabilistic and quantum programs we review the different semantics of conditional branching and propose a unifying categorical structure for the interpretation of if-then-else. We show that many semantically important categories possess this structure, covering inter alia classical, probabilistic, quantum or non-deterministic computations. We examine algebraic structures related to and generated by this categorical structure, in particular on collections of predicates. In this setting we show that the skew-associativity rules of GKATs and barycentric algebras are two instances of a common skew-associativity rule.

0.44

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

cs.LO ·2026-09-28 ·Horaţiu Cheval
publishedtheory similarity 0.58
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

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.

0.36

Logical Relations on Display

cs.PL cs.LO ·2026-11-16 ·Steven Schaefer, Johnson He, Max S. New
top venue similarity 0.58
Abstract · 31 pages, 3 figures, to appear at POPL 2027

The metatheory of programming languages suffers from a lack of reuse. Researchers develop individual calculi and prove standard properties, but very few results are truly reused across papers. The problem is worse in proof assistants, where developments routinely duplicate code from prior work or rebuild it from scratch. Category theory provides the most promising path toward reusable programming language semantics. Universal properties capture the type connectives---products, functions, sums---together with their $β$/$η$ laws. Free categorical structures identify syntactic calculi. \emph{Displayed} categories provide a uniform language for specifying logical relations, and general theorems about fibrations allow their structure to be assembled compositionally. In this work we develop a library of formalized category theory in the Cubical Agda proof assistant directly applicable to programming language metatheory. We develop theories of universal properties and free categorical structures, apply them to define denotational semantics and logical relations for simply typed calculi, and identify encodings of the categorical constructions that make typechecking them tractable. From the same categorical components, we construct several familiar results via a logical relations construction---canonicity,parametricity,conservativity---and provide a proof of coherence for monoidal categories.

0.48

Logics vs doctrines, a mirror symmetry

cs.LO math.CTmath.LO ·2026-10-21 ·Ivan Di Liberti, Umberto Tarantino, Lingyuan Ye
theory similarity 0.57
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

Finite Dependence and Invariance Hierarchies for Finitely Supported Structures

cs.LO math.CTmath.LO ·2026-09-14 ·Gabriel Ciobanu
similarity 0.55
Abstract · 44 pages, 2 tables, no figures. Unified synthesis of finite-dependence profiles, invariance hierarchies, freshness, context composition, orb…

Finite support indicates that the dependence is limited, but not how each finite context controls what can be observed. For a data symmetry G \leq Sym(A) and a finitely supported G-set X, we study the finite-dependence profile X^S = {x : Fix_G(S) fixes x}, indexed by finite contexts S \subseteq A. For relations on A^n this yields Boolean algebras B^{(n)}_{G,S} = Inv_n(Fix_G(S)), forming the invariance hierarchy. The hierarchy separates several nominal principles. Its meet law is the relation-algebra form of the Bojanczyk-Klin-Lasota least-support criterion, while level injectivity is fungibility. The independent join law governs composition across unions of contexts; it holds for locally oligomorphic automorphism groups of ultrahomogeneous structures in purely relational languages of arity at most two, but can fail for unary observations over ternary data. Freshness remains valid sort by sort, and its unrestricted some/any form characterizes full equality symmetry among closed groups. With least supports, orbit-finiteness implies finite context levels and a uniform support bound; under local oligomorphicity the converse also holds. Pointwise closure does not change the profile, and standard atomic-site presentations show that suitable ultrahomogeneous structures with the same age have equivalent action topoi, even though their material FSS universes may retain different external cardinal data. Contextual orientability gives a complementary pointed invariant whose threshold is the least support size of choice from unordered pairs. For countable omega-categorical structures with degenerate algebraic closure, the meet law is equivalent to weak elimination of imaginaries.

0.48

A Fibrational Framework For Multi-Conclusion Logics

cs.LO math.LO ·2026-10-27 ·Oualid Merzouga
theory similarity 0.54
Abstract

The fibrational framework of Licata, Shulman, and Riley gives a uniform account of substructural and modal logics for single-conclusion judgments. This thesis extends it to a multiple-output setting in which cartesian resources may be used freely, while linear resources occur exactly once on either side of the turnstile. Judgments are indexed by descriptors: directed acyclic graphs generalizing the tree-shaped expressions of the original framework. Descriptor $2$-cells encode structural transformations, and explicit gates provide weakening, contraction, coweakening, and cocontraction at linear modes. We define a sequent calculus generated by two connectives, $F$ and $U$. We prove identity, invertibility, and cut admissibility. The mode and type theories present linear-non-linear $2$-polycategories, and the projection is a local discrete fibration and a fibration, with opcartesian lifts for one-output base morphisms. Two adequacy results validate the framework: its cartesian fragment recovers the Licata--Shulman--Riley calculus, and its purely linear fragment presents classical multiplicative linear logic. Finally, we relate indexed and fibrational semantics. After developing representability correspondences for multicategories and polycategories, we establish an equivalence between multi-indexed categories over a fixed representable base and multicategorical opfibrations over it, together with its biclosed bifibrational version. We also give a one-way construction from planar poly-indexed data to a planar polycategory.

0.33