Beweis (Mathematik)

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Ein Beweis ist in der Mathematik der formal korrekte Nachweis, dass aus einer Menge von Aussagen und Axiomen 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. der Beweis durch Widerspruch
die (vollständige) Induktion

Inhaltsverzeichnis

1 Der direkte Beweis
2 Der indirekte Beweis (Widerspruchsbeweis)
3 Die vollständige Induktion
- 3.1 Satz 7
- 3.2 Satz 8
4 Konstruktiver und nicht-konstruktiver Beweis
5 Siehe auch
6 Literatur
7 Weblinks

[Bearbeiten] Der direkte Beweis

Beim direkten Beweis wird die Behauptung durch Anwenden von bewiesenen Aussagen und durch logische Folgerungen bewiesen.

Einige einfache Beispiele:

[Bearbeiten] Satz 1

Behauptung: $S(n) := 1 + 2 + 3 + ... + n = \frac{n \cdot (n+1)}{2}$

Beweis: Wir schreiben die Summe zwei Mal untereinander und addieren spaltenweise:

         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)

Daraus folgt

$2 \cdot S(n) = n \cdot (n+1)$ .

Dividiert man beide Seiten durch 2, erhält man die Behauptung.

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 9-jährige Gauß und legte das Ergebnis vor. Gauß hatte das Ergebnis nach der obigen Methode errechnet.

[Bearbeiten] Satz 2

Behauptung: Das Quadrat jeder geraden natürlichen Zahl n ist gerade.

Beweis: Sei n eine gerade natürliche Zahl. Dann lässt sich n darstellen als $n = 2 k$ , wobei k eine natürliche Zahl ist. Daraus folgt:

$n^2 = (2k)^2 = (2k)\cdot (2k) = 4 \cdot k^2 = 2 \cdot (2 \cdot k^2)$ .

$n 2$ ist daher das Doppelte einer natürlichen Zahl (Ausdruck in Klammern; sogar dieser ist bereits gerade) und damit gerade.

[Bearbeiten] 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 darstellen als $n = 2 k + 1$ , wobei k eine natürliche Zahl oder Null ist. Daraus folgt mit Hilfe der 1. binomischen Formel:

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

Aus dieser Darstellung folgt, dass $n 2$ ungerade ist.

[Bearbeiten] Der indirekte Beweis (Widerspruchsbeweis)

Beim indirekten Beweis zeigt man, dass ein Widerspruch entstünde, wenn die zu beweisende Behauptung falsch wäre (deshalb nennt man diese Methode auch Beweis durch Widerspruch oder reductio ad absurdum). Dazu verwendet man die gleichen Methoden wie beim direkten Beweis. Wenn nun die Behauptung nicht falsch sein kann, muss sie richtig sein (tertium non datur). Wichtige (und keinesfalls selbstverständliche!) Voraussetzung für die Gültigkeit eines Widerspruchbeweises ist, dass im zugrundeliegenden System die Aussage nicht gleichzeitig wahr und falsch sein kann (Widerspruchsfreiheit).

Ein klassisches Beispiel eines Widerspruchsbeweises ist der Nachweis, dass es unendlich viele Primzahlen gibt.

Wir zeigen einige weitere Beispiele.

[Bearbeiten] Satz 4

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

Beweis: Wir nehmen an, $\sqrt{n} = k$ sei ungerade. Dann ist wegen Satz 3 auch $k 2 = n$ ungerade – ein Widerspruch.

[Bearbeiten] Satz 5

Behauptung: Die Wurzel aus einer ungeraden natürlichen Quadratzahl n ist ungerade.

Beweis: Wir nehmen an, $\sqrt{n} = k$ sei gerade. Dann ist wegen Satz 2 auch $k 2 = n$ gerade – ein Widerspruch.

[Bearbeiten] Satz 6

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

Beweis: Wir nehmen an, $\sqrt{2}$ sei rational. Dann kann man $\sqrt{2}$ darstellen als Bruch

$\sqrt{2} = \frac{l}{k}$ ,

wobei l und k natürliche Zahlen und o. B. d. A. teilerfremd sind. Daraus folgt durch Quadrieren:

$2 = \frac{l^2}{k^2} \Leftrightarrow l^2 = 2 k^2$ .

Folglich ist $l 2$ eine gerade Zahl. Da die Wurzel aus einer geraden Quadratzahl auch gerade ist (Satz 4), ist l selbst gerade. Also ist l/2 eine natürliche Zahl. Nun formen wir die letzte Gleichung um:

$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. l und k sind also gerade und haben somit beide den Teiler 2. Damit sind l und k nicht teilerfremd – im Widerspruch zu der Annahme. Also ist die Annahme, $\sqrt{2}$ sei rational, falsch.

[Bearbeiten] Die vollständige Induktion

Der Beweis durch vollständige Induktion ist ein beliebtes Verfahren zum Beweisen von Allsätzen über natürliche Zahlen, das heißt, Sätze der Form "Für jede natürliche Zahl n gilt... ". (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:

[Bearbeiten] Satz 7

Behauptung: A(n): 1 + 3 + ... + (2n+1) = (n+1)²

Beweis:

A(0): (2*0+1) = 1 = (0+1)², eine wahre Aussage.
Die Behauptung sei für ein beliebiges n gültig. Für n+1 erhalten wir

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)²

Somit ist die Behauptung bewiesen.

Natürlich braucht man nicht unbedingt mit n=0 anzufangen; wenn man z. B. eine Aussage beweisen will, die für alle $n \geq 5$ gilt (wie beispielsweise die Ungleichung $2 n > n 2$ ), dann fängt man am besten mit n=5 an:

[Bearbeiten] Satz 8

Behauptung: Für alle $n\geq 5$ gilt A(n): $2 n > n 2$ .

Beweis:

A(5): $25 = 32 > 5 2 = 25$ , eine wahre Aussage.
Die Behauptung sei für ein beliebiges $n\geq 5$ gültig.

Wegen $n\geq 3$ gilt $(n+1)^2 = n^2+2\cdot n+1 \leq n^2 + (n-1)\cdot n+1 = 2\cdot n^2-n+1 \leq 2\cdot n^2-2 < 2\cdot n^2$ .

Da die Behauptung für n gültig ist, folgt somit

$2^{n+1} = 2\cdot 2^n>2\cdot n^2 > (n+1)^2$ , d.i. A(n+1).

Somit ist die Behauptung bewiesen. Wohlgemerkt wurde die Beweis hier nur für alle $n\geq 5$ erbracht. Es gilt zwar zusätzlich auch A(0) und A(1), aber hier greift der Induktionsschritt nicht (in der Tat sind A(2), A(3), A(4) falsch!). Umgekehrt würde der Induktionsschritt schon für $n\geq 3$ funktionieren, aber hier fehlt ihm der Induktionsanfang.

Eine Verallgemeinerung der Induktion auf natürlichen Zahlen ist die transfinite Induktion, die auf wohlgeordneten Mengen (oder Klassen), und insbesondere auf den Ordinalzahlen durchführbar ist. Eine andere in der Theoretischen Informatik und Graphentheorie übliche Verallgemeinerung ist die strukturelle Induktion: hier werden in induktiv definierten Strukturen Aussagen bewiesen, indem man diese induktiv nach dem Aufbau der Struktur beweist.

[Bearbeiten] Konstruktiver und nicht-konstruktiver Beweis

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, 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(x) = 2x - 1 besitzt im Intervall [0,1] eine Nullstelle x₀.

Konstruktiver Beweis: Sei x₀ = 0,5. Dann gilt: f(x₀) = 2·x₀ - 1 = 2·0,5 - 1 = 1 - 1 = 0. Ferner liegt x₀ = 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.

[Bearbeiten] Siehe auch

„o. E. d. A.“ (oft auch nur kurz: oE ("ohne Einschränkung")) und „o. B. d. A.“ sind gebräuchliche Abkürzungen für „ohne Einschränkung der Allgemeinheit“ bzw. „ohne Beschränkung der Allgemeinheit“.
Beweis (Logik)
Wohlfundierte Induktion

[Bearbeiten] Literatur

Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise, Springer, ISBN 3-540-40185-7

[Bearbeiten] Weblinks

Die Zeit: Obst in Formeln (zur Problematik eines Beweises mit Computer)
Zusammenfassung der Beweismethoden für Schüler
Zusammenfassung der wichtigsten Beweise der Schulmathematik

Von „http://de.wikipedia.org../../../b/e/w/Beweis_%28Mathematik%29_bfac.html“

Kategorien: Mathematik | Logik