A taxonomy of categories for relations

Technical Summary: A Taxonomy of Categories for Relations

Problem Statement
The study of categories abstracting the structural properties of relations has yielded a diverse and rich body of work over recent decades. However, the proliferation of similar concepts arising from different contexts (e.g., algebraic presentations of term graphs, categorical probability, partial functions, and logic) has led to a fragmented literature. These structures often share fundamental nature but utilize different notations and terminologies (e.g., restriction categories, Markov categories, $p$-categories, and copy/discard categories). This fragmentation makes it challenging to navigate the field and to establish a clear framework connecting these various categorical notions. Furthermore, while it is a known fact that the Kleisli category of a symmetric monoidal monad on a cartesian category is symmetric monoidal, a systematic investigation of how these properties extend to enriched contexts and specific sub-classes of monads (affine, relevant, and $gs$-monoidal) has been lacking.

Methodology
The authors employ a modular approach based on the language of string diagrams to unify and classify these structures. The core methodology involves:

1. Decomposition into Core Axioms: The taxonomy is built upon two fundamental concepts: share categories (equipped with a duplicator $\nabla_X: X \to X \otimes X$) and categories with garbage (equipped with a discharger $!_X: X \to I$).
2. Axiomatic Variation: By varying the requirements for the existence and naturality of these arrows, the authors derive a hierarchy of categories. For instance, requiring naturality for both arrows yields cartesian monoidal categories, while requiring only existence yields $gs$-monoidal categories.
3. Dualization and Enrichment: The framework is extended to dual structures ($cogs$-monoidal categories) and to preorder-enriched contexts (replacing standard categories with 2-categories where 2-cells represent an ordering, such as set-theoretic inclusion).
4. Kleisli Analysis: The paper investigates the Kleisli categories of symmetric monoidal monads (specifically affine, relevant, and $gs$-monoidal monads) over these base categories. It analyzes how the structural properties of the base category (e.g., existence of diagonals or projections) are preserved or transformed in the resulting Kleisli category.

Key Contributions

• Unified Taxonomy: The paper provides a comprehensive diagrammatic taxonomy that organizes "categories for relations" (including Markov, restriction, $gs$-monoidal, and cartesian categories) based on the presence and naturality of duplicators and dischargers.
• Characterization of Known Structures: It establishes precise correspondences between the proposed taxonomy and existing frameworks. Specifically:
  • $gs$-monoidal categories with projections are shown to correspond exactly to Markov categories.
  • $gs$-monoidal categories with diagonals are shown to correspond exactly to cartesian restriction categories.
• Kleisli Category Results: The authors prove that the Kleisli category of a relevant (resp. affine) monad on a category with diagonals (resp. projections) retains those specific structures. Consequently, the Kleisli category of a $gs$-monoidal monad on a cartesian monoidal category is itself cartesian monoidal.
• Enriched Context: The paper extends these results to preorder-enriched categories. It introduces oplax cartesian categories (where arrows are oplax copyable and discardable) and demonstrates that posetal oplax cartesian categories satisfying specific inequalities are equivalent to restriction categories.
• Dual and Bialgebraic Structures: The work defines and analyzes dual structures ($cogs$-monoidal, bigs-monoidal) and explores the interaction between monoid and comonoid structures, identifying conditions for bialgebraic and Frobenius categories.

Results

• Structural Preservation: The paper demonstrates that the property of being a $gs$-monoidal category is preserved under the formation of Kleisli categories for symmetric monoidal monads.
• Specific Preservation:
  • If a base category $C$ has projections (is a Markov category) and $T$ is an affine monad, the Kleisli category $C_T$ has projections.
  • If $C$ has diagonals (is a cartesian restriction category) and $T$ is a relevant monad, $C_T$ has diagonals.
  • If $C$ is cartesian monoidal and $T$ is a $gs$-monoidal monad, $C_T$ is cartesian monoidal.
• Enriched Kleisli Categories: For preorder-enriched $gs$-monoidal categories, if $C$ is oplax cartesian and $T$ is a colax $gs$-monoidal monad, then the Kleisli category $C_T$ is also oplax cartesian.
• Cartesian Bicategories: The paper shows that cartesian bicategories correspond exactly to posetal oplax bicartesian categories that are lax special and lax connected and satisfy a specific inequality. Furthermore, the Kleisli category of a colax $gs$-monoidal monad over a cartesian bicategory is itself a cartesian bicategory.
• Examples: The taxonomy is validated through various examples, including categories of spans, weighted relations (via semiring monads), and categories of sets and partial/total relations.

Significance and Claims
The authors claim that their primary contribution is bringing clarity and organization to a fragmented field by providing a single, modular reference point for these related concepts. By using string diagrams and a minimal set of axioms, they offer an intuitive yet rigorous language for comparing relational notions.

Regarding the Kleisli category analysis, the paper states that the extension of these results to the enriched context (preorder-enriched categories) is, to the best of their knowledge, original. The work aims to serve both experienced researchers by gathering relevant material in one place and newcomers by offering a self-contained introduction. The authors explicitly note that while they briefly mention epi-mono factorization, a systematic comparison with decomposition techniques like distributive laws is outside the scope of this paper, positioning their $gs$-monoidal approach as a distinct, axiomatically simple alternative to double-category-based taxonomies.

The paper concludes by outlining future directions, including the combinatorial presentation of free $gs$-monoidal categories, the extension to traced categories for feedback systems, and further investigations into alternative notions of Markov categories and affine monads in the context of probability theory.