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.
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.
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