Monads on Categories of Relational Structures.

DOI10.4230/LIPICS.CALCO.2021.14MaRDI QIDQ6061674zbMATH OpenOpenAlexFDO

Authors Chase Ford, Stefan Milius, Lutz Schröder

Publication date 8 December 2023

Full work available at URL https://arxiv.org/abs/2107.03880

zbMATH Keywords

monadsrelational logicrelational structuresHorn theories

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We introduce a framework for universal algebra in categories of relational structures given by finitary relational signatures and finitary or infinitary Horn theories, with the arity $lambda$ of a Horn theory understood as a strict upper bound on the number of premisses in its axioms; key examples include partial orders ($lambda=omega$) or metric spaces ($lambda=omeg{a}_1$). We establish a bijective correspondence between $lambda$-accessible enriched monads on the given category of relational structures and a notion of $lambda$-ary algebraic theories (i.e. with operations of arity $<lambda$), with the syntax of algebraic theories induced by the relational signature (e.g. inequations or equations-up-to-$epsilon$). We provide a generic sound and complete derivation system for such relational algebraic theories, thus in particular recovering (extensions of) recent systems of this type for monads on partial orders and metric spaces by instantiation. In particular, we present an $omeg{a}_1$-ary algebraic theory of metric completion. The theory-to-monad direction of our correspondence remains true for the case of $kappa$-ary algebraic theories and $kappa$-accessible monads for $kappa<lambda$, e.g. for finitary theories over metric spaces.

Cited in

(10)

• Logical relations for monadic types
• scientific article; zbMATH DE number 1284150 (Why is no real title available?)
• Relativized universal algebra via partial Horn logic
• scientific article; zbMATH DE number 1948186 (Why is no real title available?)
• Universal quantitative algebra for fuzzy relations and generalised metric spaces
• Belief propagation in monoidal categories
• Algebraic reasoning over relational structures
• Twists of graded algebras in monoidal categories
• Sum and tensor of quantitative effects
• Quantitative graded semantics and spectra of behavioural metrics

This page was built for publication: Monads on Categories of Relational Structures.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6061674)