pith. sign in

arxiv: 2502.10323 · v5 · submitted 2025-02-14 · 🧮 math.CT · cs.LO

A taxonomy of categories for relations

Cipriano Junior Cioffo , Fabio Gadducci , Davide Trotta This is my paper

Pith reviewed 2026-05-23 02:56 UTC · model grok-4.3

classification 🧮 math.CT cs.LO
keywords categories for relationsKleisli categoriessymmetric monoidal monadsenriched categoriestaxonomy of categoriesrelation categoriesmonads in category theory
0
0 comments X

The pith

Categories for relations arise as Kleisli categories of symmetric monoidal monads.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper surveys the various categories that abstract the structure of relations and their enriched counterparts. It shows that these categories can be obtained uniformly through the Kleisli construction applied to symmetric monoidal monads. This presentation organizes a scattered collection of definitions and frameworks from the literature into a single coherent taxonomy. A sympathetic reader would value the reduction of multiple independent notions to one underlying mechanism, which makes comparisons and extensions more straightforward.

Core claim

The diverse categories for relations appearing in the literature, including their enriched versions, arise as Kleisli categories of symmetric monoidal monads, and this construction supplies a taxonomy that brings clarity and organisation to the many related concepts and frameworks.

What carries the argument

The Kleisli category of a symmetric monoidal monad, which converts the monad into a category whose arrows model relations while preserving the monoidal structure.

If this is right

  • Many existing frameworks for relations recover directly from the Kleisli construction applied to appropriate monads.
  • Enriched categories for relations follow the same uniform pattern as the ordinary ones.
  • The taxonomy allows systematic comparison of different relation-based structures.
  • New relation categories can be generated by selecting different symmetric monoidal monads.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The uniform construction might suggest ways to import techniques from monad theory into the study of relations.
  • It could link relation categories to effect systems or other computational structures that also use monads.
  • The approach might extend to other relational-like structures beyond the ones already covered in the literature.

Load-bearing premise

That the diverse categories for relations in the existing literature can be captured without significant omissions or distortions as Kleisli categories of symmetric monoidal monads.

What would settle it

Identification of a standard category for relations (or an enriched variant) that cannot be recovered as the Kleisli category of any symmetric monoidal monad.

read the original abstract

The study of categories that abstract the structural properties of relations has been extensively developed over the years, resulting in a rich and diverse body of work. This paper strives to provide a modern presentation of these ``categories for relations'', including their enriched version, further showing how they arise as Kleisli categories of symmetric monoidal monads. The resulting taxonomy aims at bringing clarity and organisation to the many related concepts and frameworks occurring in the literature.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript provides a modern presentation and taxonomy of categories for relations (including enriched versions), claiming that they arise uniformly as Kleisli categories of symmetric monoidal monads in order to organize and clarify the existing literature on these structures.

Significance. If the claimed uniform and faithful capture holds without significant omissions or distortions, the taxonomy would offer a valuable organizational framework for the field, highlighting connections across prior work on relation categories in category theory.

major comments (1)
  1. [Taxonomy construction and examples] The central claim (abstract and taxonomy sections) that all cited categories for relations from the literature arise exactly as Kleisli categories of symmetric monoidal monads requires explicit verification; without a dedicated mapping, table, or case-by-case recovery in the main taxonomy, it is impossible to confirm completeness or absence of cases needing extra data or failing the symmetric monoidal condition.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed reading and for highlighting the need for clearer verification of the central claim. We respond to the major comment below.

read point-by-point responses

  1. Referee: [Taxonomy construction and examples] The central claim (abstract and taxonomy sections) that all cited categories for relations from the literature arise exactly as Kleisli categories of symmetric monoidal monads requires explicit verification; without a dedicated mapping, table, or case-by-case recovery in the main taxonomy, it is impossible to confirm completeness or absence of cases needing extra data or failing the symmetric monoidal condition.

    Authors: The taxonomy is developed by explicitly constructing, for each cited category of relations (including enriched variants), a symmetric monoidal monad on an appropriate base category such that the Kleisli category recovers the original structure; these constructions appear in the relevant taxonomy subsections. Nevertheless, we agree that the absence of a single consolidated mapping or table makes independent verification more laborious than necessary. We will therefore add a summary table in the revised manuscript that lists each cited category, its corresponding symmetric monoidal monad, the base category, and any relevant enrichment data, thereby making the completeness claim immediately checkable. revision: yes

Circularity Check

0 steps flagged

No circularity; taxonomy organizes external literature

full rationale

The paper's central claim is a presentation and organization of existing categories for relations as Kleisli categories of symmetric monoidal monads. No equations, definitions, or steps in the provided abstract or description reduce a result to its own inputs by construction, self-citation chains, or fitted parameters renamed as predictions. The work explicitly draws on prior literature for its examples and claims, making the derivation self-contained against external benchmarks rather than internally circular.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The taxonomy rests on standard definitions from category theory. No free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Kleisli categories of symmetric monoidal monads satisfy the structural properties needed to model relations
    The paper uses this as the unifying construction for the taxonomy.

pith-pipeline@v0.9.0 · 5590 in / 1191 out tokens · 39586 ms · 2026-05-23T02:56:59.576865+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

66 extracted references · 66 canonical work pages

  1. [1]

    American Mathe- matical Society, 2010

    Marcelo Aguiar and Swapneel Mahajan.Monoidal functors, species and Hopf algebras, volume 29 ofCRM Monograph Series. American Mathe- matical Society, 2010

    work page 2010

  2. [2]

    Niefield

    Bernhard Banaschewski and Susan B. Niefield. Projective and supercoher- ent frames.Journal of Pure and Applied Algebra, 70(1-2):45–51, 1991

    work page 1991

  3. [3]

    Cat´ egories avec multiplication.Comptes Rendus de l’Acad´ emie des Sciences de Paris, 256:1887–1890, 1963

    Jean B´ enabou. Cat´ egories avec multiplication.Comptes Rendus de l’Acad´ emie des Sciences de Paris, 256:1887–1890, 1963

    work page 1963

  4. [4]

    Diagrammatic algebra of first order logic

    Filippo Bonchi, Alessandro Di Giorgio, Nathan Haydon, and Pawe l Soboci´ nski. Diagrammatic algebra of first order logic. InLICS 2024, pages 16:1–16:15. ACM, 2024

    work page 2024

  5. [5]

    When Law- vere meets Peirce: An equational presentation of boolean hyperdoctrines

    Filippo Bonchi, Alessandro Di Giorgio, and Davide Trotta. When Law- vere meets Peirce: An equational presentation of boolean hyperdoctrines. In Rastislav Kr´ aloviˇ c and Anton´ ın Kuˇ cera, editors,MFCS 2024, volume 306 ofLIPIcs, pages 30:1–30:19. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2024

    work page 2024

  6. [6]

    String diagram rewrite theory I: Rewriting with Frobenius structure.Journal of the ACM, 69(2):14:1–14:58, 2022

    Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawe l Soboci´ nski, and Fabio Zanasi. String diagram rewrite theory I: Rewriting with Frobenius structure.Journal of the ACM, 69(2):14:1–14:58, 2022

    work page 2022

  7. [7]

    Borceux.Handbook of Categorical Algebra 2: Categories and Structures, volume 51 ofEncyclopedia of Mathematics and its Applications

    F. Borceux.Handbook of Categorical Algebra 2: Categories and Structures, volume 51 ofEncyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1994

    work page 1994

  8. [8]

    Some algebraic laws for spans (and their connections with multirelations)

    Roberto Bruni and Fabio Gadducci. Some algebraic laws for spans (and their connections with multirelations). In Wolfram Kahl, David Lorge Par- nas, and Gunther Schmidt, editors,RelMiS 2001, volume 44(3) ofENTCS, pages 175–193. Elsevier, 2003. 38

    work page 2001

  9. [9]

    Normal forms for al- gebras of connection.Theoretical Computer Science, 286(2):247–292, 2002

    Roberto Bruni, Fabio Gadducci, and Ugo Montanari. Normal forms for al- gebras of connection.Theoretical Computer Science, 286(2):247–292, 2002

    work page 2002

  10. [10]

    Bicategories of partial maps.Cahiers de Topologie et G´ eom´ etrie Diff´ erentielle Cat´ egoriques, 28(2):111–126, 1987

    Aurelio Carboni. Bicategories of partial maps.Cahiers de Topologie et G´ eom´ etrie Diff´ erentielle Cat´ egoriques, 28(2):111–126, 1987

    work page 1987

  11. [11]

    Kelly, Robert F.C

    Aurelio Carboni, Gregory M. Kelly, Robert F.C. Walters, and Richard J. Wood. Cartesian bicategories II.Theory and Applications of Categories, 19(6):93–124, 2008

    work page 2008

  12. [12]

    Aurelio Carboni, Stephen Lack, and Robert F.C. Walters. Introduction to extensive and distributive categories.Journal of Pure and Applied Algebra, 84(2):145–158, 1993

    work page 1993

  13. [13]

    Aurelio Carboni and Robert F.C. Walters. Cartesian bicategories I.Journal of Pure and Applied Algebra, 49(1):11–32, 1987

    work page 1987

  14. [14]

    Iterated distributive laws.Mathematical Proceedings of the Cambridge Philosophical Society, 150(3):459–487, 2011

    Eugenia Cheng. Iterated distributive laws.Mathematical Proceedings of the Cambridge Philosophical Society, 150(3):459–487, 2011

    work page 2011

  15. [15]

    Disintegration and Bayesian inversion via string diagrams.Mathematical Structures in Computer Science, 29(7):938–971, 2019

    Kenta Cho and Bart Jacobs. Disintegration and Bayesian inversion via string diagrams.Mathematical Structures in Computer Science, 29(7):938–971, 2019

    work page 2019

  16. [16]

    Cockett and Stephen Lack

    James R.B. Cockett and Stephen Lack. Restriction categories I: categories of partial maps.Theoretical Computer Science, 270(1):223–259, 2002

    work page 2002

  17. [17]

    Cockett and Stephen Lack

    James R.B. Cockett and Stephen Lack. Restriction categories II: partial map classification.Theoretical Computer Science, 294(1):61–102, 2003

    work page 2003

  18. [18]

    Cockett and Stephen Lack

    James R.B. Cockett and Stephen Lack. Restriction categories III: colim- its, partial limits and extensivity.Mathematical Structures in Computer Science, 17(4):775–817, 2007

    work page 2007

  19. [19]

    A 2-categorical presentation of term graph rewriting

    Andrea Corradini and Fabio Gadducci. A 2-categorical presentation of term graph rewriting. In E. Moggi and G. Rosolini, editors,CTCS 1997, volume 1290 ofLNCS, pages 87–105, Berlin, 1997. Springer

    work page 1997

  20. [20]

    An algebraic presentation of term graphs, via gs-monoidal categories.Applied Categorical Structures, 7(4):299–331, 1999

    Andrea Corradini and Fabio Gadducci. An algebraic presentation of term graphs, via gs-monoidal categories.Applied Categorical Structures, 7(4):299–331, 1999

    work page 1999

  21. [21]

    Andrea Corradini and Fabio Gadducci. Rewriting on cyclic struc- tures: Equivalence between the operational and the categorical descrip- tion.RAIRO - Theoretical Informatics and Applications - Informatique Th´ eorique et Applications, 33(4-5):467–493, 1999

    work page 1999

  22. [22]

    A functorial semantics for multi- algebras and partial algebras, with applications to syntax.Theoretical Com- puter Science, 286(2):293–322, 2002

    Andrea Corradini and Fabio Gadducci. A functorial semantics for multi- algebras and partial algebras, with applications to syntax.Theoretical Com- puter Science, 286(2):293–322, 2002. 39

    work page 2002

  23. [23]

    Scalars, monads, and categories

    Dion Coumans and Bart Jacobs. Scalars, monads, and categories. In Chris Heunen, Mehrnoosh Sadrzade, and Edward Grefenstette, editors,Quantum Physics and Linguistics: A Compositional, Diagrammatic Discourse, pages 184–216. Oxford University Press, 2013

    work page 2013

  24. [24]

    Partiality, cartesian closedness, and toposes.Information and Computation, 80(1):50–95, 1989

    Pierre-Louis Curien and Adam Obtu lowicz. Partiality, cartesian closedness, and toposes.Information and Computation, 80(1):50–95, 1989

    work page 1989

  25. [25]

    Evidential decision theory via partial Markov categories

    Elena Di Lavore and Mario Rom´ an. Evidential decision theory via partial Markov categories. InLICS 2023, pages 1–14. IEEE, 2023

    work page 2023

  26. [26]

    Partial Markov categories.arXiv preprint arXiv:2502.03477, 2025

    Elena Di Lavore, Mario Rom´ an, and Pawe l Soboci´ nski. Partial Markov categories.arXiv preprint arXiv:2502.03477, 2025

    work page arXiv 2025

  27. [27]

    Samuel Eilenberg and Gregory M. Kelly. Closed categories. In Samuel Eilenberg, David K. Harrison, Saunders MacLane, and Helmut R¨ ohrl, edi- tors,Categorical Algebra, pages 451–462. Springer, 1966

    work page 1966

  28. [28]

    Brendan Fong and David I. Spivak. Regular and relational categories: Revisiting ‘Cartesian bicategories I’.CoRR, abs/1909.00069, 2019

    work page arXiv 1909

  29. [29]

    Brendan Fong and David I. Spivak. Supplying bells and whistles in sym- metric monoidal categories.CoRR, abs/1908.02633, 2019

    work page arXiv 1908

  30. [30]

    Coalgebras and cartesian categories.Communications in Algebra, 4:665–667, 1976

    Thomas Fox. Coalgebras and cartesian categories.Communications in Algebra, 4:665–667, 1976

    work page 1976

  31. [31]

    Elsevier B.V, 1990

    Peter Freyd and Andre Scedrov.Categories, Allegories, volume 39 ofNorth- Holland Mathematical Library. Elsevier B.V, 1990

    work page 1990

  32. [32]

    A synthetic approach to Markov kernels, conditional inde- pendence and theorems on sufficient statistics.Advances in Mathematics, 370:107239, 2020

    Tobias Fritz. A synthetic approach to Markov kernels, conditional inde- pendence and theorems on sufficient statistics.Advances in Mathematics, 370:107239, 2020

    work page 2020

  33. [33]

    Weakly Markov categories and weakly affine monads

    Tobias Fritz, Fabio Gadducci, Paolo Perrone, and Davide Trotta. Weakly Markov categories and weakly affine monads. In Paolo Baldan and Valeria de Paiva, editors,CALCO 2023, volume 270 ofLIPIcs, pages 16:1–16:17. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2023

    work page 2023

  34. [34]

    From gs-monoidal to oplax cartesian categories: Constructions and functorial completeness.Applied Categorical Structures, 31(5):42, 2023

    Tobias Fritz, Fabio Gadducci, Davide Trotta, and Andrea Corradini. From gs-monoidal to oplax cartesian categories: Constructions and functorial completeness.Applied Categorical Structures, 31(5):42, 2023

    work page 2023

  35. [35]

    Stochastic order on metric spaces and the ordered Kantorovich monad.Advances in Mathematics, 366:107081, 2020

    Tobias Fritz and Paolo Perrone. Stochastic order on metric spaces and the ordered Kantorovich monad.Advances in Mathematics, 366:107081, 2020

    work page 2020

  36. [36]

    Probability, valua- tions, hyperspace: Three monads on Top and the support as a morphism

    Tobias Fritz, Paolo Perrone, and Sharwin Rezagholi. Probability, valua- tions, hyperspace: Three monads on Top and the support as a morphism. Mathematical Structures in Computer Science, 31(8):850?897, 2021. 40

    work page 2021

  37. [37]

    PhD thesis, University of Pisa, 1996

    Fabio Gadducci.On The Algebraic Approach To Concurrent Term Rewrit- ing. PhD thesis, University of Pisa, 1996

    work page 1996

  38. [38]

    A term-graph syntax for algebras over multisets

    Fabio Gadducci. A term-graph syntax for algebras over multisets. In An- drea Corradini and Ugo Montanari, editors,WADT 2008, volume 5486 of LNCS, pages 152–165. Springer, 2008

    work page 2008

  39. [39]

    A bi-categorical ax- iomatisation of concurrent graph rewriting

    Fabio Gadducci, Reiko Heckel, and Merc` e Llabr´ es. A bi-categorical ax- iomatisation of concurrent graph rewriting. In Martin Hofmann, Giuseppe Rosolini, and Dusko Pavlovic, editors,CTCS 1999, volume 29 ofENTCS, pages 80–100. Elsevier, 1999

    work page 1999

  40. [40]

    Categorial in- dependence and L´ evy processes.Symmetry, Integrability and Geometry: Methods and Applications, 18:075:1–075:27, 2022

    Malte Gerhold, Stephanie Lachs, and Michael Sch¨ urmann. Categorial in- dependence and L´ evy processes.Symmetry, Integrability and Geometry: Methods and Applications, 18:075:1–075:27, 2022

    work page 2022

  41. [41]

    Golubtsov

    Peter V. Golubtsov. Axiomatic description of categories of information transformers.Problems of Information Transmission, 35(3):259–274, 1999

    work page 1999

  42. [42]

    Golubtsov

    Peter V. Golubtsov. Monoidal Kleisli category as a background for informa- tion transformers theory.Information Theory and Information Processing, 2(1):62–84, 2002

    work page 2002

  43. [43]

    Springer, 2021

    Marino Gran.An introduction to regular categories. Springer, 2021

    work page 2021

  44. [44]

    Lectures on categorical quantum mechan- ics.Computer Science Department

    Chris Heunen and Jamie Vicary. Lectures on categorical quantum mechan- ics.Computer Science Department. Oxford University, 2012

    work page 2012

  45. [45]

    Double categories of relations relative to factorisation systems.Applied Categorical Structures, 33(2):11, 2025

    Keisuke Hoshino and Hayato Nasu. Double categories of relations relative to factorisation systems.Applied Categorical Structures, 33(2):11, 2025

    work page 2025

  46. [46]

    Semantics of weakening and contraction.Annals of Pure and Applied Logic, 69(1):73–106, 1994

    Bart Jacobs. Semantics of weakening and contraction.Annals of Pure and Applied Logic, 69(1):73–106, 1994

    work page 1994

  47. [47]

    Affine monads and side-effect-freeness

    Bart Jacobs. Affine monads and side-effect-freeness. In Ichiro Hasuo, editor, CMCS 2016, volume 9608 ofLNCS, pages 53–72. Springer, 2016

    work page 2016

  48. [48]

    From probability monads to commutative effectuses.Journal of Logic and Algebraic Methods in Programming, 94:200–237, 2018

    Bart Jacobs. From probability monads to commutative effectuses.Journal of Logic and Algebraic Methods in Programming, 94:200–237, 2018

    work page 2018

  49. [49]

    Traced monoidal cate- gories.Mathematical Proceedings of the Cambridge Philosophical Society, 119(3):447–468, 1996

    Andr´ e Joyal, Ross Street, and Dominic Verity. Traced monoidal cate- gories.Mathematical Proceedings of the Cambridge Philosophical Society, 119(3):447–468, 1996

    work page 1996

  50. [50]

    Gregory M. Kelly. A note on relations relative to a factorisation system. In Aurelio Carboni, Maria Cristina Pedicchio, and Giuseppe Rosolini, editors, Category Theory 1990, volume 1488 ofLecture Notes in Mathematics, pages 249–261. Springer, 1992

    work page 1990

  51. [51]

    Gregory M. Kelly. Basic concepts of enriched category theory.Reprints in Theory and Applications of Categories, 10:1–136, 2005. 41

    work page 2005

  52. [52]

    Monads on symmetric monoidal closed categories.Archiv der Mathematik, 21:1–10, 1970

    Anders Kock. Monads on symmetric monoidal closed categories.Archiv der Mathematik, 21:1–10, 1970

    work page 1970

  53. [53]

    Bilinearity and cartesian closed monads.Mathematica Scan- dinavica, 29(2):161–174, 1971

    Anders Kock. Bilinearity and cartesian closed monads.Mathematica Scan- dinavica, 29(2):161–174, 1971

    work page 1971

  54. [54]

    Closed categories generated by commutative monads.Jour- nal of the Australian Mathematical Society, 12(4):405–424, 1971

    Anders Kock. Closed categories generated by commutative monads.Jour- nal of the Australian Mathematical Society, 12(4):405–424, 1971

    work page 1971

  55. [55]

    Strong functors and monoidal monads.Archiv der Mathe- matik, 23:113–120, 1972

    Stephen Kock. Strong functors and monoidal monads.Archiv der Mathe- matik, 23:113–120, 1972

    work page 1972

  56. [56]

    Kleene algebra with prod- ucts and iteration theories

    Dexter Kozen and Konstantinos Mamouras. Kleene algebra with prod- ucts and iteration theories. In Simona Ronchi Della Rocca, editor,CSL 2013, volume 23, pages 415–431. Schloss-Dagstuhl-Leibniz Zentrum f¨ ur In- formatik, 2013

    work page 2013

  57. [57]

    Composing props.Theory and Applications of Categories, 13(9):147–163, 2004

    Stephen Lack. Composing props.Theory and Applications of Categories, 13(9):147–163, 2004

    work page 2004

  58. [58]

    Natural associativity and commutativity.Rice Uni- versity Studies, 49:28–46, 1963

    Saunders Mac Lane. Natural associativity and commutativity.Rice Uni- versity Studies, 49:28–46, 1963

    work page 1963

  59. [59]

    Springer, 1998

    Saunders Mac Lane.Categories for the Working Mathematician – Second edition. Springer, 1998

    work page 1998

  60. [60]

    Categorical semantics of linear logic.Panoramas et syntheses, 27:15–215, 2009

    Paul-Andr´ e Mellies. Categorical semantics of linear logic.Panoramas et syntheses, 27:15–215, 2009

    work page 2009

  61. [61]

    E. Moggi. Notions of computation and monads.Information and Compu- tation, 93(1):55–92, 1991

    work page 1991

  62. [62]

    Weak Hopf monoids in braided monoidal categories.Algebra & Number Theory, 3(2):149–207, 2009

    Craig Pastro and Ross Street. Weak Hopf monoids in braided monoidal categories.Algebra & Number Theory, 3(2):149–207, 2009

    work page 2009

  63. [63]

    Categories of partial maps

    Edmund Robinson and Giuseppe Rosolini. Categories of partial maps. Information and Computation, 79(2):95–130, 1988

    work page 1988

  64. [64]

    Robert Rosebrugh and Richard J. Wood. Distributive laws and factoriza- tion.Journal of Pure and Applied Algebra, 175(1-3):327–353, 2002

    work page 2002

  65. [65]

    A survey of graphical languages for monoidal categories

    Peter Selinger. A survey of graphical languages for monoidal categories. In Bob Coecke, editor,New Structures for Physics, volume 813 ofLecture Notes in Physics, pages 289–355. Springer, 2011

    work page 2011

  66. [66]

    Springer, 2000

    Gheorghe S ¸tef˘ anescu.Network algebra. Springer, 2000. 42 Appendix A Basic notions of category theory A.1 Regular and extesive categories Definition A.1.A category with finite limitsCis calledregularif it has co- equalisers of kernel pairs and regular epis are stable under pullbacks. The following is a well known characterisation of regular categories, ...

    work page 2000