Eine neue Brücke verbindet die seltsame Mathematik des Unendlichen mit der Informatik

• Es hat sich gezeigt, dass die deskriptive Mengenlehre, ein technisches Fachgebiet zur Erforschung der Struktur unendlicher Mengen, in die Sprache von Algorithmen neu interpretiert werden kann
• Der Mathematiker Anton Bernshteyn bewies, dass sich Probleme unendlicher Graphen als Kommunikationsprobleme in Computernetzwerken umschreiben lassen
• Diese Verbindung zeigt eine Entsprechung zwischen Messbarkeit (measurability) und der Effizienz verteilter Algorithmen
• Forschende leiten über diese Brücke Sätze und Probleme beider Disziplinen wechselseitig ineinander über und gewinnen so neue Resultate
• Die Entdeckung definiert die Grenze zwischen Unendlichkeit und Berechnung neu und erweitert die Möglichkeiten der Zusammenarbeit zwischen Mathematik und Informatik

---

Einleitung: Mengenlehre und die Welt des Unendlichen

• Die Grundlagen der modernen Mathematik beruhen auf der Mengenlehre, und die meisten Mathematiker behandeln Probleme unter dieser Voraussetzung
• Deskriptive Mengenlehrer (descriptive set theorists) sind jedoch eine kleine Gruppe von Forschenden, die weiterhin das Wesen unendlicher Mengen untersuchen
• 2023 entdeckte Anton Bernshteyn eine tiefe Verbindung zwischen deskriptiver Mengenlehre und Informatik
  • Er zeigte, dass sich Probleme bestimmter unendlicher Mengen in Kommunikationsprobleme von Computernetzwerken übersetzen lassen
• Das Ergebnis gilt als Brücke zwischen gegensätzlichen Sprachen wie Logik und Algorithmen sowie Unendlichkeit und Endlichkeit

Hintergrund der deskriptiven Mengenlehre

• Die Ursprünge der Mengenlehre liegen in den Arbeiten von Georg Cantor, der verschiedene Größen von Unendlichkeit nachwies
• Zu den Begriffen zur Beschreibung der Größe von Mengen gehören Kardinalität (cardinality) und Maß (measure)
  • Beispiel: Die Menge der reellen Zahlen im Intervall 0 bis 1 und die im Intervall 0 bis 10 haben dieselbe Kardinalität, aber die Maße 1 beziehungsweise 10
• Die deskriptive Mengenlehre unterscheidet messbare Mengen und nicht messbare Mengen und ordnet sie in eine Komplexitätshierarchie (hierarchy) ein
• Diese Hierarchie dient in anderen mathematischen Gebieten (z. B. Wahrscheinlichkeitstheorie, dynamische Systeme, Gruppentheorie) als Kriterium für die Wahl geeigneter Werkzeuge

Unendliche Graphen und Färbungsprobleme

• Bernshteyn untersuchte unendliche Graphen und modellierte die Knoten und Kanten jedes Graphen als unendlich verbundene Struktur
• Beispiel: Verbindet man Punkte auf einem Kreis in konstanten Abständen, entsteht bei rationalem Abstand ein geschlossener Ring, bei irrationalem Abstand dagegen eine unendlich verbundene Struktur
• Färbt man die Knoten eines Graphen mit zwei Farben, ist das mit dem Auswahlaxiom (axiom of choice) möglich, führt aber zu einer nicht messbaren Menge
• Verwendet man dagegen eine stetige Färbung, werden drei Farben benötigt, dafür erhält man eine messbare Menge
• Dieser Unterschied wirkt als Schlüsselelement bei der Bestimmung der Position in der mengentheoretischen Komplexitätshierarchie

Begegnung mit verteilten Algorithmen

• 2019 hörte Bernshteyn einen Informatikvortrag über verteilte Algorithmen (distributed algorithms) und erkannte eine Ähnlichkeit
  • Beispiel: Das Problem, dass Wi-Fi-Router unterschiedliche Frequenzen (Farben) wählen müssen, um sich nicht gegenseitig zu stören
• Jeder Knoten kommuniziert nur mit benachbarten Knoten und bestimmt seine Farbe mit einem lokalen Algorithmus (local algorithm)
• Mit zwei Farben ist die Lösung ineffizient, mit drei Farben dagegen effizient möglich
• Bernshteyn erkannte, dass dieser Schwellenwert (threshold) für die Zahl der Farben mit dem Schwellenwert des messbaren Färbungsproblems in der deskriptiven Mengenlehre identisch ist

Beweis der Äquivalenz zweier Welten

• Bernshteyn bewies mathematisch die Äquivalenz zwischen effizienten lokalen Algorithmen ↔ messbaren Färbungen
• In endlichen Graphen kann jedem Knoten eine eindeutige Nummer zugewiesen werden, in überabzählbar unendlichen Graphen ist das jedoch unmöglich
• Er entwickelte ein Labeling-Verfahren ohne Überschneidungen zwischen benachbarten Knoten, sodass sich Algorithmen auch auf unendliche Graphen ausdehnen lassen
• Damit wurde gezeigt: Jeder lokale Algorithmus entspricht einer messbaren Färbung in der deskriptiven Mengenlehre
• Das zeigt eine tiefe mathematische Verbindung zwischen Berechenbarkeit und Definierbarkeit (definability)

Erweiterung der Forschung und Anwendungen

• Václav Rozhoň und andere nutzten diese Verbindung, um Färbungsprobleme in Baum-Graphen (tree graphs) zu lösen und Werkzeuge für die Erforschung dynamischer Systeme zu gewinnen
• Umgekehrt gibt es auch Arbeiten, die mit Methoden der Mengenlehre die Abschätzung der Schwierigkeit von Problemen verbessert haben
• Diese Brücke ist mehr als nur ein Werkzeug zur Problemlösung; sie trägt auch zur Neuordnung der Klassifikationssysteme der Mengenlehre bei
• Deskriptive Mengenlehrer können sich nun an den systematischen Klassifikationsmethoden der Informatik orientieren, um bislang ungeordnete Probleme einzuordnen
• Bernshteyn hofft, dass diese Forschung dazu beiträgt, das Konzept des Unendlichen als Teil praktischer Mathematik wahrzunehmen

[GN⁺]

Hacker-News-Kommentare

• Ich frage mich, ob sich solche Ergebnisse auf praktische Bereiche wie verteiltes Rechnen anwenden lassen, oder ob sie nur als rein mathematische Kuriosität existieren.

  • Das ist überhaupt keine dumme Frage. Technische Einsichten könnten zu neuen Unmöglichkeitssätzen in verteilten Algorithmen oder der Theorie der Berechnungskomplexität führen. Auch mögliche Anwendungen wie Mesh-Netzwerke sind interessant.

• Die Aussage „Alle moderne Mathematik ist auf der Mengenlehre aufgebaut“ ist zu pauschal. Moderne mathematische Werkzeuge wie Lean oder Rocq entwickeln sich auf Grundlage von formaliserter Mathematik (formalized mathematics), und diese basiert auf der Typentheorie (type theory).

  • Ich bin kein Mathematiker, aber ich denke, ZFC ist immer noch ein gültiges Grundlagensystem. Abhängige Typen (dependent types) sind nützlich für die Verwaltung von Beweisassistenten, ermöglichen aber nicht, mehr Sätze zu beweisen. Lawrence Paulsons Isabelle/HOL ist nicht typbasiert, kann aber den Großteil der Mathematik beweisen.
  • Allerdings verwenden echte Mathematiker formalisierte Mathematik kaum. Selbst wenn sie davon wissen, nutzen sie sie wegen ihrer Umständlichkeit nicht als Grundlagensprache.
  • Man darf die Sprache der Mathematik nicht mit der formalen Sprache verwechseln, in der über diese Sprache bewiesen wird. Erstere verwendet fast ausschließlich Mengen, letztere notwendigerweise Typen.
  • Genauer gesagt ist es wohl richtig zu sagen, dass die Grundlagenkrise der Mathematik mit der Formalisierung der Mengenlehre vorläufig beendet wurde.

• Die scherzhafte Formulierung „cons’es all the way down“ verspottet rekursive Strukturen.

• Ich bin ergriffen von der Aussage: „Endlich kann man das Unendliche berechnen.“

  • Nächsten Monat findet in der Bay Area die Calculating Infinity-Tour von The Dillinger Escape Plan statt. Konzertlink. Ich teile das, weil sich Fans von Mathematik, Hacking und Mathcore überschneiden dürften.
  • Als Antwort auf „das Unendliche berechnen“ setzt jemand den Witz mit „Und darüber hinaus!“ fort.
  • In Haskell könne man mit einer einzigen Zeile, let x = x in x, eine abzählbare Unendlichkeit (countable infinity) ausdrücken.
  • Mit dem Meme „Chuck Norris hat zweimal von 1 bis unendlich gezählt“ wird noch ein Witz nachgelegt.
  • Mit „Das hat wirklich lange gedauert /s“ wird noch eine sarkastische Bemerkung hinzugefügt.

• Ich stimme der Behauptung nicht zu, dass „die Informatik sich nur mit endlichen Dingen beschäftigt“. Tatsächlich befasst sich die Informatik tiefgehend mit dem Unendlichen.

  • Dass Quanta das so behandelt, kommt häufig vor. Es tendiert zu populärwissenschaftlicher Darstellung, konzentriert sich auf personenbezogene Geschichten und lässt Details weg.
  • Allerdings interessiert sich die Informatik weniger für überabzählbare Unendlichkeit (uncountable infinity). Damit beschäftigt sich vor allem die Maßtheorie (measure theory).
  • Ich dachte anfangs auch, „CS approximiert Unendlichkeit“, aber tatsächlich ist genau das Wort Approximation der Kern. Wir arbeiten immer nur innerhalb endlicher Grenzen. Selbst wenn das Universum unendlich wäre, ist der Bereich, den wir beobachten können, durch die Lichtgeschwindigkeit begrenzt.
  • Sätze wie „Die Informatik verwendet keine Logik“ sind viel zu nachlässige Formulierungen. Boolesche Logik ist der direkte Gegenbeweis.

• Ich habe lange Mathematik studiert und bin zu der Überzeugung gekommen, dass Unendlichkeit (infinity) nicht existiert. Ich glaube, Mathematik könnte ohne Unendlichkeit besser sein.

  • Ich habe auch nur Mathematik auf Ingenieursniveau gelernt, aber ich denke, Unendlichkeit ist keine Zahl, sondern ein Prozess (process). Die „...“ in {1, 2, 3, ...} bedeuten einen nie endenden Erweiterungsprozess. So etwas wie die unendlichste Primzahl gibt es nicht, nur eine Erzeugungsregel, nach der immer größere Primzahlen existieren.
  • Wenn man die Unendlichkeit aber entfernt, wird Mathematik schrecklich kompliziert. Wenn man die natürlichen Zahlen nicht endlos erweitern darf, werden Berechnungen sehr unhandlich.
  • Mathematik interessiert sich weniger für Existenz als für konzeptuelle Nützlichkeit. Auch ein Kreis existiert in der Realität nicht, ist aber nützlich. Ohne Unendlichkeit müsste man sie am Ende in Formen wie „der Grenzwert, wenn x gegen eine sehr, sehr große Zahl geht“ neu erfinden.
  • Mit dem Scherz „Man kann einfach bei 8 aufhören“ wird die Entbehrlichkeit der Unendlichkeit verspottet.
  • Unendlichkeit ist nur ein Name für einen nicht endenden Prozess. Manche Prozesse wachsen schneller, deshalb gibt es größere Unendlichkeiten. Persönlich mag ich das Unendlichkeitskonzept des Riemannschen Kugelmodells.

• Mit dem Witz, node_modules habe die Mathematik des Unendlichen mit meinem Dateisystem verbunden, wird die Explosion von Abhängigkeiten verspottet.

• Der Satz „Alle moderne Mathematik ist auf der Mengenlehre aufgebaut“ wird zurückgewiesen mit dem Hinweis, dass es auch Typentheorie (Type Theory) gibt.

  • Type Theory ist ein stärkeres Axiomensystem als ZFC. Siehe dazu diese MathOverflow-Antwort.
  • Allerdings gibt es noch keine typentheoretische Axiomenmenge, die so einflussreich wäre wie ZF oder ZFC.
  • Technisch gesehen ist deskriptive Mengenlehre (descriptive set theory) von der grundlegenden Mengenlehre getrennt. Sie lässt sich leicht mit Typen- und Raumbegriffen rekonstruieren, was oft vorteilhafter ist. Die mathematische Unendlichkeit aus computationaler Perspektive neu zu interpretieren, ist kein neuer Versuch.
  • Die Beschreibung als „Disziplin zur Organisation von Mengen abstrakter Objekte“ vereinfacht die Mengenlehre zu stark. Trotzdem bleibt es wahr, dass der Großteil der Mathematik nach wie vor aus Mengenaxiomen definiert wird.