Beweis (Mathematik)
Ein Beweis ist in der Mathematik der formal korrekte Nachweis, dass aus einem Satz von Aussagen eine weitere Aussage folgt.Hierbei existieren unter anderem drei Methoden, nach denen ein Beweis in der Mathematik durchgeführt werden kann:
- der direkte Beweis
- der indirekte Beweis bzw. Beweis durch Widerspruch
- sowie die (vollständige) Induktion bzw. "Schluss von n auf n+1"
Table of contents |
2 Der indirekte Beweis (Widerspruchsbeweis) 3 Die vollständige Induktion 4 Konstruktiver und nicht-konstruktiver Beweis 5 Siehe auch 6 Weblinks |
Beim direkten Beweis wird die Behauptung durch Folgerungen, Ausrechnen ... bewiesen.
Einige einfache Beispiele:
Satz 1
Beweis: Wir schreiben die Summe zweimal untereinander und addieren spaltenweise:
Daraus folgt: 2 * S(n) = n * (n+1)
Dividiert man beide Seiten durch 2 erhält man die Behauptung.
Der direkte Beweis
Behauptung: S(n) = 1 + 2 + 3 + ... + n = n*(n+1)/2 S(n) = 1 + 2 + ... + (n-1) + n
S(n) = n + (n-1) + ... + 2 + 1
-------------------------------------------------
S(n) + S(n) = (n+1) + (n+1) + ... + (n+1) + (n+1)
Zu diesem Beweis gibt es eine Anekdote: Eines Tages hatte der Mathematiklehrer von Carl Friedrich Gauß keine Lust, Unterricht zu halten. Daher gab er den Schülern die Aufgabe, die Zahlen von 1 bis 100 zusammenzuzählen. Kaum hatte es sich der Lehrer gemütlich gemacht und die Zeitung aufgeschlagen, da meldete sich der 7-jährige Gauss und legte das Ergebnis vor. Gauss hatte das Ergebnis nach der obigen Methode errechnet.
Satz 2
Behauptung: Das Quadrat einer geraden natürlichen Zahl n ist gerade.
Beweis: Sei n eine gerade natürliche Zahl. Dann lässt sich n eindeutig darstellen als n = 2k, wobei k eine natürliche Zahl ist. Daraus folgt: . ist daher durch 4 teilbar, also gerade.
Satz 3
Behauptung: Das Quadrat einer ungeraden natürlichen Zahl n ist ungerade.
Beweis: Sei n eine ungerade natürliche Zahl. Dann lässt sich n eindeutig darstellen als n = 2k + 1, wobei k eine natürliche Zahl ist. Daraus folgt mit Hilfe der 1. binomischen Formel: . Die beiden ersten Summanden sind gerade. Also ist ungerade.
Beim indirekten Beweis nimmt man an, dass das Gegenteil der Behauptung wahr ist. Danach führt man diese Aussage mit den gleichen Methoden wie beim direkten Beweis zum Widerspruch, weswegen man diese Methode auch Beweis durch Widerspruch nennt.
Ein klassisches Beispiel hierfür ist der Nachweis, dass es unendlich viele Primzahlen gibt.
Wir zeigen einige weitere Beispiele.
Satz 4
Beweis:
Wir nehmen an, sei ungerade. Dann ist wegen Satz 3 auch ungerade - ein Widerspruch.
Satz 5
Beweis:
Wir nehmen an, sei gerade. Dann ist wegen Satz 2 auch gerade - ein Widerspruch.
Beweis:
Wir nehmen an, sei rational.
Dann kann man darstellen als Bruch
Der indirekte Beweis (Widerspruchsbeweis)
Behauptung: Die Wurzel aus einer geraden natürlichen Quadratzahl n ist gerade.
Behauptung: Die Wurzel aus einer ungeraden natürlichen Quadratzahl n ist ungerade.
Satz 6
Behauptung: Die Zahl ist irrational. = n / k
wobei n und k natürliche Zahlen und teilerfremd sind.
Daraus folgt durch quadrieren: . Folglich ist eine gerade Zahl.
Da die Wurzel aus einer geraden Quadratzahl auch gerade ist (Satz 4), muss n selbst gerade sein. Also ist n/2 eine natürliche Zahl.
Nun formen wir die letzte Gleichung um:
.Das zeigt, dass und somit auch k gerade natürliche Zahlen sind. n und k sind also gerade, haben also beide den Teiler 2. Damit sind n und k nicht teilerfremd - im Widerspruch zu der Annahme. Also ist die Annahme, sei rational, falsch.
Der Beweis durch vollständige Induktion ist ein beliebtes Verfahren zum Beweisen von Aussagen, die auf allen natürlichen Zahlen definiert sind (Die Methode lässt sich aber auch für andere Mengen verallgemeinern). Man zeigt zuerst, dass die Aussage für n=0 gilt, und danach, dass sie auch für n+1 gilt, wenn sie für n gilt. Die vollständige Induktion lässt sich mit einem Dominoeffekt vergleichen. Man stellt die Steine so auf, dass wenn einer umfällt auch der nächste umfällt (n → n+1) und stößt den ersten Stein um (n=0).
Ein einfaches Beispiel:
Satz 7
Beweis:
Natürlich braucht man nicht unbedingt mit n=0 anzufangen; wenn man z. B. eine Aussage beweisen will, die für alle n5 gilt (wie beispielsweise die Ungleichung ), dann fängt man am besten mit n=5 an.
Eine Verallgemeinerung der Induktion auf natürlichen Zahlen ist die transfinite Induktion, die z. B. auf Ordinalzahlen durchführbar ist.
Beim Beweis von Existenz-Sätzen unterscheidet man zwischen einem konstruktiven Beweis und einem nicht-konstruktiven Beweis.
Bei einem konstruktiven Beweis wird entweder die Lösung selbst genannt oder ein Verfahren angegeben, das zur Lösung führt: 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, daß 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(x) = 2x - 1 besitzt im Intervall [0,1] eine Nullstelle x0.
Konstruktiver Beweis: Sei x0 = 0,5. Dann gilt: f(x0) = 2·x0 - 1 = 2·0,5 - 1 = 1 - 1 = 0. Ferner liegt x0 = 0,5 im Intervall [0,1]. Damit ist die Behauptung bewiesen.
Nicht-konstruktiver Beweis: f(x) ist stetig. Ferner ist f(0) = -1 < 0 und f(1) = 1 > 0. Nach dem Zwischenwertsatz für stetige Funktionen folgt die Behauptung.Die vollständige Induktion
Behauptung: A(n): 1 + 3 + ... + (2n+1) = (n+1)²
Somit ist die Behauptung bewiesen.
A(n+1): 1 + 3 + ... + (2n+1) + (2n+3) = ((n+1) + 1)²
Da die Behauptung für n gültig ist, folgt
1 + 3 + ... + (2n+1) + (2n+3) = (n+1)² + (2n+3) = (n+2)² = ((n+1) + 1)²Konstruktiver und nicht-konstruktiver Beweis