Mathematik Wahr oder Falsch?

„Die Route wird berechnet …“ – diesen Spruch kennen alle, die das Navi den besten Weg von A nach B suchen lassen. Während wir auf die Route warten, berechnen Algorithmen auf der Basis der aktuellen Verkehrs­situation, ob wir heute lieber die Auto­bahn oder die Land­­straße nehmen sollten. Längst helfen uns solche digitalen Assistenten in einer Vielzahl alltäglicher Situationen.

Auch bei der Lösung von mathematischen Problemen können Algorithmen, die uns Entscheidungen abnehmen, nützlich sein. Und zwar, wenn es darum geht, ob bestimmte Aussagen wahr oder falsch sind. Einem solchen Entscheidungs­algorithmus wird eine mathematische Aussage vorgegeben, und er liefert als Antwort entweder „wahr“ oder „falsch“.

Dabei gilt es, den Kontext der Aussage präzise festzu­legen – so wie das Navi wissen muss, ob man zu Fuß oder mit dem Auto unterwegs ist. Betrachten wir die Aussage: „Es gibt eine kleinste Zahl.“ Kinder der 2. Klasse würden wohl sagen: „Klar, die Null!“ Doch sobald sie im Winter auf das Thermo­meter schauen, werden sie fest­stellen, dass es auch kleinere Zahlen gibt. Es kommt also darauf an, was man unter dem Begriff „Zahl“ versteht. Unser Team beschäftigt sich mit Entscheidungs­algorithmen im Bereich der reellen Zahlen, also jenen Zahlen, mit denen wir auch im Alltag umgehen und die bei Berechnungen auftauchen: –6 Grad Celsius, ¹/₂ Teelöffel, 5,99 Euro, √2, Kreiszahl π. Überdies muss eine Aussage in einer geeigneten Sprache formuliert sein. Anders als unsere All­tags­sprache, besteht diese aus Symbolen. Der Satz „Drei plus zwei ist kleiner als acht“ etwa entspricht in der mathematischen Form: „3 + 2 < 8“. Neben Zahlen sind die Grund­rechen­arten, also +, –, × und ÷, sowie die Vergleichssymbole =, < und > zulässig. Ein guter Entscheidungs­algorithmus würde auf die Eingabe „3 + 4 = 9 – 5“ ein „falsch“ ausgeben. Weitere Symbole sind Variablen wie x und y sowie sogenannte logische Symbole. Diese erlauben komplexere Aussagen und stehen für Ausdrücke wie „Es gibt ein x, für das … gilt“ oder „Wenn …, dann …“. Auf diese Weise lassen sich Aussagen wie „Es gibt ein x, für das x + 5 = 8 gilt“ formulieren, die ein Entscheidungs­algorithmus als „wahr“ erkennen sollte. Dabei ist zu beachten, dass der Algorithmus das gesuchte x nicht ausgibt. Die Lösung x = 3 müssen wir also noch berechnen.

Einen ersten Algorithmus für Aussagen in dieser symbolischen Sprache, die allein auf den vier Grund­rechen­arten basiert, entwickelte der polnisch-amerikanische Mathematiker Alfred Tarski im Jahr 1948. Für Ausdrücke wie 2X oder y6 benötigen wir allerdings die Rechenart des Exponenzierens. Damit kann der Tarski-Algorithmus nicht umgehen, weshalb bis in die 2000er-Jahre zwei weitere Algorithmen entwickelt wurden, die des Exponenzierens fähig sind. Nennen wir sie hier einfachheits­halber Algorithmus A und Algorithmus B. Leider konnten die Entwickler­teams die Funktions­tüchtig­keit dieser beiden Algorithmen nur unter Annahme je einer „Vermutung“ nachweisen. Im ersten Fall handelt es sich um die Vermutung von Schanuel, im zweiten Fall um die sogenannte Transfer-Vermutung.

Ausgerechnet in der Mathematik erscheint es nun merkwürdig, eine Vermutung, also eine unbewiesene Aussage, anzunehmen und darauf neue Resultate aufzubauen. Doch ist dies in der Mathematik üblich, wenn sich die meisten Expertinnen und Experten einig sind, dass die Vermutung wahrscheinlich stimmt.

Aber wie arbeiten die Algorithmen A und B? Sie beginnen jeweils mit einer Liste von grund­legend wahren Aussagen wie „0 < 1“ oder „Für alle x und für alle y gilt: x + y = y + x“, dem Kommutativ­gesetz der Addition. Solche Aussagen nennt man Axiome. Sie sind im Algorithmus eingespeichert wie die Straßenkarten im Navi. Auf Basis der Axiome wendet der Algorithmus bestimmte Regeln an, um zu neuen wahren Aussagen zu gelangen. Beispiels­weise lässt sich mit der Regel „Zahl einsetzen“ aus dem Kommutativ­gesetz folgern: 2 + 3 = 3 + 2. Wenn wir nun eine Aussage in den Algorithmus eingeben, wollen wir wissen, ob sie wahr oder falsch ist. Der Algorithmus folgert aus den Axiomen so lange weitere wahre Aussagen, bis er unsere eingegebene Aussage oder ihr Gegenteil erhält. Im ersten Fall liefert er uns ein „wahr“, im zweiten ein „falsch“. Ähnlich fährt ein Navi virtuell die Straßenkarten ab und beachtet dabei in jedem Schritt die Verkehrs­regeln, bis es schließlich die für unsere Zwecke optimale Route ausgibt. Bei der Anwendung sollten wir sicher sein, dass der Algorithmus tatsächlich auf die von uns eingegebene Aussage oder ihr Gegen­teil stößt, also die Route vervollständigt. Ob das klappt, hängt von den eingespeicherten Axiomen ab – auch das Navi findet nicht den optimalen Weg ans Ziel, wenn ein Straßenabschnitt in seiner Datenbank fehlt. Hier kommt Algorithmus B ins Spiel – er basiert auf der bereits erwähnten Transfer-Vermutung: Sie besagt, dass wir neben den grund­legenden Rechen­regeln nur ein weiteres Axiom benötigen, nämlich das Axiom der Ordnungs-Minimalität (kurz: O-Minimalität). Es drückt aus, dass die Lösungs­mengen von Gleichungen und Ungleichungen nur aus endlich vielen Intervallen bestehen. Dabei ist ein Intervall ein zusammen­hängender „Abschnitt“ auf dem Zahlen­strahl, also eine Menge von Zahlen, die oberhalb und/oder unter­halb eines bestimmten Wertes liegen. So ist die Lösungsmenge der Ungleichung „4 < 2X < 8“ das Intervall aller reellen Zahlen zwischen 2 und 3, da genau diese Zahlen für x eingesetzt werden können, damit die Aussage stimmt.

Am Anfang unserer Arbeit hatten wir es also mit einem Algorithmus zu tun, der zwar funktioniert, aber nicht exponenzieren kann. Dann mit zwei Algorithmen, die zwar exponenzieren können, aber nicht sicher funktionieren. Und mit zwei unbewiesenen Vermutungen. Unser Ziel war, Zusammen­hänge zwischen der Vermutung von Schanuel, der Transfer-Vermutung und der Eigenschaft der O-Minimalität zu finden.

Indem wir wahre Aussagen formulierten, die ohne O-Minimalität niemals erreicht werden, zeigten wir, dass der Algorithmus B ohne die Transfer-Vermutung tatsächlich nicht funktionieren kann. Zudem gelang es uns, Verbindungen zwischen der Vermutung von Schanuel und der Transfer-Vermutung aufzudecken. Dies ist besonders interessant, da die beiden Vermutungen aus zwei unter­schiedlichen Gebieten der Mathematik – Zahlen­theorie und mathematischer Logik – stammen, zwischen denen wir so eine bisher unbekannte Brücke schlugen. Zuletzt haben wir neue Ansätze beschrieben, mit denen sowohl die Transfer-Vermutung als auch die Vermutung von Schanuel bewiesen werden könnten. Vielleicht führen diese Ansätze in Zukunft gerade zu den fehlenden Puzzle­teilen, welche die ersehnten Beweise vervollständigen.

Doch wozu das Ganze, bezweifelt doch niemand, dass die beiden Entscheidungs­algorithmen funk­tionieren und daher eingesetzt werden könnten? Die Antwort ist ernüchternd: Schon bei kurzen Aussagen wie „Es gibt ein x, für das 2X = 8 gilt“ würden wir mit heutiger Rechen­leistung wohl nicht mehr erleben, dass die Algorithmen ein „wahr“ ausgeben. Dabei ist diese Gleichung eigentlich so einfach, dass man sie sogar gut im Kopf lösen kann.

Wir betrachten die abstrakten Fragestellungen, mit denen wir uns beschäftigen, vor allem als geistige Heraus­forderungen. Auch wenn unsere Algorithmen in der Praxis vermutlich niemals anwendbar sein werden, sind wir nicht die Ersten, die von solchen Gedanken­modellen fasziniert sind. So schrieb auch schon der Mathematiker Alfred Tarski (1901–1983) dazu: „Es mag unpopulär und altmodisch klingen, aber ich denke nicht, dass eine wissenschaftliche Errungenschaft, die uns die Welt besser verstehen lässt und sie in unseren Augen harmonischer macht, weniger wert­geschätzt werden sollte als beispiels­weise eine Erfindung, mit der sich die Kosten für das Pflastern von Straßen senken oder unsere Sanitär­anlagen verbessern lassen.“