Beweis (Mathematik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Beispielhafter, schematischer Aufbau eines Beweises

Ein Beweis ist in der Mathematik die als fehlerfrei anerkannte Herleitung der Richtigkeit bzw. der Unrichtigkeit einer Aussage aus einer Menge von Axiomen, die als wahr vorausgesetzt werden, und anderen Aussagen, die bereits bewiesen sind. Um den Beweis klar vom gültigen Schluss zu unterscheiden, spricht man auch vom axiomatischen Beweis.

Umfangreichere Beweise von mathematischen Sätzen werden in der Regel in mehrere kleine Teilbeweise aufgeteilt, siehe dazu Satz und Hilfssatz.

In der Beweistheorie, einem Teilgebiet der mathematischen Logik, werden Beweise formal als Ableitungen aufgefasst und selbst als mathematische Objekte betrachtet, um etwa die Beweisbarkeit oder Unbeweisbarkeit von Sätzen aus gegebenen Axiomen selbst zu beweisen.

Konstruktive und nicht-konstruktive Beweise[Bearbeiten]

Bei einem konstruktiven Existenzbeweis wird entweder die Lösung selbst genannt, deren Existenz zu zeigen ist, oder ein Verfahren angegeben, das zur Lösung führt, das heißt, es wird eine Lösung konstruiert.

Bei einem nicht-konstruktiven Beweis wird anhand von Eigenschaften auf die Existenz einer Lösung geschlossen. Manchmal wird sogar indirekt die Annahme, es gäbe keine Lösung, zum Widerspruch geführt, woraus folgt, dass es eine Lösung gibt. Aus solchen Beweisen geht nicht hervor, wie man die Lösung gewinnt.

Ein einfaches Beispiel soll dies verdeutlichen.

Behauptung: Die Funktion f mit f(x) = 2x - 1 besitzt im Intervall [0,1] eine Nullstelle x_0.

Konstruktiver Beweis: Sei x_0 = 0{,}5. Dann gilt f(x_0) = 2\cdot x_0 - 1 = 2\cdot 0{,}5 - 1 = 1 - 1 = 0. Ferner liegt x_0 = 0{,}5 im Intervall [0,1]. Damit ist die Behauptung bewiesen. Die Nullstelle ist sogar mit x_0 = 0{,}5 angegeben.

Nicht-konstruktiver Beweis: f ist stetig. Ferner ist f(0) = -1 < 0 und f(1) = 1 > 0. Nach dem Zwischenwertsatz für stetige Funktionen folgt die Behauptung. Über den Wert der Nullstelle liefert dieser Beweis jedoch keine Information.

Beweismethoden[Bearbeiten]

Einige mathematische Sätze oder logische Schlussregeln lassen sich für eine Vielzahl von Beweisen einsetzen und beeinflussen die Struktur des Beweises besonders stark. Die systematische Vorgehensweise zur Anwendung dieser bezeichnet man dann als Beweismethode, Beweisverfahren, Beweistechnik oder Beweisprinzip. Die Gültigkeit einer Beweismethode bedarf selbst eines Beweises, im Rahmen der Axiome und der Logik gültig zu sein (etwa ist die Reductio ad absurdum (s. u.) in der Grundform nicht in intuitionistischer Logik, und eine transfinite Induktion über alle Kardinalzahlen nur unter Voraussetzung des Wohlordnungssatzes möglich). Hier eine Auswahl von Standard-Beweismethoden:

Reductio ad absurdum[Bearbeiten]

Hauptartikel: Reductio ad absurdum

Bei einem indirekten Beweis (Reductio ad absurdum, Widerspruchsbeweis) zeigt man, dass ein Widerspruch entsteht, wenn die zu beweisende Behauptung falsch wäre. Dazu nimmt man an, dass die Behauptung falsch ist, und wendet dann die gleichen Methoden wie beim direkten Beweis an. Wenn daraus ein Widerspruch entsteht, dann kann die Behauptung nicht falsch sein, also muss sie richtig sein (Satz vom ausgeschlossenen Dritten). Wichtige (und keinesfalls selbstverständliche!) Voraussetzung für die Gültigkeit eines Widerspruchsbeweises ist, dass im zugrunde liegenden System die Aussage nicht zugleich wahr und falsch sein kann (Widerspruchsfreiheit).

Ein klassisches Beispiel eines Widerspruchsbeweises ist der euklidische Beweis dafür, dass es unendlich viele Primzahlen gibt.

Einfache Beweise, die sich dieser Möglichkeit der Schlussfolgerung nicht bedienen, werden in Abgrenzung davon als direkte Beweise bezeichnet. Ein Beispiel:

Behauptung 1: Das Quadrat einer ungeraden natürlichen Zahl n ist stets ungerade.

Beweis: Es sei n eine ungerade natürliche Zahl. Dann lässt sich n darstellen als n = 2k + 1, wobei k eine natürliche Zahl oder Null ist. Daraus folgt mit Hilfe der ersten binomischen Formel

n^2 = (2k+1)^2 = 4k^2+4k+1 = 2 \cdot (2k^2+2k)+1.

Aus der Möglichkeit, n^2 so darzustellen folgt, dass n^2 ungerade ist.

Nun ein Beispiel für eine reductio ad absurdum, wobei die vorherige Behauptung verwendet wird:

Behauptung 2: Ist die Wurzel aus einer geraden natürlichen Zahl n eine natürliche Zahl, so ist diese gerade.

Beweis: Angenommen, \sqrt{n} = k wäre ungerade. Dann ist wegen der bereits bewiesenen Behauptung 1 auch k^2 = n ungerade, und das ist ein Widerspruch zu der Voraussetzung, dass n gerade ist. Also ist die getroffene Annahme falsch, das heißt, \sqrt{n} ist gerade.

Ein weiteres klassisches Beispiel:

Behauptung 3: Die Zahl \sqrt{2} ist irrational.

Beweis: Angenommen, diese Zahl wäre rational. Dann kann man sie als Bruch \sqrt{2} = \tfrac{l}{k} darstellen, wobei l und k natürliche Zahlen und ohne Beschränkung der Allgemeinheit teilerfremd sind (sonst kann man den Bruch soweit kürzen, bis das der Fall ist). Daraus folgt durch Quadrieren

2 = \frac{l^2}{k^2} \, , also \, l^2 = 2 k^2.

Folglich ist l^2 eine gerade Zahl. Da die Wurzel aus einer geraden Quadratzahl auch gerade ist (Behauptung 2), ist l selbst gerade, also ist \tfrac{l}{2} eine natürliche Zahl. Durch Umformung der letzten Gleichung erhält man

k^2 = \frac{l^2}{2} = 2 \cdot \left(\frac{l}{2}\right)^2.

Das zeigt, dass k^2 und somit auch k gerade natürliche Zahlen sind. Also sind l und k beide gerade und haben somit beide den Teiler 2. Damit sind l und k nicht teilerfremd – im Widerspruch zu der Annahme ihrer Teilerfremdheit. Also ist auch die ursprüngliche Annahme, \sqrt{2} sei rational, falsch.

Vollständige Induktion[Bearbeiten]

Veranschaulichung der vollständigen Induktion

Der Beweis durch vollständige Induktion ist ein oft angewendetes Verfahren zum Beweis von Sätzen der Form „Für jede natürliche Zahl n gilt ...“. Dazu zeigt man zuerst, dass die Aussage für n = 0 (oder auch einen anderen Anfangswert n_0) gilt, und danach, dass sie immer auch für n+1 gilt, wenn sie für ein n gilt. Die vollständige Induktion lässt sich mit einem Domino-Effekt veranschaulichen. Man stellt die Steine so auf, dass, wenn einer umfällt, auch immer der nächste umfällt (nn+1), und stößt den ersten Stein um (n = 0).

Ein einfaches Beispiel:

Behauptung: Es gilt für alle natürlichen Zahlen n: 1 + 3 + \ldots + (2n+1) = (n+1)^2

Beweis:

  1. Die Behauptung gilt für n = 0: (2\cdot 0+1) = 1 = (0+1)^2 ist eine wahre Aussage.
  2. Die Behauptung sei für ein n gültig. Für n+1 untersucht man die Summe
   1 + 3 + ... + (2n+1) + (2n+3)
   Da die Behauptung für n gültig ist, folgt
   1 + 3 + ... + (2n+1) + (2n+3) = (n+1)^2 + (2n+3) = (n+1)^2 + 2(n+1) + 1 = ((n+1) + 1)^2

Also gilt die Behauptung auch für n+1, damit ist die Aussage nach dem Induktionsprinzip bewiesen.

Vollständige Fallunterscheidung[Bearbeiten]

Beim Beweis einer Aussage durch vollständige Fallunterscheidung wird eine endliche Anzahl von Fällen betrachtet, die in ihrer Gesamtheit alle möglichen Fälle überdecken und von denen jeder eine einfachere Behandlung des Problems ermöglicht.

Behauptung: Jede Primzahl p \ge 3 hat die Form p = 4 \cdot k \pm 1 mit einer natürlichen Zahl k.

Beweis: Man unterscheidet folgende vier Fälle für die Zahl p, von denen immer genau einer eintritt:

  1. p = 4k
  2. p = 4k + 1
  3. p = 4k + 2
  4. p = 4k + 3 = 4(k+1) - 1

Im ersten dieser Fälle ist p durch 4 teilbar und damit keine Primzahl, im dritten Fall ist p durch 2 teilbar und somit ebenfalls keine Primzahl. Also muss einer der Fälle zwei oder vier eintreten, das heißt p hat die Form p = 4 \cdot k \pm 1 mit einer natürlichen Zahl k.

Es sei angemerkt, dass die Fallunterscheidung zwar vollständig sein muss, aber die untersuchten Fälle sich nicht gegenseitig ausschließen müssen.

Diagonalverfahren[Bearbeiten]

Die Diagonalverfahren wurden von Georg Cantor zum Beweis zweier spezieller Aussagen entwickelt. Sie haben sich seitdem als allgemeine Beweismethoden bewährt.

Das erste Cantorsche Diagonalverfahren ist ein direkter Beweis für die Abzählbarkeit einer Menge. Es wird gezeigt, dass man jedem Element der zu untersuchenden Menge eine natürliche Zahl zuordnen kann.

Das zweite Cantorsche Diagonalverfahren ist ein indirekter Beweis für die Überabzählbarkeit einer Menge. Es wird also das Gegenteil angenommen, nämlich dass die Menge abzählbar sei. Dann wird aus dieser Annahme ein Widerspruch hergeleitet, sodass sie fallen gelassen werden muss.

Schubfachprinzip[Bearbeiten]

Das Schubfachprinzip geht auf den deutschen Mathematiker Dirichlet zurück und kann sehr anschaulich formuliert werden: Verteilt man n+1 Gegenstände auf n Schubfächer, dann befinden sich in mindestens einem Schubfach mindestens zwei Gegenstände.

Transfinite Induktion[Bearbeiten]

Bei der transfiniten Induktion wird die vollständige Induktion auf beliebige wohlgeordnete Klassen verallgemeinert.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

 Wikibooks: Mathe für Nicht-Freaks: Beweis – Lern- und Lehrmaterialien
 Wikibooks: Beweisarchiv – Lern- und Lehrmaterialien