Rechnung

Mathematik Wahr oder Falsch?

Algorithmen können bei der Entscheidung helfen, ob eine mathematische Aussage wahr oder falsch ist. Das klingt einfach. Doch warum es tatsächlich funktioniert, ist eine offene Frage

von Dr. Lothar Sebastian Krapp

„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, 1/2 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.

Lothar Sebastian Krapp sprüht mit Kreidespray eine symbolische Formel auf den Innenhof der Uni Konstanz
©Ingo Knopf
Szene aus einem Video, in dem Lothar Sebastian Krapp mit Kreidespray eine symbolische Formel auf den Innenhof der Uni Konstanz sprüht

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.

YouTube

Mit dem Laden des Videos akzeptieren Sie die Datenschutzerklärung von YouTube.
Mehr erfahren

Video laden

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.“

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 Nazi­terror und emigrierte in die USA. Von 1942 bis zu seinem Tod im Jahr 1983 arbeitete er an der University of California in Berkeley. Zeit­genossen beschreiben den Gelehrten als extro­vertiert, schlag­fertig und scharf­zü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 Frage­runden 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

Sie verwenden einen veralteten Browser oder haben Javascript in Ihrem Browser deaktiviert.
Bitte aktualisieren Sie Ihren Browser oder aktivieren Sie Javascript.
x