Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03247.jsonl.gz/644

„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 Verkehrssituation, ob wir heute lieber die Autobahn oder die Landstraß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 Entscheidungsalgorithmus wird eine mathematische Aussage vorgegeben, und er liefert als Antwort entweder „wahr“ oder „falsch“.
Dabei gilt es, den Kontext der Aussage präzise festzulegen – 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 Thermometer schauen, werden sie feststellen, dass es auch kleinere Zahlen gibt. Es kommt also darauf an, was man unter dem Begriff „Zahl“ versteht. Unser Team beschäftigt sich mit Entscheidungsalgorithmen im Bereich der reellen Zahlen, also jenen Zahlen, mit denen wir auch im Alltag umgehen und die bei Berechnungen auftauchen: –6 Grad Celsius, 1/2 Teelöffel, 5,99 Euro, √2, Kreiszahl π. Überdies muss eine Aussage in einer geeigneten Sprache formuliert sein. Anders als unsere Alltagssprache, 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 Grundrechenarten, also +, –, × und ÷, sowie die Vergleichssymbole =, < und > zulässig. Ein guter Entscheidungsalgorithmus 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 Entscheidungsalgorithmus 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 Grundrechenarten 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 einfachheitshalber Algorithmus A und Algorithmus B. Leider konnten die Entwicklerteams die Funktionstüchtigkeit 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 grundlegend wahren Aussagen wie „0 < 1“ oder „Für alle x und für alle y gilt: x + y = y + x“, dem Kommutativgesetz 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. Beispielsweise lässt sich mit der Regel „Zahl einsetzen“ aus dem Kommutativgesetz 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 Verkehrsregeln, 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 Gegenteil 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 grundlegenden Rechenregeln 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ösungsmengen von Gleichungen und Ungleichungen nur aus endlich vielen Intervallen bestehen. Dabei ist ein Intervall ein zusammenhängender „Abschnitt“ auf dem Zahlenstrahl, also eine Menge von Zahlen, die oberhalb und/oder unterhalb 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, Zusammenhä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 unterschiedlichen Gebieten der Mathematik – Zahlentheorie 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 Puzzleteilen, welche die ersehnten Beweise vervollständigen.
Doch wozu das Ganze, bezweifelt doch niemand, dass die beiden Entscheidungsalgorithmen funktionieren 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 Rechenleistung 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 Herausforderungen. Auch wenn unsere Algorithmen in der Praxis vermutlich niemals anwendbar sein werden, sind wir nicht die Ersten, die von solchen Gedankenmodellen 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 wertgeschätzt werden sollte als beispielsweise eine Erfindung, mit der sich die Kosten für das Pflastern von Straßen senken oder unsere Sanitäranlagen verbessern lassen.“
Deshalb ist Schnee weiß
Vier Weisheiten des Mathematikers, Logikers und Philosophen Alfred Tarski
Alfred Tarski wurde 1901 in Warschau geboren. 1939 entkam er knapp dem Naziterror und emigrierte in die USA. Von 1942 bis zu seinem Tod im Jahr 1983 arbeitete er an der University of California in Berkeley. Zeitgenossen beschreiben den Gelehrten als extrovertiert, schlagfertig und scharfzüngig. Zitate, die von Tarski überliefert sind, belegen, dass er auch über eine gute Portion Witz und Selbstironie verfügte. Eine Auswahl:
„Die Kenntnis der Logik ist zweifellos für jeden, der richtig denken und folgern will, von erheblicher praktischer Bedeutung.“
„Wenn ein Mathematiker die Arbeit eines seiner Kollegen, sagen wir A, herabsetzen will, tut er dies am effektivsten, wenn er nach der praktischen Anwendung der Ergebnisse fragt. Der so bedrängte Kollege wird als Beispiel für die Anwendung der eigenen Ergebnisse nun auf Forschungen eines anderen Mathematikers B verweisen. Konfrontiert man nun B mit der gleichen Frage, so wird sich dieser auf einen weiteren Kollegen C beziehen. Nach einigen Fragerunden werden wir wieder auf die Forschungen von A treffen. So schließt sich der Kreis.“
„Die Logik gilt zu Recht als Grundlage aller Wissenschaften, und sei es nur deshalb, weil wir in jeder Argumentation Begriffe aus dem Bereich der Logik verwenden, und weil wir immer nach ihren Gesetzen zu dem richtigen Schluss kommen.“
„Sie werden in der Semantik kein Mittel gegen Karies, Größenwahn oder Klassenkampf finden.“
Der Satz „Schnee ist weiß“ ist genau dann wahr, wenn Schnee weiß ist. — JS