A Syntax for Strictly Associative and Unital ∞-Categories

Eric Finster, Alex Rice, Jamie Vicary

TL;DR

This paper introduces a new type theory, CATTsua, that provides a formal syntax for strictly associative and unital $\infty$-categories. This is achieved through a novel "insertion" operation within the type theory's equality relation, which simplifies complex categorical structures and enables more efficient proof construction and verification.

What Problem Does This Paper Address?

Higher categories are fundamental structures in mathematics, computer science, and physics, with applications ranging from type theory to quantum field theory. Working with these structures, especially in proof-relevant settings, often involves managing numerous "witnesses" or coherence laws (like associators and unitors) that demonstrate the equivalence of different ways to compose operations. This can lead to immense proof obligations and make formal verification intractable. While fully strict $\infty$-categories (where all coherence laws are trivial) are too restrictive, and fully weak ones are too complex, the paper aims to find a middle ground: a "semistrict" theory where many coherence laws are trivialized by the system itself, without sacrificing expressivity. Specifically, they focus on making associativity and unitality strict, leaving only interchange laws as potentially non-trivial.

Methods

The core technical contribution is a new computation rule in the definitional equality of their type theory, called "insertion." This rule allows for the simplification of complex terms by "inserting" an argument's structure into a larger structure, effectively merging pasting diagrams and reducing syntactic complexity. This insertion operation is defined via a universal property and is illustrated with diagrams showing how it modifies coherence terms. The authors formalize this as an equational theory and prove that it terminates and has unique normal forms, leading to a decision procedure for equality. They also introduce related operations like "disc removal" and "endo-coherence removal" to further simplify terms. The entire system is implemented in OCaml and formalized in Agda.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Insertion as a Unifying Principle: The "insertion" operation is the key innovation. It allows the type theory to automatically handle the merging of structures, effectively "computing out" many coherence laws without explicit proof terms. This is analogous to how a type checker can simplify expressions without explicit user intervention.
  • Semistrictness via Equality: Instead of defining semistrict $\infty$-categories axiomatically, the paper achieves semistrictness through the definitional equality of their type theory. This means that proofs involving strict associativity and unitality can be written as if they were fully strict, and the type theory's equality relation will automatically verify the necessary coherence laws.
  • Tree Representation for Structure: The paper leverages a correspondence between pasting diagrams (used in higher category theory) and finite planar rooted trees. This tree representation is crucial for defining and reasoning about the insertion operation and other structural properties.
  • Bridging Theory and Practice: The paper not only presents a theoretical framework but also provides an OCaml implementation (CATTsua) and formalizes key results in Agda, demonstrating the practical applicability and rigor of their approach.

Key Results

  • Definition of CATTsua: A type theory is presented that defines strictly associative and unital $\infty$-categories.
  • Insertion Operation: A novel computational rule for definitional equality that simplifies complex coherence terms.
  • Decision Procedure for Equality: The authors prove that their system has terminating and confluent reduction rules, allowing for decidable equality checking.
  • Formalization and Implementation: The core technical results are formalized in Agda, and a working OCaml implementation is provided.
  • Examples: The paper demonstrates the system's power by encoding and simplifying examples like the triangle and pentagon equations of monoidal categories, and a 5-dimensional homotopy called the syllepsis.

Limitations and Future Work

The authors acknowledge that while their system trivializes associativity and unitality, interchange laws remain potentially non-trivial. Future work could explore extending this framework to handle other coherence laws or investigate its application to specific areas like proof assistants for formal verification. The paper also mentions that their approach avoids issues faced by previous attempts to define semistrict higher categories, such as Dolan's critique regarding monoidal closure properties.

Summary updated

BibTeX
@inproceedings{finster2024syntax,
  author = {Eric Finster and Alex Rice and Jamie Vicary},
  title = {{A Syntax for Strictly Associative and Unital ∞-Categories}},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662102},
}
Figure