Terminal Coalgebras and Non-wellfounded Sets in Homotopy Type Theory

Das große Ganze: Den Aufbau eines Universums aus „rotierenden“ Mengen

Stellen Sie sich vor, Sie bauen ein Universum von Objekten (Mengen). Auf die traditionelle Art der Mathematik (die sogenannte „wohlgefundene“ Mengenlehre) wird jedes Objekt aus kleineren Objekten aufgebaut, die wiederum aus noch kleineren Objekten bestehen, und so weiter, bis hin zu nichts. Es ist wie eine Pyramide: Man kann keinen Block in der Luft schweben lassen; er muss auf etwas darunter ruhen.

Aber was wäre, wenn Sie ein Universum bauen wollten, in dem Dinge auf sich selbst ruhen können? Was wäre, wenn Sie eine Box hätten, die sich selbst enthält? Oder eine Kette von Boxen, bei der Box A in Box B liegt, Box B in Box C liegt und Box C wiederum in Box A liegt? In der traditionellen Mathematik ist dies verboten, da es eine unendliche Schleife erzeugt. In dieser Arbeit untersuchen die Autoren, wie man ein mathematisches Universum aufbauen kann, das solche Schleifen erlaubt, indem sie ein modernes Framework namens Homotopietheorie (HoTT) verwenden.

Die Arbeit tut zwei Dinge:

1. Sie baut ein Modell von Mengen auf, das Schleifen erlaubt, und folgt dabei den Regeln eines Mathematikers namens Scott.
2. Sie baut ein anderes Modell von Mengen auf, das Schleifen erlaubt, und folgt dabei den Regeln eines Mathematikers namens Aczel.

Die Werkzeuge: Bäume, Koalgebren und das „Entfalten“

Um ihre Modelle zu verstehen, stellen Sie sich einen Baum vor.

• Wohlgefundene Bäume (der alte Weg) sind wie Stammbäume. Sie haben eine Wurzel, Äste und enden schließlich in Blättern. Sie hören auf zu wachsen.
• Nicht-wohlgefundene Bäume (der neue Weg) können wie ein Fraktal oder ein Spiegelkabinett sein. Ein Ast kann zurückschleifen und wieder zur Wurzel werden. Oder ein Ast kann sich in zwei identische Äste aufspalten, die exakt wie der gesamte Baum aussehen.

Die Autoren verwenden ein Konzept namens Koalgebra, um diese Bäume zu beschreiben. Betrachten Sie eine Koalgebra als eine „Maschine“, die Ihnen sagt, wie Sie einen Knoten betrachten und sehen, was als Nächstes kommt.

• Wenn die Maschine „stopp“ sagt, haben Sie ein Blatt.
• Wenn die Maschine sagt „gehe zu diesen Kindern“, haben Sie Äste.
• Wenn die Maschine sagt „gehe zu einem Kind, das eigentlich du selbst bist“, haben Sie eine Schleife.

Die Arbeit stellt die Frage: Was ist die „ultimative“ Maschine, die alle möglichen Schleifen beschreiben kann?

Die zwei Modelle: Scott vs. Aczel

Die Autoren konstruieren zwei verschiedene „ultimative Maschinen“ (mathematische Modelle), um diese Schleifen zu handhaben. Diese entsprechen zwei verschiedenen Philosophien darüber, wie Gleichheit in diesen kreisenden Welten zu behandeln ist.

1. Das „Spiegel“-Modell (Scotts Anti-Fundationsaxiom)

• Die Analogie: Stellen Sie sich ein Spiegelkabinett vor. Wenn Sie vor einem Spiegel stehen, sehen Sie eine Reflexion. Wenn diese Reflexion in einem anderen Spiegel ist, sehen Sie eine Reflexion einer Reflexion.
• Die Regel: In diesem Modell gelten zwei Objekte als „gleich“, wenn ihre Entfaltungsmuster gleich aussehen. Wenn man die Schichten einer Menge immer weiter entfaltet (wie beim Schälen einer Zwiebel oder beim Entfalten eines Baumes), und das Muster der Verzweigungen identisch mit dem einer anderen Menge ist, dann sind sie dieselbe.
• Das Ergebnis: Die Autoren bauten eine spezifische Art von Baumstruktur (genannt $V^0_\infty$), die als dieses Modell fungiert. Es ist ein „Fixpunkt“, was bedeutet, dass, wenn man die Regeln des Universums auf es anwendet, man dasselbe Universum zurückerhält.
• Wichtigste Erkenntnis: Dieses Modell ist nicht die „finale“ oder „terminale“ Maschine im strengsten Sinne. Es ist eine „dritte Option“ – es ist weder der Ausgangspunkt (initial) noch der absolute Endpunkt (terminal). Es steht dazwischen. Es erfüllt Scotts Regeln, die strenger bei der Identifizierung von Schleifen sind.

2. Das „Universelle“ Modell (Aczels Anti-Fundationsaxiom)

• Die Analogie: Stellen Sie sich einen Meisterkatalog aller möglichen Geschichten vor, einschließlich jener Geschichten, die sich selbst erzählen.
• Die Regel: In diesem Modell kann jeder Graph (ein Bild aus Punkten und Linien) in eine Menge verwandelt werden. Wenn Sie ein Bild einer Schleife haben, gibt es eine eindeutige Menge, die dieses Bild perfekt widerspricht.
• Das Ergebnis: Die Autoren konstruierten eine „terminale Koalgebra“ (die ultimative Maschine) für diesen Zweck. Um jedoch diese spezifische Maschine zu bauen, mussten sie ein spezielles, etwas kontroverses mathematisches Werkzeug namens Propositional Resizing verwenden.
  • Was ist Propositional Resizing? Stellen Sie sich vor, Sie haben eine riesige Bibliothek von Büchern (Propositionen). Dieses Werkzeug erlaubt es Ihnen, die gesamte Bibliothek so zusammenzuschrumpfen, dass sie auf ein einziges Regal passt, ohne die Geschichten zu verlieren. Es ist eine mächtige Abkürzung, die die Konstruktion möglich macht.
• Wichtigste Erkenntnis: Dieses Modell erfüllt Aczels Regeln. Es ist das „terminale“ Objekt, was bedeutet, dass es die vollständigste Version eines kreisenden Mengenuniversums unter diesen Regeln ist.

Das „Identitäts“-Rätsel: Was macht zwei Dinge gleich?

Ein wesentlicher Teil der Arbeit besteht darin, ein kniffliges Rätsel zu lösen: Wie wissen wir, ob zwei kreisende Bäume tatsächlich dieselben sind?

In der Standardmathematik gilt: Wenn zwei Dinge gleich aussehen, sind sie gleich. Aber in einer Welt mit Schleifen wird es seltsam.

• Die Autoren entdeckten, dass die „Gleichheit“ zwischen zwei Punkten in ihren kreisenden Bäumen als eine andere Art von Baum (ein „indizierter M-Typ“) beschrieben werden kann.
• Die Metapher: Stellen Sie sich vor, Sie vergleichen zwei unendliche Fraktale. Um zu beweisen, dass sie gleich sind, schauen Sie nicht nur auf das Gesamtbild; Sie müssen jeden einzelnen Ast, jeden Teilast, jeden Teil-Teilast vergleichen. Die Arbeit liefert ein präzises Rezept (eine „Charakterisierung“) dafür, wie man diesen Vergleich durchführt. Sie haben bewiesen, dass die „Gleichheit“ dieser komplexen Schleifen selbst ein strukturiertes, unendliches Objekt ist.

Zusammenfassung der Leistungen

1. Scotts Modell: Sie bauten ein Universum von Mengen, das Schleifen erlaubt, wobei die Gleichheit durch die Form des „Entfaltungsbaums“ bestimmt wird. Dieses Modell ist ein Fixpunkt, aber nicht der absolut „terminale“.
2. Aczels Modell: Sie bauten das „ultimative“ Universum von Mengen, das Schleifen erlaubt, wobei jeder Graph in eine Menge verwandelt werden kann. Dies erforderte eine spezielle mathematische Annahme (Propositional Resizing).
3. Das „Gleichheits“-Rezept: Sie haben genau herausgefunden, wie man „Gleichheit“ für diese unendlichen, kreisenden Strukturen definiert, und gezeigt, dass Gleichheit selbst eine Art von Baumstruktur ist.
4. Formalisierung: Sie haben dies nicht nur auf Papier niedergeschrieben; sie haben es in einem Computerprogramm namens Agda aufgebaut, das jeden logischen Schritt überprüft, um sicherzustellen, dass keine Fehler vorliegen.

Warum ist das wichtig?

Die Arbeit behauptet nicht, reale Ingenieursprobleme oder medizinische Fragen zu lösen. Stattdessen löst sie ein fundamentales Rätsel der Mathematik. Sie zeigt, dass wir ein konsistentes, logisches Universum bauen können, in dem „Kreise“ und „Schleifen“ erlaubt sind, indem wir die moderne Sprache der Homotopietheorie verwenden. Sie schließt die Lücke zwischen der klassischen Mengenlehre (die Schleifen verbietet) und der modernen Informatik-Logik (die komplexe, zirkuläre Datenstrukturen wie Streams und Übergangssysteme handhaben muss).

Kurz gesagt: Sie haben zwei verschiedene „Universen“ gebaut, in denen Dinge sich selbst enthalten können, bewiesen, dass diese nach spezifischen Regeln funktionieren, und genau gezeigt, wie man feststellt, ob zwei solche selbstenthaltenden Dinge tatsächlich identisch sind.