🔢 mathematics

Unbiasing symmetric monoidal categories in Lean

Diese Arbeit stellt eine Formalisierung des Unbiasing-Prozesses symmetrischer monoidaler Kategorien in Lean 4 vor, die durch die Erweiterung zu einem Cat-wertigen Pseudofunktor von Spans endlicher Mengen sowie die Anwendung von Mac Lanes Kohärenzsatz und der Darstellung durch symmetrische Listen realisiert wird.

Ursprüngliche Autoren: Robin Carlier

Veröffentlicht 2026-03-03

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Robin Carlier

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Problem: Die "Reihenfolge"-Falle

Stell dir vor, du hast eine Gruppe von Freunden, und ihr wollt gemeinsam eine Pizza essen.
In der klassischen Mathematik (und in vielen Computerprogrammen) ist das Essen der Pizza oft so geregelt: Du musst zuerst die erste Scheibe mit der zweiten essen, dann das Ergebnis mit der dritten, und so weiter.

(Pizza1 + Pizza2) + Pizza3

Das funktioniert gut, wenn du nur zwei Freunde hast. Aber was, wenn du 100 Freunde hast? Musst du dann wirklich eine riesige Kette von Klammern bilden?

(((Pizza1 + Pizza2) + Pizza3) + ... + Pizza100)

Das ist nicht nur umständlich, sondern auch verwirrend. In der echten Welt ist es egal, in welcher Reihenfolge du die Pizzas zusammenlegst. Eine Pizza ist eine Pizza, egal ob du sie links oder rechts an die andere legst.

In der Mathematik nennt man das symmetrische monoidale Kategorien. Das ist eine Art "Super-Regelwerk", das beschreibt, wie man Dinge (wie Pizzas, Vektoren oder Quantenzustände) zusammenfügt. Das Problem ist: Die Standard-Regeln in Computerprogrammen (wie in der Bibliothek Mathlib für Lean) zwingen uns oft, uns an diese starre Reihenfolge zu halten. Das nennt man "biased" (voreingenommen).

Die Lösung: "Unbiasing" (Die Voreingenommenheit aufheben)

Der Autor dieses Papers, Robin Carlier, hat eine Methode entwickelt, um diese starre Reihenfolge aufzuheben. Er nennt es "Unbiasing".

Stell dir vor, anstatt eine lange Kette von Klammern zu bauen, hast du einen magischen Korb.

Du wirfst einfach alle Pizzas (oder Freunde) in den Korb.
Der Korb weiß automatisch: "Ah, das sind 100 Pizzas. Ich kann sie alle gleichzeitig essen, egal in welcher Reihenfolge."
Er garantiert dir, dass das Ergebnis immer das gleiche ist, egal wie du die Pizzas hineingeworfen hast.

Das Ziel des Papers ist es, dieses "magische Korb-System" in der Sprache des Computers (Lean 4) zu bauen.

Wie haben sie das gemacht? (Die drei Schritte)

Um diesen magischen Korb zu programmieren, mussten die Autoren drei große Hürden überwinden:

1. Die "Symmetrische Liste" (Der Bauplan)

Zuerst mussten sie eine neue Art von Liste erfinden. Eine normale Liste ist wie eine Schlange: Kopf, dann Hals, dann Körper. Wenn du den Kopf mit dem Hals vertauschst, hast du eine andere Liste.
Aber in einer symmetrischen Liste ist es egal, ob du den Kopf links oder rechts hast. Es ist wie ein Haufen Sand. Wenn du zwei Körner Sand vertauschst, ist es immer noch derselbe Haufen.

Die Metapher: Stell dir vor, du hast eine Liste von Namen auf einem Zettel. In einer normalen Liste ist die Reihenfolge wichtig. In einer "symmetrischen Liste" sind die Namen nur in einem Beutel. Wenn du den Beutel schüttelst und die Namen neu sortiert werden, ist es für den Beutel immer noch derselbe Inhalt.
Der Autor hat bewiesen, dass man jede komplizierte Regel, wie man Dinge zusammenfügt, auf diese einfachen "Beutel-Listen" zurückführen kann. Das ist der Kohärenzsatz (Coherence Theorem). Er sagt im Grunde: "Es gibt nur einen korrekten Weg, Dinge zu mischen, wenn man die Reihenfolge ignoriert."

2. Die "Spiegel-Brücke" (Spans und Pseudofunktionen)

Jetzt kommt der tricky Teil. Wie verbindet man diese Beutel-Listen mit der echten Welt der Mathematik?
Stell dir vor, du hast eine Landkarte mit Städten (das sind die Mengen) und Straßen (das sind die Funktionen).

Manchmal willst du von Stadt A nach B gehen.
Manchmal willst du von B nach A.
Manchmal willst du beide Richtungen gleichzeitig betrachten.

Der Autor baut eine Brücke (einen "Span"), die diese Richtungen verbindet. Er zeigt, dass man jede komplexe Operation (wie das Zusammenfügen von 100 Pizzas) als eine Art "Reise" über diese Brücken beschreiben kann.

Die Metapher: Stell dir vor, du hast einen Übersetzer, der nicht nur Wörter übersetzt, sondern ganze Sätze, die in einer anderen Sprache geschrieben sind, aber die gleiche Bedeutung haben. Der Autor baut einen Übersetzer, der sagt: "Wenn du in der Welt der starren Listen (Bias) eine komplizierte Klammer-Formel hast, übersetze ich sie in eine einfache Anweisung für den magischen Korb (Unbias)."

3. Der Beweis: Alles passt zusammen

Der schwierigste Teil war zu beweisen, dass dieser Übersetzer wirklich funktioniert und keine Fehler macht.

Der Autor hat gezeigt, dass wenn man alle möglichen Wege nimmt, um Dinge zu mischen, man am Ende immer beim selben Ergebnis landet.
Er hat genutzt, dass man die "Beutel-Listen" (Symmetric Lists) perfekt mit Permutationen (das Vertauschen von Elementen) in Verbindung bringen kann.
Die Metapher: Es ist wie ein riesiges Puzzle. Der Autor hat bewiesen, dass jedes einzelne Puzzleteil (jede mathematische Regel) exakt in sein Loch passt und dass es keine Lücken oder überlappenden Teile gibt. Wenn du das Puzzle einmal zusammengebaut hast, ist das Bild klar: Die starre Welt der Listen ist nur eine komplizierte Version der einfachen Welt der Beutel.

Warum ist das wichtig?

Warum sollte sich jemand dafür interessieren, wie man Pizzas in einem Computerprogramm mischt?

Für die Mathematik: Es erlaubt Mathematikern, über Dinge zu reden, die sie bisher nur schwer beschreiben konnten. Zum Beispiel: "Was passiert, wenn ich ein Objekt mit sich selbst 1000-mal verbinde?" Mit dem alten System war das eine Albtraum-Formel. Mit dem neuen System ist es einfach: "Nimm den Beutel mit 1000 Objekten."
Für die Zukunft (Höhere Kategorien): Die Mathematik bewegt sich gerade in Richtung "Höherer Kategorien" (wo nicht nur Punkte und Linien, sondern auch Flächen und Volumina als Objekte gelten). Das alte System war dafür zu starr. Das neue "Unbiasing"-System ist der perfekte Klebstoff, um die einfache Mathematik mit dieser komplexen, zukünftigen Mathematik zu verbinden.
Für Computer: Wenn man Beweise in Software (wie Lean) führt, will man nicht jede einzelne Klammer manuell überprüfen. Das neue System erlaubt dem Computer, automatisch zu erkennen: "Ah, die Reihenfolge ist egal, das Ergebnis ist korrekt." Das macht das Beweisen viel schneller und sicherer.

Zusammenfassung in einem Satz

Robin Carlier hat in Lean 4 einen "magischen Korb" programmiert, der es erlaubt, mathematische Objekte in beliebiger Reihenfolge zusammenzufügen, ohne dass man sich um die komplizierte Klammer-Reihenfolge kümmern muss, und hat bewiesen, dass dieser Korb immer genau das richtige Ergebnis liefert – egal wie viele Objekte man hineingibt.

Das ist ein riesiger Schritt, um Computer und Mathematik für die komplexen Probleme von morgen fit zu machen.

1. Problemstellung

Symmetrische monoidale Kategorien sind die kategorientheoretische Verallgemeinerung kommutativer Monoide. Die klassische Definition („biased") basiert auf binären Operationen (Tensorprodukt $\otimes$ ), einem Einheitsobjekt und natürlichen Isomorphismen für Assoziativität ( $\alpha$ ), Einheiten ( $\lambda, \rho$ ) und Symmetrie ( $\beta$ ).

Das Hauptproblem besteht darin, dass viele Anwendungen (z. B. die Bildung freier kommutativer Monoid-Objekte oder Summen über endliche Mengen ohne kanonische Ordnung) eine „unbiased" (voreingenommene) Sichtweise erfordern. Das bedeutet, dass Tensorprodukte und die zugehörigen Kohärenzen für beliebige endliche Arity (nicht nur binär) verfügbar und wohldefiniert sein müssen.
In der klassischen Definition ist die Gleichheit von Objekten eine Eigenschaft, die unter Äquivalenzen von Kategorien nicht invariant ist; stattdessen werden Isomorphismen als Struktur eingeführt. Um von binären zu $n$ -ären Operationen zu gelangen, muss man zeigen, dass alle möglichen Wege, eine $n$ -fache Tensorierung zu assoziieren und zu permutieren, durch eindeutige „kanonische" Isomorphismen verbunden sind. Dies ist der Inhalt des berühmten Kohärenzsatzes von Mac Lane.

In der formalisierten Mathematik (insbesondere in der Bibliothek Mathlib für den Lean 4 Proof Assistant) war bisher nur die klassische, voreingenommene Definition vorhanden. Dies erschwerte komplexe Konstruktionen und die Verbindung zu höheren Kategorien (z. B. $(\infty, 1)$ -Kategorien), bei denen die „unbiased" Perspektive essenziell ist.

2. Methodik

Der Autor formalisiert den Prozess des „Unbiasings" durch eine Kombination aus kategorientheoretischen Konstruktionen und einer formalen Implementierung in Lean 4. Die Methodik gliedert sich in drei Hauptschritte:

A. Formalisierung des Kohärenzsatzes mittels „Symmetric Lists"

Anstatt den Kohärenzsatz direkt über Diagramme in der Kategorie zu beweisen, wird eine kombinatorische Darstellung gewählt:

Symmetric Lists: Es wird die Kategorie der symmetrischen Listen $SList(J)$ über einer Menge $J$ definiert. Objekte sind Listen von Elementen aus $J$ , Morphismen werden durch Generatoren (Vertauschungen benachbarter Elemente swap) und Relationen (Symmetrie, Hexagon-Relation, Natürlichkeit) erzeugt.
Verbindung zu Coxeter-Gruppen: Die Morphismen in $SList(J)$ werden mit Permutationen identifiziert. Der Autor formalisiert die Darstellung der symmetrischen Gruppe $\Sigma_n$ als Coxeter-Gruppe vom Typ $A_{n-1}$ .
Gewichtung (Weighting): Morphismen werden mit Elementen der unendlichen Coxeter-Gruppe $A_\infty$ gewichtet. Es wird bewiesen, dass diese Gewichtung treu ist (injektiv): Zwei Morphismen sind genau dann gleich, wenn sie dieselbe Permutation (bzw. dasselbe Gruppenelement) repräsentieren.
Äquivalenz: Es wird gezeigt, dass $SList(J)$ äquivalent zur freien symmetrischen monoidalen Kategorie über $J$ ist.

B. Spans und Pseudofunktoren

Um die „unbiased" Struktur zu kodieren, wird die Kategorie der Spans (Spannungen) endlicher Mengen verwendet.

Span-Bicategories: Eine Span ist ein Diagramm $A \leftarrow S \to B$ . Die Kategorie $Span(Fin)$ wird als Bicategory formalisiert.
Pith: Es wird das „Pith" der Bicategory betrachtet, d. h. die Sub-Bicategory, in der nur invertierbare 2-Morphismen (Isomorphismen von Spans) erlaubt sind.
Pith-Beck-Chevalley-Systeme: Um einen Pseudofunktor von $Pith(Span(Fin))$ zu definieren, wird ein System aus zwei Pseudofunktoren (einem kovarianten und einem kontravarianten) sowie Isomorphismen für Pullback-Quadrate (Base-Change-Isomorphismen) definiert. Dies ermöglicht die Konstruktion eines Pseudofunktors, der eine Span auf einen Funktor zwischen Produktkategorien abbildet.

C. Kleisli-Bicategory und Universalität

Die universellen Formeln der symmetrischen monoidalen Kategorien werden in einer Kleisli-Bicategory $K_{SList}$ kodiert.

Objekte sind Mengen.
Morphismen $J \to K$ sind Familien von symmetrischen Listen über $K$ , indiziert durch $J$ .
Ein symmetrisches monoidales Kategorie $\mathcal{C}$ wird als Cat-wertiger Pseudofunktor von $(K_{SList})^{op}$ nach $Cat$ interpretiert (eine Art Yoneda-Einbettung für Pseudoalgebren).
Der „Unbiasing"-Prozess besteht darin, einen Pseudofunktor $\Lambda: Pith(Span(Fin)) \to K_{SList}^{op}$ zu konstruieren. Die Komposition dieses $\Lambda$ mit dem Pseudofunktor für $\mathcal{C}$ liefert das gewünschte „unbiased" Tensorprodukt.

3. Schlüsselbeiträge

Erste mechanisierte Beweise: Dies ist der erste formalisierte Beweis in Lean, dass eine symmetrische monoidale Kategorie (im klassischen Sinne) einen Pseudofunktor von $Pith(Span(Fin))$ nach $Cat$ definiert (Theorem 1.1).
Formalisierung von Symmetric Lists: Die vollständige Implementierung der Kategorie der symmetrischen Listen in Mathlib, einschließlich der Anpassung von Piceghellos Arbeit aus dem Homotopy Type Theory (HoTT) Kontext in die nicht-HoTT-Umgebung von Lean. Dies beinhaltet die explizite Identifikation von Morphismen mit Permutationen via Coxeter-Gruppen.
Pith-Beck-Chevalley-Systeme: Die Definition und Formalisierung einer neuen Struktur, die es erlaubt, Pseudofunktoren aus dem Pith von Span-Bicategories zu konstruieren, ohne auf Adjunktionen im vollen Sinne zurückgreifen zu müssen (da diese im Pith oft nicht existieren).
Dualität und Multisets: Die Einführung eines Dualitätsfunktors für symmetrische Listen und die Nutzung von Multisets (als Isomorphieklassen von Listen) zur Vereinfachung von Berechnungen. Der Beweis, dass für „lineare" Listen (ohne Duplikate) Morphismen eindeutig sind, erlaubt die Automatisierung vieler Gleichheitsbeweise.

4. Ergebnisse

Theorem 1.1: Für jede symmetrische monoidale Kategorie $\mathcal{C}$ $C$ existiert ein Pseudofunktor $\mathcal{C}^\otimes: Pith(Span(Fin)) \to Cat$ $C^{\otimes} : P i t h (S p an (F in)) \to C a t$ . Dieser sendet eine endliche Menge $J$ $J$ auf die Produktkategorie $\mathcal{C}^J$ $C^{J}$ und eine Span $A \xleftarrow{f} S \xrightarrow{g} B$ $A f S g B$ auf den Funktor $g_! f^*$ $g_{!} f^{*}$ .
- $f^*$ ist die Präkomposition (Ziehen von Indizes).
- $g_!$ ist die „Tensorierung über Fasern": Ein $A$ -indizierter Familien wird auf eine $B$ -indizierte Familie abgebildet, wobei die Elemente über $g^{-1}(\{b\})$ tensorisiert werden.
Theorem 1.3 (Kohärenz): Die freie symmetrische monoidale Kategorie über einer Menge $J$ ist äquivalent zur Kategorie der endlichen Mengen über $J$ mit Bijektionen, ausgestattet mit der symmetrischen monoidalen Struktur der disjunkten Vereinigung.
Automatisierung: Durch die Nutzung der Subsingleton-Eigenschaft für lineare Listen (Listen ohne Duplikate) können viele Gleichheitsbeweise in Lean automatisch durch den subsingleton-Taktik geschlossen werden, da zwischen solchen Objekten höchstens ein Morphismus existiert.

5. Bedeutung und Ausblick

Brücke zur höheren Kategorientheorie: Die Arbeit liefert das notwendige „Klebeband", um klassische Kategorien in Mathlib als Objekte in der Theorie der $(\infty, 1)$ -Kategorien zu interpretieren. Die Verwendung von Spans und Pseudofunktoren entspricht den Modellen für symmetrische monoidale $(\infty, 1)$ -Kategorien (z. B. Lawvere-Strukturen).
Erweiterte Algebra: Die unbiasing-Technik ermöglicht die formale Definition von Tensorpotenzen $X^{\otimes n}$ als Funktoren, die mit der symmetrischen Gruppe $\Sigma_n$ interagieren, sowie die Behandlung freier kommutativer Monoid-Objekte in beliebigen symmetrischen monoidalen Kategorien.
Mathlib-Erweiterung: Die Ergebnisse werden schrittweise in die Mathlib-Bibliothek integriert. Dies erfordert die Erweiterung der Bicategory-Infrastruktur (z. B. Biequivalenzen, Produkte in Bicategories), um die volle Äquivalenz zwischen der Kategorie der Pseudofunktoren und der Kategorie der symmetrischen monoidalen Kategorien zu formalisieren.

Zusammenfassend stellt diese Arbeit einen Meilenstein in der formalisierten Kategorientheorie dar, indem sie die Lücke zwischen der klassischen, binären Definition symmetrischer monoidaler Kategorien und der modernen, unvoreingenommenen Sichtweise schließt, die für fortgeschrittene algebraische Konstruktionen und höhere Kategorientheorie unerlässlich ist.