🔢 mathematics

Unbiasing symmetric monoidal categories in Lean

This paper presents a Lean 4 formalization within Mathlib that unbias symmetric monoidal categories by extending their data to a Cat-valued pseudofunctor over spans of finite sets, leveraging Mac Lane's coherence theorem and a Kleisli bicategory encoding to handle higher-arity tensor products and their coherences.

Original authors: Robin Carlier

Published 2026-03-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Robin Carlier

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef in a very busy kitchen. You have a recipe that says, "Mix ingredients A and B." That's easy. But what if the recipe says, "Mix ingredients A, B, C, D, and E"?

In the world of standard cooking (or standard mathematics), you usually have to figure out the order. Do you mix A and B first, then add C? Or do you mix C and D, then add that to A and B? In a normal kitchen, the order matters for the process, even if the final taste is the same.

This paper is about building a new, super-smart kitchen assistant (written in a computer language called Lean 4) that understands a fundamental rule: When you are mixing things that are perfectly symmetric, the order you do it in doesn't actually matter, as long as you get the right ingredients in the bowl.

Here is the breakdown of the paper's big ideas using simple analogies:

1. The Problem: The "Biased" Recipe

In traditional math (and early versions of the Lean library), a "Symmetric Monoidal Category" is like a recipe that only knows how to mix two things at a time.

If you want to mix 5 things, the computer forces you to write it as ((A + B) + C) + (D + E).
It has to prove that ((A + B) + C) is the same as (A + (B + C)).
It has to prove that swapping A and B doesn't change the result.

This is called being "biased." The computer is obsessed with the specific order of operations. It's like a robot chef that refuses to make a salad unless you tell it exactly which two leaves to toss together first, then which two to toss next. It works, but it's tedious and hard to scale up to huge recipes.

2. The Solution: The "Unbiased" Kitchen

The authors wanted to build a system where the computer understands unbiased mixing. They wanted to say, "Here is a list of 100 ingredients. Just mix them all together." The computer should know that no matter how you group them, the result is the same.

To do this, they didn't just change the recipe; they changed the language the robot speaks.

3. The Magic Tool: "Symmetric Lists"

The authors invented a way to represent a mix of ingredients not as a long chain of parentheses, but as a "Symmetric List."

The Old Way: A long, messy string of instructions: (((A+B)+C)+D)...
The New Way: A bag of ingredients where the order doesn't matter, but the count does.

They proved a famous mathematical idea (Mac Lane's Coherence Theorem) using a clever trick: Symmetric Lists are just Permutations.
Think of it like shuffling a deck of cards.

If you have a list of cards [A, B, C], you can shuffle them to get [B, A, C].
The authors showed that every possible way to rearrange your ingredients (every "shuffle") corresponds to a specific, unique mathematical move.
They built a computer model where every "shuffle" is labeled with a unique ID. If two different paths of mixing ingredients lead to the same final shuffle, the computer knows they are the same result.

4. The Bridge: Spans and Bridges

The paper uses a concept called "Spans." Imagine you have two islands (Set A and Set B). A "Span" is a bridge connecting them through a third island (Set C).

To get from A to B, you go A → C → B.
The authors showed that you can treat these bridges as a universal language. They built a system where "mixing ingredients" is just a special kind of bridge crossing.

They created a Pseudofunctor (a fancy word for a "translator") that takes the messy, biased world of standard math and translates it into this clean, unbiased world of "Spans" and "Symmetric Lists."

5. Why Does This Matter? (The "Why Should I Care?")

You might ask, "Why do we need a robot chef that can mix 100 things at once?"

Complex Formulas: In advanced physics and group theory, there are formulas that sum up thousands of terms. Doing this with the "old" method requires proving thousands of tiny steps about order. The "new" method lets the computer just say, "Sum these 1,000 items," and it knows it's valid.
Future-Proofing: The authors are preparing for the future of mathematics, which involves "Higher Categories" (math that deals with shapes and spaces, not just numbers). The "biased" way of doing things breaks down in these higher dimensions. The "unbiased" way they built is the only way to scale up to these complex, multi-dimensional math problems.
Trust: By writing this in Lean 4, they didn't just say it works; they forced the computer to check every single logical step. If there was a hole in their logic, the computer would have refused to compile the code.

The Bottom Line

This paper is about liberating mathematics from the tyranny of order.

The authors built a digital framework that allows computers to understand that when you are dealing with symmetric things (like mixing a salad or adding numbers), the specific sequence of "first this, then that" is an illusion. The result is a robust, "unbiased" system that can handle complex, large-scale mathematical structures that were previously too messy for computers to handle reliably.

It's like upgrading from a calculator that only knows how to add two numbers at a time, to a super-computer that understands the concept of "a pile of numbers" and can sum them all instantly, regardless of how you arranged them on the table.

1. Problem Statement

In formalized mathematics (specifically within the Lean 4 proof assistant and the Mathlib library), the standard definition of a symmetric monoidal category is "biased." It is defined using only binary tensor products ( $\otimes$ ), a unit object ($1$), and specific coherence isomorphisms (associators, unitors, and braidings) for these low-arity operations.

While this definition is minimal and easy to construct, it creates significant obstacles for advanced mathematical applications:

Higher Arity Operations: Many mathematical constructions (e.g., free commutative monoids, tensor powers $x^{\otimes n}$ , or sums over arbitrary finite sets) require a canonical way to define tensor products of $n$ objects for arbitrary $n$ , independent of how the objects are parenthesized or ordered.
Higher Category Theory: Theories of $(\infty, 1)$ -categories (such as Lurie's $\infty$ -operads or Cranch's Lawvere symmetric monoidal categories) treat symmetric monoidal structures as pseudofunctors from a source category containing all finite sets and their symmetries. The current "biased" definition in Mathlib does not naturally scale to these higher-categorical frameworks.
The "Unbiasing" Gap: There is a lack of a formalized bridge that takes a standard biased symmetric monoidal category and constructs an "unbiased" version (a pseudofunctor encoding all finite tensor products and their coherences) within the Lean ecosystem.

2. Methodology

The author addresses this by formalizing the unbiasing process in Lean 4, relying on Mac Lane's Coherence Theorem. The methodology proceeds in three main stages:

A. Formalizing the Coherence Theorem via Symmetric Lists

To prove that the biased definition implies the existence of a unique canonical isomorphism for any higher-arity tensor product, the author formalizes the free symmetric monoidal category.

Symmetric Lists ($SList$): Instead of using the standard inductive definition of free monoidal categories (which struggles with braiding), the author adapts Piceghello's work (originally in Homotopy Type Theory) to Mathlib. They define a category of symmetric lists, where objects are lists of elements and morphisms are generated by "swaps" ( $sw_{a,b,l}$ ) subject to relations mimicking the symmetric group (Coxeter group relations).
Coxeter Group Encoding: A key technical contribution is proving that morphisms in $SList$ correspond bijectively to permutations. The author formalizes the link between the generators of the symmetric list category and the Coxeter group $A_\infty$ , proving that the "weight" (label) of a morphism uniquely determines it.
Equivalence: They prove that the category of symmetric lists on a set $J$ is equivalent to the free symmetric monoidal category on $J$ . This provides a concrete, computable model for the "unbiased" structure.

B. Span Bicategories and Pseudofunctors

The target structure for the unbiased category is a pseudofunctor from the pith of the bicategory of spans of finite sets ($Pith(Span(Fin))$) to the category of categories ($Cat$).

Span Bicategories: The author formalizes the bicategory of spans, where 1-morphisms are spans $A \leftarrow S \to B$ and 2-morphisms are morphisms between apices.
Pith-Beck-Chevalley Systems: Since the functors involved in the unbiasing (tensor products and pullbacks) are not adjoint in the standard sense required for full span bicategories, the author introduces a specific structure called a Pith-Beck-Chevalley system. This structure consists of two pseudofunctors (one covariant, one contravariant) and a family of base-change isomorphisms for pullback squares.
Theorem 3.3: The paper proves that any such system uniquely extends to a pseudofunctor out of the pith of the span bicategory.

C. The Kleisli Bicategory and Duality

To connect the span bicategory to the symmetric monoidal category:

Kleisli Bicategory ( $K_{SList}$ ): The author defines a Kleisli bicategory for the relative pseudomonad of symmetric lists. This allows encoding universal formulas of symmetric monoidal categories.
Duality Functor: A crucial step is constructing a duality functor $D_{J,K}$ that transposes vectors of symmetric lists. This is interpreted as a matrix transposition where the "entries" are finite sets (or symmetric lists).
Linear Symmetric Lists: The author introduces the concept of "linear" symmetric lists (lists with no duplicate elements). They prove that between linear lists, morphisms are unique (subsingleton). This property is used to automate proofs of commutativity for the base-change isomorphisms, as any two isomorphisms between linear lists must be equal.

3. Key Contributions

Formalization of Mac Lane's Coherence Theorem: A complete formalization in Lean 4 of the theorem stating that the free symmetric monoidal category on a set is equivalent to the category of symmetric lists. This includes a novel proof that morphisms in this category are in bijection with permutations via Coxeter group weights.
Unbiasing Construction: The construction of a pseudofunctor $\mathcal{C}^\otimes: Pith(Span(Fin)) \to Cat$ from any given symmetric monoidal category $\mathcal{C}$ . This functor maps a finite set $J$ to the product category $\mathcal{C}^J$ and a span to a functor that computes tensor products over fibers.
Pith-Beck-Chevalley System: The definition and formalization of a new structural tool (Theorem 3.3) to generate pseudofunctors from the pith of span bicategories, which is necessary because the standard adjunctions do not lift to the pith in the required way.
Matrix-like Computations: The use of multiset arithmetic and "linear" lists to simplify the verification of complex coherence diagrams. By reducing coherence checks to properties of multisets (where duplicates are handled by symmetry groups), the author leverages Lean's automation tactics (simp, subsingleton) to discharge tedious proof obligations.

4. Main Results

Theorem 1.1 (Unbiasing): For any symmetric monoidal category $\mathcal{C}$ , there exists a pseudofunctor from the pith of the span bicategory of finite sets to $Cat$ that encodes the tensor product of arbitrary finite families of objects. This realizes $\mathcal{C}$ as a Lawvere symmetric monoidal $(\infty, 1)$ -category (in the ordinary categorical sense).
Theorem 1.3 (Coherence): The free symmetric monoidal category on a set $J$ is equivalent to the category of symmetric lists on $J$ (formalized as $Core(Fin/J)$).
Corollary 2.9: A precise characterization of morphisms in the category of symmetric lists as bijections of indices that respect the underlying elements, establishing the link between the algebraic structure and permutations.

5. Significance

Mathematical Library (Mathlib): This work provides the first mechanized proof of the unbiasing of symmetric monoidal categories. It lays the necessary groundwork for formalizing advanced algebraic structures in Mathlib, such as free commutative monoid objects and symmetric tensor powers ( $x^{\otimes n}$ ).
Bridge to Higher Categories: The construction aligns the classical definition of symmetric monoidal categories with the modern $(\infty, 1)$ -categorical perspective (specifically Cranch's Lawvere approach). This is a prerequisite for integrating higher category theory into Mathlib, as it allows ordinary categories to be reinterpreted as their higher-categorical counterparts.
Proof Engineering: The paper demonstrates sophisticated techniques for handling "DTT Hell" (dependent type theory difficulties with object equality) by using definitional equalities carefully and leveraging the subsingleton tactic for coherence proofs. It serves as a blueprint for formalizing complex pseudoalgebraic structures.

In summary, Carlier's work transforms the "biased" definition of symmetric monoidal categories into a robust, "unbiased" framework within Lean, enabling the formalization of higher-arity operations and bridging the gap between classical category theory and modern higher-categorical models.