Strictly Associative and Unital $\infty$-Categories as a Generalized Algebraic Theory

Eric Finster, Alex Rice, Jamie Vicary

Introduction

In the study of higher category theory ($\infty$-categories), the "weakness" of fundamental laws like associativity and unitality introduces significant formal complexity. In a weak $\infty$-category, an equality such as $(f \circ g) \circ h = f \circ (g \circ h)$ does not hold strictly; instead, it requires a "witness" or associator to show equivalence. These witnesses then require their own higher-dimensional witnesses (e.g., the pentagon equation), leading to an exponential explosion of data that complicates formal proofs.

This paper introduces CATT_sua, a novel type theory that provides the first formal definition of strictly associative and unital $\infty$-categories. By implementing a new "insertion" rule for definitional equality, the authors provide a system that automatically trivializes this "bureaucracy," turning complex associator and unitor witnesses into simple identities while preserving the necessary weakness of interchangers.

The CATT_sua Framework

The authors define CATT_sua as a Generalized Algebraic Theory (GAT). The theory manages contexts ($\text{Ctx}$), types ($\text{Type}_\Gamma$), and terms ($\text{Term}_\Gamma$) through a set of formal inference rules. This structure allows the system to represent "pasting diagrams"—the shapes of higher-dimensional compositions—as finite planar rooted trees.

Inference rules for the CATT_sua type theory

By formalizing these rules, the authors ensure that the theory is grounded in a rigorous logical framework suitable for implementation in proof assistants like Agda.

The Insertion Rule and Normalization

The primary innovation of CATT_sua is the insertion rule, a form of "syntactic surgery" for definitional equality. If a compound operation contains an argument that is itself a standard coherence, the insertion rule allows the system to "merge" the inner tree structure into the outer tree.

The insertion operation on tree-based contexts

This operation satisfies a formal universal property (a pushout) in the category of contexts. To ensure the system is practical, the authors prove that the reduction relation—combining insertion with "disc removal" and "endo-coherence removal"—is both terminating and confluent. This means every term has a unique "normal form," making equality decidable. The termination proof notably utilizes Cantor normal forms of ordinals up to $\omega^\omega$ to show that even when insertion appears to increase term size, it reduces underlying syntactic complexity.

Key Results and Applications

The implementation of CATT_sua in OCaml and its formalization in Agda yield several significant results:

  • Automated Simplification: Classic requirements of weak category theory, such as the triangle and pentagon equations, normalize completely to identities. This allows users to write proofs without manually managing these witnesses.
  • The Syllepsis: The authors successfully encoded the syllepsis—a complex 5-dimensional homotopy—in a significantly shorter and cleaner form than was possible in previous fully weak models.
  • Decidability: The theory provides a concrete decision procedure for equality. If two compositions are equivalent under strict associativity and unitality, the algorithm can prove it automatically.

Conclusion and Future Work

CATT_sua represents a major step toward practical formalization of higher category theory. By automating the management of associators and unitors, it strikes a balance between the expressivity of weak theories and the efficiency of strict ones. Future work includes integrating these semistrict tactics into mainstream proof assistants like Coq or Lean and extending the theory beyond contractible $\infty$-categories to more general categorical structures.

Summary updated

Abstract

We present the first definition of strictly associative and unital $\infty$-category. Our proposal takes the form of a type theory whose terms describe the operations of such structures, and whose definitional equality relation enforces desired strictness conditions. The key technical device is a new computation rule in the definitional equality of the theory, which we call insertion, defined in terms of a universal property. On terms for which it is defined, this operation "inserts" one of the arguments of a substituted coherence into the coherence itself, appropriately modifying the pasting diagram and result type, and simplifying the syntax in the process. We generate an equational theory from this reduction relation and we study its properties in detail, showing that it yields a decision procedure for equality. Expressed as a type theory, our model is well-adapted for generating and verifying efficient proofs of higher categorical statements. We illustrate this via an OCaml implementation, and give a number of examples, including a short encoding of the syllepsis, a 5-dimensional homotopy that plays an important role in the homotopy groups of spheres.
BibTeX
@inproceedings{finster2024strictly,
  author = {Eric Finster and Alex Rice and Jamie Vicary},
  title = {{Strictly Associative and Unital $\textbackslash\{\}infty$-Categories as a Generalized Algebraic Theory}},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662102},
}
Figure