Presenting a Category Modulo a Rewriting System

Florence Clerc, Samuel MimramRTA 2015 · OpenReview

TL;DR

This paper introduces a new way to "present" categories, which are fundamental structures in mathematics. They generalize existing methods to handle situations where objects themselves can be considered equivalent under certain rules, akin to "rewriting modulo" an equational theory. The key contribution is showing that three seemingly different ways of constructing such a category—using normal forms, quotients, or localizations—coincide under specific coherence conditions, generalizing known results for groups.

What Problem Does This Paper Address?

In mathematics, especially in category theory, we often want to describe complex structures (like categories) in a simpler way using generators and relations. This is called a "presentation." However, traditional presentations only allow relations between morphisms (arrows), not between objects (the points or nodes). This limitation makes it difficult to present categories where the objects themselves are subject to equivalence relations, such as those arising from rewriting systems. For example, presenting the monoidal category $A \times A$ (where $A$ is the simplicial category) is tricky because its objects form the monoid $\mathbb{N} \times \mathbb{N}$, which isn't free, and requires relations between objects (like $a \cdot b = b \cdot a$). This paper tackles this by extending the notion of category presentations to "modulo a rewriting system," allowing for relations on objects.

Methods

The core of the paper is defining and exploring "presentations modulo." This involves:

  • Presentations Modulo: A standard category presentation $(P_0, P_1, P_2)$ (objects, morphisms, relations) is augmented with a set $P_1 \subseteq P_1$ of "equational generators." These generators define an equivalence relation on objects.
  • Three Constructions: For a given presentation modulo, three ways to construct the intended category are explored:
  • Normal Forms: Restricting to objects that are "normal forms" with respect to the equational generators.
  • Quotient Category: Forcing the equational generators to become identities.
  • Localization: Forcing the equational generators to become isomorphisms.
  • Coherence Conditions: The authors introduce a series of "coherence conditions" on the presentation and the rewriting system defined by $P_1$. These include:
  • Residuation: A way to track "remaining" parts of morphisms after applying rewriting rules, generalizing concepts from confluent rewriting systems.
  • Cylinder Property: Ensuring that residuals are compatible with composition and relations.
  • Weight Functions: Used to prove termination of rewriting systems.
  • Equivalence Proofs: The main technical contribution is proving that under these coherence conditions, the three constructions (normal forms, quotient, localization) yield equivalent categories. This is achieved by defining functors between them and proving they are equivalences of categories.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and uses abstract examples rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Unifying Framework: The paper provides a unified framework for presenting categories where objects can be identified via rewriting rules. This bridges the gap between standard category presentations and algebraic structures like monoids with relations on their generators.
  • Equivalence of Constructions: The most significant insight is demonstrating that for "coherent" presentations modulo, the seemingly different approaches of using normal forms, quotients, and localizations all lead to the same categorical structure. This is a powerful generalization of similar results in group theory.
  • Generalization of Rewriting: The work extends the idea of "rewriting modulo" from term rewriting systems to the categorical setting, allowing for abstract rewriting on objects.
  • Foundation for Higher Categories: The authors explicitly state that this work is a stepping stone towards generalizing these ideas to 2-categories and higher, which is a complex but important area of research.

Key Results

  • Theorem 28: The category of normal forms is isomorphic to the quotient category.
  • Theorem 32: For a "coherent" presentation modulo, the quotient category is equivalent to the localization.
  • Proposition 30: Under certain conditions, the inclusion of the original category into its localization is faithful.
  • Example (Dihedral Category): The paper illustrates the techniques with a non-trivial example of the dihedral category $D_n$, showing how to transform a presentation into one that satisfies the coherence conditions, leading to a concrete result about $D_2$.

Limitations and Future Work

  • Coherence Conditions: The main limitation is the need for specific "coherence conditions" for the equivalence of the three constructions to hold. These conditions ensure the rewriting systems are well-behaved (e.g., confluent, terminating). Finding presentations that satisfy these can be challenging.
  • Extension to 2-Categories: The authors explicitly state that extending this framework to 2-categories (and higher) is a significant area for future work. This involves dealing with exchange laws and the subtleties of 2-categorical composition.
  • Applications: While an example is provided, exploring more applications of this presentation method to various algebraic structures and categories would be valuable.
  • Practical Computations: The paper lays theoretical groundwork. Future work could focus on developing algorithms for constructing these presentations and performing computations within the resulting categories.

Summary updated

Abstract

Presentations of categories are a well-known algebraic tool to provide descriptions of categories by the means of generators, for objects and morphisms, and relations on morphisms. We generalize here this notion, in order to consider situations where the objects are considered modulo an equivalence relation (in the spirit of rewriting modulo), which is described by equational generators. When those form a convergent (abstract) rewriting system on objects, there are three very natural constructions that can be used to define the category which is described by the presentation: one is based on restricting to objects which are normal forms, one consists in turning equational generators into identities (i.e. considering a quotient category), and one consists in formally adding inverses to equational generators (i.e. localizing the category). We show that, under suitable coherence conditions on the presentation, the three constructions coincide, thus generalizing celebrated results on presentations of groups. We illustrate our techniques on a non-trivial example, and hint at a generalization for 2-categories.
BibTeX
@inproceedings{clerc2015presenting,
  author = {Florence Clerc and Samuel Mimram},
  title = {{Presenting a Category Modulo a Rewriting System}},
  booktitle = {RTA},
  year = {2015},
  url = {https://openreview.net/forum?id=Q0-59JuitE},
}

Loading related content...

Figure