»In der Mathematik wird Dummheit zum Talent erhoben und das Talent zur Unfähigkeit degradiert«, sagte der Philosoph Sir William Hamilton im Jahr 1836. Seine negative Einstellung rührte vor allem daher, dass Mathematik aus seiner Sicht nicht viel mit logischen Schlussfolgerungen zu tun hatte. Und tatsächlich lag er damit nicht ganz falsch: Eine formale Theorie der Logik gab es zu diesem Zeitpunkt noch nicht. Erst als der Mathematiker George Boole etwa 20 Jahre später Rechenregeln für logische Ausdrücke vorstellte, legte er den Grundstein für ein solides mathematisches Fundament. Mit diesem Grundgerüst hängt auch die im April 2023 vorgestellte neunte Dedekind-Zahl zusammen, deren 42-stelliger Wert für Schlagzeilen sorgte.

In der Mittelstufe lernen die meisten Schülerinnen und Schüler erstmals die elementare Algebra kennen: Plötzlich werden nicht mehr bloß feste Zahlenwerte miteinander addiert, multipliziert, subtrahiert oder durcheinander geteilt, sondern es tauchen auch Variablen, wie x oder y auf, die für eine unbekannte Zahl stehen. In diesem Zusammenhang lernt man Gleichungssysteme kennen, die man lösen muss, ebenso wie die zu den Gleichungen gehörenden geometrischen Darstellungen: die Funktionsgraphen, etwa Geraden oder Parabeln. Zu Beginn des 19. Jahrhunderts stellten Mathematiker fest, dass man diese Form der Algebra weiter abstrahieren kann: Warum sollten Variablen wie x oder y bloß Zahlenwerte annehmen? Schließlich könnten sie auch komplizierteren Strukturen entsprechen, zum Beispiel Vektoren, Matrizen oder noch abstrakteren Größen.

Boole wollte aber noch einen Schritt weiter gehen und »Gedanken« durch eine symbolische Sprache wie die Algebra ausdrücken. Die Rechenregeln sollten dabei helfen, den Wahrheitsgehalt dieser Gedanken zu ermitteln. Zum Beispiel: Die Aussage »Paris ist die Hauptstadt von Frankreich und Frankreich gehört zur EU« ist genau dann wahr, wenn die zwei Sätze »Paris ist die Hauptstadt von Frankreich« und »Frankreich gehört zur EU« jeweils für sich genommen wahr sind.

Von der »Mathematik der Wahrheit« zu Computern

Das lässt sich etwas abstrakter durch zwei Variablen a und b ausdrücken, die für beliebige Aussagen stehen können: »a und b« ist genau dann wahr, wenn a wahr und auch b wahr ist. Um das Ganze kompakter auszudrücken, führen Fachleute das Symbol ∧ für die Verknüpfung »und« ein und bezeichnen eine wahre Aussage mit »1«, eine falsche mit »0«. Somit erhält man die logische Regel: a ∧ b ergibt genau dann 1, falls a = 1 und b = 1. Andernfalls (also wenn entweder a oder b oder beide gleich 0 sind) lautet das Ergebnis 0. Das kann man in einer Verknüpfungstabelle zusammenfassen:

»Die reine Mathematik wurde durch Boole entdeckt«Bertrand Russell, Philosoph und Mathematiker

Boole fand neben der und-Operation weitere Verknüpfungen, wodurch es ihm gelang, eine Algebra für Wahrheitswerte (»wahr« oder »falsch«) zu entwerfen – und damit eine formale Theorie der Logik zu entwickeln. Auf diese Art revolutionierte er das Fach. »Die reine Mathematik wurde durch Boole in seiner Arbeit ›The Laws of Thought‹ entdeckt«, sagte der renommierte Mathematiker und Philosoph Bertrand Russell. Heute bildet die boolesche Algebra die Grundlage für Computer: Die elektronischen Schaltungen, welche die vielen Einsen und Nullen eines Algorithmus verarbeiten, basieren auf den Prinzipien der booleschen Algebra.

Eine wichtige Rolle spielen in diesem Zusammenhang so genannte boolesche Funktionen. Und sie sind es auch, die uns zu den Dedekind-Zahlen führen werden. Boolesche Funktionen f sind Abbildungen, die verknüpften Variablen einen Wahrheitsgehalt zuordnen. Im Prinzip entsprechen sie einer logischen Aussage. Ein einfaches Beispiel dafür ist die zuvor erwähnte und-Verbindung zweier Ausdrücke: f(a, b) = a ∧ b. Die Funktionen können aber auch komplizierter ausfallen. Zum Beispiel kann man die Aussage »mindestens zwei der Variablen a, b, c sind wahr« als boolesche Funktion ausdrücken: ((a und b) oder (a und c) oder (b und c)). Indem man die Werte 1 oder 0 für a, b, c in f einsetzt, erfährt man, ob mindestens zwei der Variablen wirklich wahr sind (in diesem Fall lautet das Ergebnis 1) oder ob die Aussage falsch ist (das Ergebnis ist 0). Hierbei braucht man neben der und-Operation eine weitere Verknüpfung, die oder-Operation (∨). Deren Funktionsweise lässt sich ebenfalls in einer Tabelle zusammenfassen:

Die und- und oder-Operationen genügen jedoch nicht, um jede mögliche boolesche Funktion zu konstruieren. Man braucht dafür noch eine dritte Operation, die Negation ¬. Sie kehrt den Wahrheitsgehalt einer Aussage um, also ¬0 = 1 und umgekehrt ¬1 = 0.

Die mysteriösen Dedekind-Zahlen hängen mit der Anzahl von booleschen Funktionen zusammen. Angenommen, man hat n verschiedene Variablen a, b, c, … Jede dieser Variablen kann den Wert 1 oder 0 annehmen, was zu 2ⁿ verschiedenen Kombinationen führt (alle sind wahr; a ist falsch und alle anderen sind wahr; a und b sind falsch und alle anderen wahr und so weiter). Aus diesen Variablen kann man durch boolesche Funktionen nun allerlei Aussagen basteln, die sich am Ende als wahr (1) oder falsch (0) herausstellen. Das heißt, zu jedem der 2ⁿ verschiedenen Konfigurationen erhält man durch eine boolesche Funktion das Ergebnis 0 oder 1. Demnach gibt es für n Variablen zwei hoch zwei hoch n boolesche Funktionen. Das ist eine dreifache Exponentialfunktion, sie wächst also unglaublich schnell an.

Die Dedekind-Zahlen beziehen sich jedoch auf spezielle boolesche Funktionen, die man »monoton« nennt. Angenommen, eine Variable a hat den Wert 0 (die Aussage a ist also falsch) und die boolesche Funktion f, die von a abhängt, liefert das Ergebnis 1. Sprich, die zu f(a=0, b, c, …) gehörige logische Aussage ist wahr. Falls a plötzlich ihren Wert ändert und wahr wird (also a = 1), dann kann ein monotones f(a=1, b, c, …) durch diese Änderung nicht falsch werden, sondern muss immer noch den Wert 1 liefern. Der Mathematiker Richard Dedekind stellte 1897 die Frage, wie viele monotone boolesche Funktionen es für n Variablen gibt. Diese »Dedekind-Zahlen« M(n) sind so schwer zu berechnen, dass bis heute nur die ersten neun bekannt sind – dennoch lässt sich das Prinzip recht gut veranschaulichen.

Wie entscheidet man, wann eine Gruppe in die Kantine geht?

Dafür hat ein Nutzer der Plattform »Reddit« ein Beispiel aus dem Arbeitsalltag entwickelt. Meinen Kolleginnen und Kollegen von »Spektrum« gehen meist um 12 Uhr in die Kantine zum Mittagessen. Aber es könnte sein, dass einige aus der Gruppe um diese Uhrzeit noch nicht hungrig sind und lieber etwas warten möchten. Nun kann man versuchen, eine »Kantinen-Regel« dafür zu entwickeln, ob man um 12 Uhr aufbricht oder lieber noch etwas wartet. Die Regel entspricht einer booleschen Funktion, die von mehreren Variablen (Hungergefühl der Kollegen) abhängt und ein eindeutiges Ergebnis liefert: Wir gehen um 12 Uhr essen (1) oder wir warten noch (0).

Natürlich gibt es viele Möglichkeiten, wie eine solche Regel aussehen könnte – denn niemand hat gefordert, dass sie fair sein soll. Zum Beispiel könnten manche Mitarbeiter stärker berücksichtigt werden, wie eine schwangere Kollegin, die hungrig ist. Die einzige Einschränkung, die man der Regel auferlegen sollte, ist: Falls eine Person plötzlich Hunger entwickelt (was der Änderung einer Variablen von 0 zu 1 entspricht), kann das nicht dazu führen, dass die Entscheidung zur Kantine aufzubrechen (1) geändert wird und man lieber noch etwas wartet (0). Sonst ist alles erlaubt. Damit erfüllt die Kantinen-Regel die Anforderungen einer monotonen booleschen Funktion.

Die n-te Dedekind Zahl entspricht der Anzahl an möglichen Kantinen-Regeln, die man mit n Mitarbeitenden entwickeln kann. Angenommen, ich bin an einem Tag alleine im Büro (n = 1). Dann gibt es drei verschiedene mögliche Kantinen-Regeln – ob sie mir nun gefallen oder nicht, sei dahingestellt:

1. Falls ich um 12 Uhr hungrig bin (a = 1), gehe ich in die Kantine (f(a) = 1), sosnst (a = 0) warte ich noch (f(a) = 0). Damit lautet die dazugehörige boolesche Funktion: f(a) = a.
2. Ich gehe um 12 Uhr in die Kantine (1), unabhängig davon, ob ich hungrig bin oder nicht – zum Beispiel, weil ich um 13 Uhr einen Termin habe. Die dazugehörige Funktion lautet f(a) = 1.
3. Ich gehe erst später in die Kantine (0), unabhängig davon, ob ich hungrig bin oder nicht – zum Beispiel, weil ich um 12 Uhr einen Termin habe. Die dazugehörige Funktion ist f(a) = 0.

Damit hat die erste Dedekind-Zahl den Wert drei, M(1) = 3.

Auch die zweite Dedekind-Zahl lässt sich auf diese Weise berechnen. Wenn außer mir eine weitere Kollegin im Büro ist, kann man wieder alle möglichen Kantinen-Regeln durchspielen. In diesem Fall gibt es sechs Stück:

1. Wir gehen um 12 Uhr essen, unabhängig davon, ob wir hungrig sind: f(a, b) = 1.
2. Wir gehen erst später essen, unabhängig davon, ob wir hungrig sind: f(a, b) = 0.
3. Die Entscheidung hängt nur davon ab, wie hungrig ich (a) bin: f(a, b) = a.
4. Die Entscheidung hängt nur davon ab, wie hungrig meine Kollegin (b) ist: f(a, b) = b.
5. Wir gehen nur dann um 12 Uhr essen, falls wir beide gleichzeitig hungrig sind, sonst warten wir: f(a, b) = a ∧ b.
6. Wir gehen um 12 Uhr essen, falls eine von uns hungrig ist: f(a, b) = a ∨ b.

Es gibt in etwa so viele Sterne im Universum, wie man Kantinen-Regeln für acht Personen aufstellen kann

Damit ist M(2) = 6. Bisher wirkt die Berechnung der Dedekind-Zahlen nicht allzu kompliziert. Doch wie sich herausstellt, wachsen die Werte rasant an. Das sollte nicht allzu erstaunlich sein, wenn man bedenkt, dass die Anzahl aller booleschen Funktionen mit einer dreifachen Potenz anwachsen.

Die dritte Dedekind-Zahl ist 20, die vierte 168 und die fünfte 7581. Diese Werte waren die einzigen, die der Mathematiker Randolph Church bis 1940 berechnen konnte. Sechs Jahre später bestimmte sein Kollege Morgan Ward M(6) = 7 828 354. 1965 gelang es Church schließlich, M(7) = 2 414 682 040 998 zu finden. Erst 1991 konnte Doug Wiedemann M(8) berechnen (56 130 437 228 687 557 907 788). Das ist nicht allzu erstaunlich: Um diesen gigantischen Wert zu finden, musste der Mathematiker den damaligen Cray 2 Supercomputer gut 200 Stunden lang auf Hochtouren laufen lassen. M(8) ist größer als 10²², was in etwa der geschätzten Anzahl an Sternen im Universum entspricht. Es gibt also in etwa so viele Sterne im Universum, wie man Kantinen-Regeln für acht Personen aufstellen kann.

Zwei Gruppen finden zufälligerweise gleichzeitig die neunte Dedekind-Zahl

Die neunte Dedekind-Zahl erfordert so viele Berechnungen, dass ihr exakter Zahlenwert erst im April 2023 bestimmt wurde. Und das gleich zweimal: Erstaunlicherweise gelang es zwei Forscherteams unabhängig voneinander, das gleiche Ergebnis innerhalb von weniger als zwei Wochen zu veröffentlichen.

Da die Leistung von Supercomputern in den vergangenen 40 Jahren erheblich zugenommen hat, erschien dem Informatiker Lennart Van Hirtum die neunte Dedekind-Zahl plötzlich in Reichweite, wie er in einer Pressemitteilung der Universität Paderborn erklärte. Es gibt sogar eine Formel, um die Dedekind-Zahlen mit Hilfe einer riesigen Summe zu berechnen. Für die Bestimmung von M(9) kann man sie aber nicht so einfach nutzen, wie Van Hirtum in der Pressemitteilung sagte: »Selbst wenn man einen großen Supercomputer ausschließlich für diese Aufgabe verwenden würde, würde es immer noch viele Jahre dauern, bis die Berechnung abgeschlossen ist.« Doch der Informatiker und seine Kollegen gaben nicht auf: Indem sie einige Symmetrien ausnutzten, die die Anzahl der zu addierenden Terme reduzieren, konnten sie die Berechnung von M(9) auf etwa 10¹⁸ Rechenschritte reduzieren – ein Wert, mit dem moderne Supercomputer umgehen können.

Erstaunlicherweise waren sie aber nicht die einzigen, die an dieser Aufgabe tüftelten. Der Mathematiker Christian Jäkel von der TU Dresden hatte sich in den letzten sechs Jahren ebenfalls damit beschäftigt, die neunte Dedekind-Zahl zu berechnen. Er wählte dafür einen anderen Ansatz, bei dem er Elemente von M(5) miteinander multiplizierte. Auch hierbei war ein enormer Rechenaufwand nötig: 28 Tage lange waren acht Grafikkarten (die auch für das Training von großen KI-Modellen genutzt werden) im Einsatz. Am 5. April 2023 veröffentlichte Jäkel schließlich sein 42-stelliges Ergebnis für die neunte Dedekind-Zahl auf dem Preprint-Server ArXiv: 286386577668298411128469151667598498812366.

Nur 13 Tage später publizierten auch Van Hirtum und seine Kollegen ihre Arbeit. »Ich war schockiert«, sagte Jäckel zum populärwissenschaftlichen Magazin »New Scientist«. »Ich wusste nichts von ihrer Arbeit. Ich dachte, es würde mindestens 10 Jahre oder so dauern, um das Ergebnis neu zu berechnen.« Zu seiner großen Freude kamen die Informatiker um Van Hirtum zum gleichen Zahlenwert für die neunte Dedekind-Zahl.

Damit ist nun auch geklärt, wie viele mögliche Kantinen-Regeln es für neun Personen gibt. Die Anzahl ist unvorstellbar groß. Noch unvorstellbarer wird es, wenn man die zehnte Dedekind-Zahl betrachtet. Ihre Größe wird auf etwa 10⁸² geschätzt, eine 82-stellige Zahl. Bis dieser Zahlenwert allerdings exakt bestimmt wird, werden höchstwahrscheinlich viele Jahre vergehen – dafür ist noch einiges mehr an Rechenleistung notwendig.