Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Vorlesung 1

Probleme

In vielen Lebensbereichen gibt es Probleme: Alltagsprobleme, Beziehungsprobleme, Gesundheitsprobleme, Gewichtsprobleme, Finanzierungsprobleme, Umweltprobleme, technische Probleme, politische Probleme, philosophische Probleme. Zu diesen Problemen gehören jeweils Vorstellungen, wie eine Lösung aussehen könnte oder zumindest eine Ahnung, in welche Richtung man nach einer Lösung suchen könnte; eine präzise Formulierung, wann ein Problem gelöst wäre, fehlt allerdings in den meisten Fällen.

Für die Probleme gibt es in der Regel verschiedene Lösungsansätze oder Lösungsstrategien. Ihr Erfolg variiert und hängt stark von unbeeinflussbaren Begleitumständen, aber auch von der Unschärfe der Problemstellung und den eigenen Bewertungsmaßstäben ab. Eine Strategie, die für dieses und jenes Problem erfolgreich war, stellt sich bei einem neuen Problem plötzlich als unbrauchbar heraus.

Könnte es eine (Meta)-strategie geben, die bei allen Problemen hilft bzw. alle Probleme löst? Eine solche Strategie kann es für die oben formulierten Problembereiche allein schon wegen der angesprochenen Unschärfe nicht geben. Die Probleme sind nie so klar umrissen, dass Einigkeit darüber besteht, ob etwas eine Lösung ist oder nicht.

Dies sieht bei mathematischen Probleme anders aus. Diese sind klar formuliert, zumeist als eine offene Frage, die grundsätzlich nur eine positive oder eine negative Antwort haben kann, und wo die Schwierigkeit darin besteht, dies herauszufinden und zu begründen (beweisen), was denn nun der Fall ist.

In der Schule beschränkt man sich typischerweise auf mathematische Probleme, für die dann eine Lösungsstrategie vorgestellt wird. Daher fragen viele Menschen, ob es denn in der Mathematik noch was zu entdecken gibt. In Wahrheit sind die mathematischen Probleme die treibende Kraft der professionellen Beschäftigung mit Mathematik.

Wir wollen zunächst einige offene mathematische Probleme vorstellen. Im Laufe der Vorlesung werden wir dann die Frage präzisieren, ob es wenigstens für diesen Teilbereich des menschlichen Denkens eine universelle Lösungsstrategie geben kann. Die Antwort wurde um 1930 von Kurt Gödel bewiesen: Eine solche Strategie kann es nicht geben.

Offene mathematische Probleme

Unter den natürlichen Zahlen versteht man die Menge

$\mathbb {N} =\{0,1,2,3,\ldots \}.$

Wir setzen im Moment diese Menge als gegeben voraus und auch die darauf definierten Operationen, also die Addition und die Multiplikation. Die natürlichen Zahlen werden zum Zählen und Berechnen von endlichen Mengen verwendet, und im Allgemeinen gibt es dabei keine Probleme. Addition und Multiplikation sind durch einfache Algorithmen durchführbar (in der mathematischen Logik spricht man von „berechenbar“) und können auch durch eine Maschine ausgeführt werden. Man muss aber nicht viel weiter gehen, um Probleme über natürliche Zahlen formulieren zu können, für die derzeit keine Lösung bekannt ist.

Eine natürliche Zahl ${}k$ heißt Teiler einer natürlichen Zahl ${}n$, wenn es eine weitere natürliche Zahl ${}m$ gibt mit ${}n=km$.

Definition

Eine natürliche Zahl ${}n\geq 2$ heißt eine Primzahl, wenn die einzigen natürlichen Teiler von ihr ${}1$ und ${}n$ sind.

Die ersten Primzahlen sind

$2,3,5,7,11,13,17,19,23,\ldots .$

Jede natürliche Zahl lässt sich als ein Produkt von Primzahlen schreiben, z.B. ist ${}100=2\cdot 2\cdot 5\cdot 5$. Dies ist ein Satz der elementaren Zahlentheorie. Ein anderer wichtiger Satz geht auf Euklid zurück und besagt, dass es unendlich viele Primzahlen gibt. Der Beweis dafür ist ein Widerspruchsbeweis.

Satz

Es gibt unendlich viele Primzahlen.

Beweis

Angenommen, die Menge aller Primzahlen sei endlich, sagen wir ${}\{p_{1},p_{2},\ldots ,p_{r}\}$. Man betrachtet die Zahl

${}N=p_{1}\cdot p_{2}\cdot p_{3}{\cdots }p_{r}\ +1\,.$

Diese Zahl ist durch keine der Primzahlen ${}p_{i}$ teilbar, da bei Division von ${}N$ durch ${}p_{i}$ immer ein Rest ${}1$ verbleibt. Damit sind die Primfaktoren von ${}N$, die es nach Fakt ***** geben muss, nicht in der Ausgangsmenge enthalten - Widerspruch.

$\Box$

Dieser Satz ist für den handwerklichen, alltagstauglichen Umgang mit den natürlichen Zahlen nicht besonders wichtig, er macht aber eine wichtige Aussage über die Natur der natürlichen Zahlen. Der Beweis ist recht einfach nachvollziehbar, aber es ist nicht unmittelbar klar, wie man einen solchen Beweis findet. Man beachte auch, dass es durchaus möglich ist, in einem endlichen Text Aussagen über die Unendlichkeit zu formulieren und zu beweisen.

Es gibt nun in der Mathematik, insbesondere in der Zahlentheorie, einfach zu formulierende und leicht zu verstehende Aussagen, von denen man bis heute nicht weiß, ob sie wahr oder falsch sind. Dazu geben wir einige prominente Beispiele.

Das Goldbach-Problem

Problem

Gibt es für jede gerade natürliche Zahl ${}n\geq 4$ Primzahlen ${}p$ und ${}q$ mit

${}n=p+q\,?$

Die Frage ist also, ob man jede gerade natürliche Zahl ab ${}4$ als Summe von zwei Primzahlen schreiben kann. Dies kann wahr oder falsch sein, diese Eigenschaft kann gelten oder nicht. Bisher ist es aber niemandem gelungen, diese Eigenschaft zu beweisen oder zu widerlegen. Man spricht von einem offenen Problem. Die sogenannte Goldbachsche Vermutung besagt, dass dieses Problem eine positive Antwort besitzt. Es ist eine treibende Kraft in der Mathematik, eine Vermutung zu bestätigen (zu beweisen) oder zu widerlegen.

Für jede gegebene gerade Zahl ${}n\geq 4$ lässt sich in endlich vielen Schritten entscheiden, ob sie eine Summe von zwei Primzahlen ist. Dazu überprüft man einfach der Reihe nach die ungeraden Zahlen${}k<n$, ob sie und der komplementäre Summand${}n-k$ Primzahlen sind. Falls es ein solches Paar ${}(k,n-k)$ gibt, hat man die Goldbacheigenschaft für diese eine Zahl ${}n$ bestätigt. Für alle geraden Zahlen ${}n\geq 4$, für die diese Eigenschaft überprüft wurde, hat man stets solche Primsummanden gefunden. Inzwischen sind alle Zahlen bis zur Größenordnung ${}10^{18}$ überprüft. Zum Beispiel ist (es gibt im Allgemeinen mehrere Darstellungen)

$4=2+2,\,6=3+3,\,8=3+5,\,10=5+5=3+7,\,12=5+7,\,14=3+11=7+7,\,16=3+13=5+11,\,etc.$

Doch solche rechnerischen Ergebnisse sagen letztlich nichts über die Gültigkeit der Goldbachschen Vermutung aus, bei der es ja nicht darum geht, für möglichst viele und große Zahlen zu zeigen, dass die Goldbacheigenschaft gilt, sondern für alle.

Grundsätzlich gibt es mehrere Möglichkeiten, wie diese Frage beantwortet werden könnte. Der einfachste Fall wäre, wenn man eine konkrete gerade Zahl ${}n\geq 4$ angibt und von dieser zeigt, dass sie nicht die Summe von zwei Primzahlen ist. Der Beweis dafür wäre dann eventuell sehr lang, man müsste alle möglichen Summanden überprüfen, aber ansonsten anspruchslos. Dann wäre die Goldbachvermutung falsch. Es ist auch denkbar, dass man zeigt, dass es eine Zahl geben muss, die die Goldbacheigenschaft nicht erfüllt, ohne eine solche konkret anzugeben. Dann wäre die Goldbachvermutung ebenfalls falsch, ein solcher Beweis könnte beliebig kompliziert sein. Oder man zeigt, das es für jede gerade Zahl ${}n\geq 4$ eine Summendarstellung mit zwei Primzahlen geben muss, wobei ein solcher Beweis wieder beliebig kompliziert sein könnte und die Goldbachsche Vermutung beweisen würde. Oder man zeigt sogar, wie man zu einem jeden ${}n$ ein Primzahlsummandenpaar explizit berechnen kann.

Mersenne-Primzahlen

Marin Mersenne (1588-1648)

Definition

Eine Primzahl der Form ${}2^{n}-1$ heißt Mersennesche Primzahl.

Generell nennt man die Zahl ${}M_{n}=2^{n}-1$ die ${}n$-te Mersenne-Zahl. Mit dieser Bezeichnung sind die Mersenne-Primzahlen genau diejenigen Mersenne-Zahlen, die Primzahlen sind. Die Mersennezahl ${}M_{n}=2^{n}-1$ hat im Dualsystem eine Entwicklung, die aus genau ${}n$ Einsen besteht. Die ersten Mersenne-Primzahlen sind

$2^{2}-1=3,2^{3}-1=7,2^{5}-1=31,2^{7}-1=127.$

Die Zahl ${}2^{11}-1=2047=23\cdot 89$ ist die erste Mersenne-Zahl, wo der Exponent zwar prim (der Exponent einer Mersenne-Primzahl muss selbst eine Primzahl sein, siehe Lemma 13.2 (Zahlentheorie (Osnabrück 2008))) ist, die aber selbst keine Mersenne-Primzahl ist. Dies wurde 1536 von Hudalrichus Regius (Walter Hermann Ryff) gezeigt. Der nächste Kandidat, nämlich ${}2^{13}-1=8191$, ist wieder prim. Bis ca. 1950 war bekannt, dass für die Exponenten

$2,3,5,7,13,17,19,31,61,89,107{\text{ und }}127$

Mersenne-Primzahlen vorliegen, und keine weiteren unterhalb dem Exponenten ${}258$. Von verschiedenen Leuten, unter anderem von Cataldi und Mersenne selbst, wurden falsche Behauptungen aufgestellt. Ab ca. 1950 kamen Computer zum Bestimmen von Mersenne-Primzahlen zum Einsatz, und es wurden bisher insgesamt ${}47$ Mersenne-Primzahlen gefunden. Alle größten bekannten Primzahlen sind Mersenne-Zahlen. Das liegt daran, dass es für diese Zahlen einen vergleichsweise einfachen Primzahltest gibt, nämlich den Lucas-Lehmer-Test. Mit diesem Test wird etwa alle zwei Jahre eine neue größte Primzahl gefunden. Eine Rekordliste findet sich unter Mersenne-Primzahlen auf Wikipedia.

Das Auffinden von großen (Mersenne)-Primzahlen, also der konkrete Nachweis, dass eine bestimmte Zahl diese Eigenschaft besitzt, ist aber etwas anderes als der Existenznachweis, dass es innerhalb oder oberhalb gewisser Schranken solche Zahlen gibt oder dass es überhaupt nur endlich oder unendlich viele solcher Zahlen gibt. Aufgrund des Satzes von Euklid weiß man, dass es jenseits jeder beliebig großen natürlichen Zahl noch Primzahlen gibt. Für Mersenne-Primzahlen ist das unbekannt.

Problem

Gibt es unendlich viele Mersenne-Primzahlen?

Wie gesagt, dies ist unbekannt, es wird aber vermutet, dass es unendlich viele gibt.

Primzahlzwillinge

Definition

Ein Primzahlzwilling ist ein Paar bestehend aus ${}p$ und ${}p+2$, wobei diese beiden Zahlen Primzahlen sind.

Die ersten Beispiele für Primzahlzwillinge sind

$(3,5),\,(5,7),\,(11,13),\,(17,19),\,(29,31),\ldots .$

Übrigens ist ${}3,5,7$ der einzige Doppel-Primzahlzwilling, siehe Aufgabe *****.

Problem

Gibt es unendlich viele Primzahlzwillinge?

Der große Fermat und der Satz von Wiles

Aus dem siebzehnten Jahrhundert stammt das Problem, ob die Fermat-Gleichungen

${}x^{n}+y^{n}=z^{n}\,$

für alle ${}n\geq 3$ nur triviale ganzzahlige Lösungen, bei denen ${}x=0$ oder ${}y=0$ ist, besitzen. Die entsprechende Fermatsche Vermutung, der sogenannte „Große Fermat“, galt lange Zeit als das berühmteste offene Problem der Mathematik. Nach rund 350 Jahren wurde der Große Fermat schließlich 1995 von Andrew Wiles bewiesen.

Andrew Wiles (*1953)

Satz

Die diophantische Gleichung

${}x^{n}+y^{n}=z^{n}\,$

besitzt für kein ${}n\geq 3$ eine ganzzahlige nichttriviale Lösung.

Mathematik-geschichtlich gesprochen kann man sagen, dass mathematische Probleme sehr hartnäckig sind, aber früher oder später doch gelöst werden. Beispielsweise wurden alle Probleme der antiken Mathematik im Laufe des 19. Jahrhunderts gelöst. Eine wichtige geschichtliche Beobachtung ist auch, dass die Lösungen zwar auch mit individuellen Höchstleistungen zusammenhängen, aber doch stark von der allgemeinen Entwicklung des mathematischen Apparats abhängen. Viele elementar formulierbare Probleme wurden nicht elementar bewiesen, sondern erst durch neue komplexe Theorien und Methoden, die neue Sichtweisen auf das Problem ermöglichten.

Eine solche geschichtliche Beobachtung trägt aber nichts zu der Frage bei, ob es eine allgemeine Lösungsstratgie für mathematische Probleme geben könnte.

Helfen Maschinen?

Betrachten wir das Goldbach-Problem und nehmen wir für einen Moment an, dass die Goldbachsche Vermutung nicht stimmt, dass es also eine gerade natürliche Zahl ${}\geq 4$ gibt, die nicht die Summe von zwei Primzahlen ist. Ein Computer, eine Rechenmaschine, nennen wir sie ${}M_{1}$, die der Reihe nach alle geraden Zahlen auf die Goldbach-Eigenschaft überprüft, wird früher oder später auch diese Zahl erreichen und feststellen, dass sie nicht diese Eigenschaft besitzt und wird damit die Vermutung widerlegen.

Nehmen wir nun an, dass die Goldbachsche Vermutung stimmt, und dass es dafür einen Beweis gibt, der in „normaler Sprache“ formuliert werden kann. Eine zweite Rechenmaschine ${}M_{2}$ drucke nach und nach alle möglichen Texte (in aufsteigender Länge) aus. Nehmen wir an, dass ${}M_{2}$ erkennen kann, ob ein Text aus sinnvollen Wörtern und Sätzen besteht, ob es sich um einen korrekten mathematischen Beweis handelt und ob dieser die Goldbachsche Vermutung beweist. Dann wird ${}M_{2}$ früher oder später einen Beweis für die Goldbachsche Vermutung ausgeben und dieses auch erkennen.

Da wir nicht wissen, ob die Goldbachsche Vermutung wahr ist oder nicht, kombinieren wir die beiden Maschinen zu einer einzigen Maschine ${}M$, die abwechselnd die ${}M_{1}$-Funktion und die ${}M_{2}$-Funktion ausführt. D.h., dass ${}M$ abwechselnd eine Zahl überprüft, ob sie der Goldbachschen Vermutung widerspricht, und sodann einen Text überprüft, ob er einen Beweis für die Goldbachsche Vermutung beinhaltet. Da die Goldbachsche Vermutung wahr oder falsch ist, wird früher oder später ${}M$ ein Gegenbeispiel oder einen Beweis finden und somit das Problem entscheiden. Vorausgesetzt, dass es für jede wahre Aussage einen (maschinell überprüfbaren) Beweis gibt.

Universelle Lösungsverfahren

Wir haben anhand einiger Beispiele gesehen, dass man mit sehr elementaren Mitteln offene Probleme formulieren kann, für die Mathematiker trotz jahrhundertelanger Bemühungen keine Antwort finden konnten. Zugleich gab es ähnliche Fragen, die lange Zeit offen waren, und dann irgendwann „plötzlich“ gelöst werden konnten.

Alles in allem ist die Lösung von mathematischen Problemen ein extrem zäher Prozess. Warum hatte Wiles den Schlüssel zum Fermatproblem, aber nicht auch zu den drei anderen oben genannten Problemen? Wird es irgendwann einmal einen Menschen geben, der alle bis dahin offenen Probleme lösen kann? Gibt es außerirdische Intelligenz, die alle mathematischen Probleme lösen kann?

In dieser Vorlesung soll es um eine Variante dieser Fragestellung gehen, nämlich um die Frage, ob es eine universelle Strategie geben kann, mit der man sämtliche mathematische Probleme angehen könnte, oder zumindest solche, die sich für die natürlichen Zahlen in einfacher Weise formulieren lassen. Von einer solchen Strategie würde man die folgenden Eigenschaften erwarten.

1. Die Strategie ist fixiert (durch einen endlichen Text, ein Programm, eine Maschine).
2. Die Strategie ist deterministisch und ist nicht auf neue Einfälle, Intuition, Genialität angewiesen.
3. Sie führt, angesetzt auf jedes Problem, zu einer (richtigen) Lösung.
4. Dabei braucht die Durchführung der Strategie nur endlich viele Schritte (die Anzahl der benötigten Schritte darf vom Problem abhängen).

Ramon Llull (1232-1316)

Gottfried Wilhelm Leibniz (1646-1716)

Die Präzisierung dieser Idee führt zu der Frage, ob es einen Algorithmus geben kann, der alle (zahlentheoretischen) Probleme löst. In vielen mathematischen Teilbereichen gibt es solche Algorithmen, z.B. das eingangs erwähnte Addieren oder Multiplizieren von natürlichen Zahlen, die Bestimmung, ob eine vorgegebene natürliche Zahl eine Primzahl ist, das Lösen von linearen Gleichungssystemen, u.s.w. Ein solcher universeller Algorithmus bzw. eine Maschine, worauf dieser universelle Algorithmus läuft, wäre sicher eine Sensation und würde die mathematische Welt enorm verändern. Selbst dann, wenn er so aufwändig wäre, dass er nie in der Zeitspanne eines Menschen (oder des Universums) zu einem einzigen Resultat gelangen würde, so wäre doch allein schon der Nachweis der prinzipiellen Existenz eine gewaltige theoretische Erkenntnis. Gedanken zu einer solchen Maschine finden sich bei Llull und bei Leibniz.

In dieser Vorlesung werden wir mathematisch beweisen, dass es einen solchen universellen Algorithmus nicht geben kann, und zwar noch nicht einmal für den Bereich der natürlichen Zahlen. Dies ist einer der Hauptsätze von Kurt Gödel. Wichtig ist an dieser Stelle zu betonen, dass es sich dabei um mathematische Sätze handelt, nicht um philosophische Sätze, auch wenn sie erkenntnistheoretisch interpretiert werden können. Es gibt auch keinen philosophischen Ersatz für diese Sätze, etwa im Sinne, „weil die Welt komplex und die Sprache unscharf ist gibt es immer Probleme“. Das wäre etwa so, wie wenn man die Relativitätstheorie mit den Worten „alles ist relativ“ gleichsetzt. Das eine ist eine mathematisch-physikalische Theorie, das andere ein nichtssagender Allgemeinplatz.

Obwohl die Unvollständigkeitssätze deutliche Schranken für die maschinelle Entscheidbarkeit und Beweisbarkeit von mathematischen Sätzen setzen, gibt es auch starke Resultate, die besagen, dass viele mathematische Tätigkeiten maschinell durchführbar sind. Der ebenfalls auf Gödel zurückgehende Vollständigkeitssatz sagt, dass Beweise für Sätze der „ersten Stufe“ als eine formale Ableitung aus Axiomen realisiert werden können, und dass damit die Korrektheit von Beweisen grundsätzlich mechanisch überprüft werden kann und dass alle korrekten Beweise mechanisch aufzählbar sind. Das oben am Beispiel der Goldbachschen Vermutung angedachte Aufzählungsprinzip für mathematische Beweise ist also prinzipiell realistisch (ein Problem dabei ist, dass die natürlichen Zahlen nicht einstufig axiomatisierbar sind, siehe Satz 12.11).

Die Behandlung der Ergebnisse von Gödel setzt mehrere mathematische Präzisierungen voraus: Eine axiomatische Präzisierung der natürlichen Zahlen, eine Präzisierung der mathematischen Sprache, in der mathematische Aussagen formuliert werden können, eine Präzisierung von Beweis, eine Präzisierung von Algorithmus (mit Hilfe von rekursiven Funktionen, Turing-Maschine, Registermaschine, etc.). Dies alles ist der Inhalt der folgenden Vorlesungen.

Fußnoten

Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)