Beweisverfahren

Ein mathematischer Beweis ist eine lückenlose Kette von logischen Schlüssen, die zeigt, dass eine Behauptung wahr ist. Jeder Schritt muss sich aus Annahmen, Definitionen oder schon bewiesenen Sätzen ergeben. Wenn die Kette hält, steht das Ergebnis für alle Zeiten fest. Das unterscheidet die Mathematik von den Naturwissenschaften, in denen Theorien durch Messungen nur bestätigt, aber nie endgültig bewiesen werden.

Ein paar Beispiele reichen nicht als Beweis. Der Term n² + n + 41 liefert für n = 0, 1, 2, … bis 39 lauter Primzahlen. Trotzdem stimmt „immer eine Primzahl“ nicht. Auf dieser Seite lernst du, wie ein Beweis aufgebaut ist und welche Verfahren es gibt. Die Grundlagen der Logik dazu (Implikation, Kontraposition, Quantoren) stehen auf der Seite Aussagenlogik. Hier wendest du sie an.

Was ist ein Beweis? Beispiel, Messen und Beweis

Zeichnest du ein Dreieck und misst die Winkel, kommen vielleicht 180° heraus. Das ist ein Hinweis, aber kein Beweis. Du hast ein einziges Dreieck gemessen, und Messungen haben immer kleine Fehler. Ein Beweis dagegen gilt für alle Dreiecke gleichzeitig und ohne Ungenauigkeit. Er arbeitet mit Begriffen, nicht mit Zeichnungen.

Woher stammen die Startpunkte? Aus Axiomen und Definitionen. Axiome sind Grundannahmen, die man ohne Beweis akzeptiert, zum Beispiel: Durch zwei verschiedene Punkte geht genau eine Gerade. Definitionen legen fest, was ein Wort bedeutet, etwa: Eine Zahl heißt gerade, wenn sie sich als 2 · k mit einer ganzen Zahl k schreiben lässt. Alles Weitere wird daraus gefolgert. Sätze, die bewiesen sind, dürfen später selbst als Bausteine dienen.

Der direkte Beweis

Beim direkten Beweis startest du bei der Voraussetzung und gehst über logische Zwischenschritte geradewegs zur Behauptung. Das ist das einfachste Verfahren. Ein Beispiel zum Aufwärmen:

Der entscheidende Trick ist, „gerade“ und „ungerade“ algebraisch aufzuschreiben (2k und 2k + 1). Dann kannst du rechnen.

Beweis durch Kontraposition

Manchmal ist der direkte Weg unhandlich. Dann hilft ein Umweg über die Logik: Die Aussage „Wenn A, dann B“ ist gleichwertig mit „Wenn nicht B, dann nicht A“. Das ist die Kontraposition. Statt A → B beweist du also ¬B → ¬A. Warum das erlaubt ist, zeigt die Wahrheitstafel auf der Seite zur Aussagenlogik.

Beweis durch Widerspruch

Beim Widerspruchsbeweis (lateinisch reductio ad absurdum) nimmst du an, die Behauptung sei falsch. Dann folgerst du daraus Schritt für Schritt etwas, das offensichtlich nicht stimmen kann, etwa 1 = 2 oder „eine Zahl ist gerade und ungerade zugleich“. Weil jeder Schritt korrekt war, muss die Annahme falsch gewesen sein. Also stimmt die Behauptung. Dieses Verfahren gehört zu den berühmtesten Methoden der Mathematik.

Beispiel 1: √2 ist irrational

Eine Zahl ist irrational, wenn sie sich nicht als Bruch zweier ganzer Zahlen schreiben lässt. Die Behauptung: √2 ist irrational.

1. Annahme (Gegenteil): √2 ist rational, also √2 = p/q mit ganzen Zahlen p und q. Wir dürfen den Bruch vollständig gekürzt annehmen, p und q haben also keinen gemeinsamen Teiler.
2. Quadrieren: 2 = p²/q², also p² = 2q². Daher ist p² gerade.
3. Nach Satz 3 ist dann auch p gerade, etwa p = 2r.
4. Einsetzen: (2r)² = 2q², also 4r² = 2q² und q² = 2r². Also ist q² gerade und nach Satz 3 auch q.
5. Widerspruch: p und q sind beide gerade, haben also den gemeinsamen Teiler 2. Das widerspricht der Annahme, dass der Bruch gekürzt ist.

Die Annahme war falsch, also ist √2 irrational. ∎ Beachte, wie Satz 3 aus dem vorigen Abschnitt hier als Baustein dient. Die Geschichte dieser Entdeckung steht auf der Seite über Pythagoras, die Sage um Hippasos weiter unten.

Beispiel 2: Es gibt unendlich viele Primzahlen

Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist. Die Behauptung: Es gibt unendlich viele davon.

1. Annahme: Es gibt nur endlich viele Primzahlen, nämlich p₁, p₂, …, p_n.
2. Bilde N = p₁ · p₂ · … · p_n + 1. Diese Zahl ist größer als 1, hat also einen Primteiler q.
3. Dieser Primteiler q muss in der Liste vorkommen, denn sie enthält ja alle Primzahlen. Dann teilt q das Produkt p₁ · … · p_n und auch N. Also teilt q den Unterschied N − (p₁ · … · p_n) = 1.
4. Widerspruch: Keine Primzahl teilt 1.

Also gibt es unendlich viele Primzahlen. ∎ Euklid hat das um 300 v. Chr. in seinen Elementen als Satz IX.20 bewiesen, und zwar etwas anders formuliert: Er zeigte, dass jede endliche Liste von Primzahlen zu kurz ist. Mehr dazu auf der Seite Euklid. Die Zahl N muss dabei übrigens nicht selbst prim sein: 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30.031 = 59 · 509.

Das Gegenbeispiel

Wie widerlegst du eine Behauptung, die für alle Zahlen gelten soll? Ein einziges Beispiel, bei dem sie nicht stimmt, genügt. Das nennt man ein Gegenbeispiel. Es ist die Verneinung einer Allaussage: Das Gegenteil von „Für alle x gilt …“ ist „Es gibt ein x, für das … nicht gilt“.

Das Beispiel zeigt eine wichtige Regel: Beispiele können beweisen, dass etwas nicht gilt, aber nie, dass etwas immer gilt. Weitere Gegenbeispiele: „Alle Primzahlen sind ungerade“ scheitert an der 2. „Wenn a² = b², dann a = b“ scheitert an a = 3 und b = −3.

Die Fallunterscheidung

Bei der Fallunterscheidung teilst du alle möglichen Fälle in endlich viele Gruppen auf und beweist die Behauptung in jeder Gruppe einzeln. Wichtig ist, dass die Fälle zusammen alle Möglichkeiten abdecken.

Der Äquivalenzbeweis: beide Richtungen

Soll gezeigt werden, dass zwei Aussagen gleichwertig sind („A genau dann, wenn B“), musst du beide Richtungen beweisen: „⇒“ (A → B) und „⇐“ (B → A). Wer nur eine Richtung zeigt, hat nur die Hälfte bewiesen.

Existenzbeweise: konstruktiv und nicht konstruktiv

Manchmal soll bewiesen werden, dass es etwas gibt. Ein konstruktiver Existenzbeweis nennt das Objekt: „Es gibt eine Primzahl über 100“, denn 101 ist eine. Ein nicht konstruktiver Beweis zeigt nur, dass es das Objekt geben muss, ohne es anzugeben. Ein berühmtes Beispiel: Gibt es irrationale Zahlen a und b, für die a^b rational ist? Betrachte √2^√2. Ist diese Zahl rational, sind wir fertig mit a = b = √2. Ist sie irrational, nimm a = √2^√2 und b = √2. Dann ist a^b = (√2^√2)^√2 = √2² = 2, rational. In beiden Fällen gibt es ein Paar, nur weiß man nach dem Beweis nicht, welcher Fall zutrifft. Ein Beispiel für einen ganz anderen Existenzbeweis ist Cantors Diagonalverfahren, das auf der Seite Mengenlehre erklärt wird.

Ausblick: vollständige Induktion

Für Aussagen über alle natürlichen Zahlen gibt es ein weiteres Verfahren, die vollständige Induktion. Man zeigt, dass die Aussage für die erste Zahl gilt, und dass sie von jeder Zahl auf die nächste „weitergereicht“ wird, wie eine Reihe umfallender Dominosteine. So beweist man zum Beispiel 1 + 2 + … + n = n(n + 1)/2 für alle n. Wie das genau funktioniert, mit Beispielen und typischen Fehlern, erklärt die Seite Vollständige Induktion.

Tipps zum Aufschreiben

• Schreibe zuerst Voraussetzung und Behauptung getrennt auf.
• Übersetze Begriffe in Formeln (gerade: 2k, ungerade: 2k + 1, teilbar durch 3: 3k).
• Begründe jeden Schritt. Schreibe dazu, warum er gilt („nach Satz 2“, „Definition gerade“).
• Wähle das Verfahren nach der Aussage. Kommt in der Behauptung „nicht“ oder „irrational“ vor, probiere den Widerspruch. Ist die Voraussetzung schwer zu nutzen, probiere die Kontraposition.
• Beende den Beweis klar mit ∎, damit der Leser weiß: Jetzt ist es geschafft.
• Prüfe mit einem Beispiel, ob die Behauptung plausibel ist. Ein Beispiel ersetzt den Beweis nicht, entdeckt aber falsche Behauptungen früh.

Übungen

Geschichte: Vom Beweis des Thales zum Computer

In Ägypten und Babylon rechnete man mit erprobten Regeln und Beispielen, ausdrückliche Beweise im heutigen Sinn sind aus dieser Zeit kaum überliefert. Der Überlieferung nach war Thales von Milet (um 600 v. Chr.) einer der Ersten, der mathematische Aussagen durch Überlegung statt durch bloße Erfahrung begründete. Was von ihm tatsächlich stammt, ist nicht gesichert, denn er hinterließ nichts Schriftliches.

Die Griechen machten daraus ein System. Euklid stellte um 300 v. Chr. in den Elementen die Geometrie auf wenige Axiome und Definitionen und leitete daraus Satz für Satz ab. Dieses Vorbild prägte das Beweisen über 2.000 Jahre. Um 1900 setzte David Hilbert es fort: Mit dem Hilbertprogramm wollte er die gesamte Mathematik auf endlich viele Axiome stützen und ihre Widerspruchsfreiheit sichern. 1931 zeigte Kurt Gödel mit seinen Unvollständigkeitssätzen, dass das nicht geht: In jedem hinreichend starken und widerspruchsfreien Axiomensystem gibt es Aussagen, die sich weder beweisen noch widerlegen lassen.

Auch die Länge von Beweisen ist gewachsen. Andrew Wiles bewies 1994 den Großen Fermatschen Satz, der gut 350 Jahre offen war. Eine Lücke im ersten Entwurf schloss er zusammen mit seinem früheren Doktoranden Richard Taylor. Sein Beweis in den Annals of Mathematics (1995) umfasst über 100 Seiten und setzt tiefe moderne Theorien voraus. Ungelöste Fragen wie die der Millennium-Probleme stehen im Magazinbeitrag Die Millennium-Probleme einfach erklärt.

Computergestützte Beweise

1976 bewiesen Kenneth Appel und Wolfgang Haken den Vier-Farben-Satz: Vier Farben genügen, um jede Landkarte so zu färben, dass benachbarte Länder verschiedene Farben haben. Ein Computer prüfte dafür knapp 2.000 Grundkonfigurationen einzeln durch, was kein Mensch von Hand nachvollziehen konnte. Es entstand die Frage: Ist das noch ein Beweis? Heute prüfen Beweisassistenten wie Lean oder Coq jeden Schritt eines Beweises formal. Der Vier-Farben-Satz wurde 2005 so bestätigt. Mehr dazu in der Epoche Mathematik im 21. Jahrhundert.

Häufige Fragen

Warum reichen Beispiele nicht als Beweis?

Weil es unendlich viele Möglichkeiten gibt und ein Gegenbeispiel irgendwo auf dich warten kann. Das Beispiel n² + n + 41 und Fermats Vermutung zu 2²ⁿ + 1 zeigen es.

Was ist der Unterschied zwischen Kontraposition und Widerspruchsbeweis?

Bei der Kontraposition beweist du direkt die gleichwertige Aussage ¬B → ¬A. Beim Widerspruchsbeweis nimmst du A und ¬B gleichzeitig an und leitest einen Widerspruch her.

Darf man die Behauptung am Anfang des Beweises benutzen?

Nein, sonst ist es ein Zirkelschluss. Nur beim Widerspruchsbeweis nimmst du ihr Gegenteil bewusst an, um es zu widerlegen.

Wozu braucht man Beweise?

Sie machen Aussagen sicher, auch dort, wo Zeichnungen und Beispiele täuschen. Auf bewiesenen Sätzen baut die ganze weitere Mathematik auf.

Quellen und weiterführende Literatur

• Wikipedia: Beweis (Mathematik)
• Albrecht Beutelspacher: Das ist o.B.d.A. trivial!, Springer Spektrum.
• Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise, Springer, Berlin.
• MacTutor History of Mathematics: Euclid of Alexandria (englisch)
• MacTutor History of Mathematics: Andrew Wiles (englisch)