Mathematische Grundlagen

Beweistechniken

Ein Satz bezeichnet in der Mathematik eine wichtige mathematische Aussage, worunter wir zunächst informell eine Behauptung verstehen wollen, die entweder wahr oder falsch sein kann. Beispiele hierfür sind "7 ist eine gerade Zahl" (diese Behauptung ist falsch) oder "Wasser ist nass" (diese Behauptung ist richtig). Die Richtigkeit eines solchen Satzes ist häufig nicht so offensichtlich wie bei den vorangegangenen Beispielen und muss deshalb in der Regel bewiesen werden. Unter einem Beweis verstehen wir dabei die fehlerfreie und nachvollziehbare Herleitung einer Aussage, die in eindeutiger und unanfechtbarer Weise entweder die Richtigkeit oder Unrichtigkeit dieser Aussage zeigt.

Weil Beweise in der Mathematik eine außerordentlich wichtige Rolle spielen, werden im Folgenden zunächst einige der gängigsten Beweistechniken vorgestellt.

Um mathematische Sätze zu beweisen, bedarf es in der Regel viel Erfahrung und Kreativität. Nachdem ein Beweis geführt, also die Aussage eines Satzes erfolgreich bewiesen wurde, schließt man einen Beweis häufig mit den Worten "quod erat demonstrandum" (q.e.d.) ab. Dies ist lateinisch und bedeutet soviel wie "was zu beweisen war". Zurückzuführen ist diese Floskel auf berühmte griechische Mathematiker der Antike wie Euklid und Archimedes, die ihre Beweise auf diese Weise abschlossen (natürlich mit der entsprechenden griechischen Übersetzung). Heutzutage verwendet man statt dieses Ausdrucks häufig das Zeichen \(\square\), welches auf den amerikanischen Mathematiker Paul Halmos (1916-2006) zurückgeht.

Direkte Beweise

Bei direkten Beweisen beginnen wir mit bestimmten Voraussetzungen und leiten daraus schrittweise die Behauptung her. Wir zeigen die Richtigkeit der zu beweisenden Aussage dabei direkt. Mathematisch ausgedrückt haben direkte Beweise somit die Form \(A \Rightarrow B\), wobei \(A\) die Voraussetzungen sind und \(B\) die Aussage darstellt, die bewiesen werden soll. Der Implikationspfeil \(\Rightarrow\) bedeutet dabei, dass \(B\) aus \(A\) folgt. Man spricht dies "\(A\) impliziert \(B\)" oder "aus \(A\) folgt \(B\)" oder "wenn \(A\), dann \(B\)" aus.

Beispiel: Direkte Beweise

1. Sei \(x \in \mathbb{R}\) mit \(x \lt 0\). Dann gilt \(-x \gt 0\).
   Beweis: Wir beweisen die Aussage durch einen einfachen Dreisatz, indem wir auf beiden Seiten -x addieren: \(x \lt 0 \Leftarrow\Rightarrow x + (-x) \lt -x \Leftarrow\Rightarrow 0 \lt -x. \square\)


2. Sei \(n \in \mathbb{N}\). Dann ist \(n + (n + 1) + (n + 2)\) durch 3 teilbar.
   Beweis: Nach Voraussetzung sein \(n\) eine natürliche Zahl. Damit ist auch \(n + 1\) eine natürliche Zahl. Für eine beliebige natürliche Zahl \(k \in \mathbb{N}\) gilt, dass \(3 \cdot k\) durch 3 teilbar ist. Daraus folgt, dass auch \(3 \cdot (n + 1)\) durch 3 teilbar ist. Wegen \(3 \cdot (n + 1) = 3n + 3 = n + n + n + 1 + 2 = n + (n + 1) + (n + 2)\) folgt somit die Behauptung. \(\square\)


3. Sei \(n \in \mathbb{N}\) eine ungerade Zahl. Dann ist \(n^2\) ebenfalls eine ungerade Zahl.
   Beweis: Nach Voraussetzung sei \(n\) eine ungerade natürliche Zahl. Dann können wir \(n\) darstellen als \(n = 2k + 1\) mit einem \(k \in \mathbb{N}_0\). Damit folgt \(n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2 \cdot (2k^2 + 2k) + 1\) und weil \(2 \cdot (2k^2 + 2k)\) eine gerade natürliche Zahl (oder 0) ist, muss \(n^2\) folglich ungerade sein. \(\square\)

Beweise durch Widerspruch

Gelegentlich ist es schwierig, für eine Behauptung \(B\) einen direkten Beweis der Form \(A \Rightarrow B\) zu finden. Manchmal kann es einfacher sein, die Aussage durch einen Widerspruch zu beweisen. Man spricht dabei auch von indirekten Beweisen. Hierzu geht man wie folgt vor: Es gelte die Voraussetzung \(A\) und man nimmt an, \(B\) sei falsch. Im Beweis zeigt man nun, dass die Annahme \(B\) sei falsch nicht stimmen kann. Daraus folgt, dass \(B\) richtig sein muss. Beweise durch Widerspruch basieren somit auf den Gesetzen der Logik. Sie stützen sich darauf, dass aus einer wahren Aussage \(A\) niemals eine falsche Aussage \(B\) folgen kann.

Beispiel: Beweise durch Widerspruch

1. Sei \(n \in \mathbb{N}\) eine gerade natürliche Zahl mit \(\sqrt{n} \in \mathbb{N}\). Dann ist \(\sqrt{n}\) ebenfalls eine gerade Zahl.
   Beweis: Angenommen, \(\sqrt{n}\) wäre ungerade. Wir haben im vorherigen Beispiel zu den direkten Beweisen gesehen, dass das Quadrat von ungeraden Zahlen ebenfalls ungerade ist. Somit würde folgen, dass \(\sqrt{n}^2 = n\) ebenfalls ungerade ist. Dies ist aber ein Widerspruch zur Voraussetzung, dass \(n\) eine gerade Zahl ist. Folglich ist die Annahme \(\sqrt{n}\) wäre ungerade falsch. \(\square\)


2. Seien \(a, b \in \mathbb{R}^+\). Dann gilt \(\frac{a + b}{2} \geq \sqrt{ab}\).
   Beweis: Angenommen, es würde gelten \(\frac{a + b}{2} \lt \sqrt{ab}\). Dann folgt:
   

   	\(\frac{a + b}{2}\)	\(\lt\)	\(\sqrt{ab}\)
   \(\Rightarrow\)	\(a + b\)	\(\lt\)	\(2 \cdot \sqrt{ab}\)
   \(\Rightarrow\)	\((a + b)^2\)	\(\lt\)	\(4ab\)
   \(\Rightarrow\)	\(a^2 + b^2 + 2ab\)	\(\lt\)	\(4ab\)
   \(\Rightarrow\)	\(a^2 + b^2 - 2ab\)	\(\lt\)	\(0\)
   \(\Rightarrow\)	\((a - b)^2\)	\(\lt\)	\(0\)

   Das Quadrat einer reellen Zahl kann allerdings niemals negativ sein. Somit ist die Annahme \(\frac{a + b}{2} \lt \sqrt{ab}\) falsch. \(\square\)

Beweise durch Kontraposition

Eine weitere beliebte Beweismethode ist der Beweis durch Kontraposition. Dieser Ansatz basiert auf den Gesetzen der Logik. Anstatt eine Aussage der Form \(A \Rightarrow B\) zu beweisen, führt man einen Beweis für den negierten Ausdruck. Das bedeutet, man zeigt nicht, dass aus der Aussage \(A\) die Aussage \(B\) folgt, sondern stattdessen, dass aus der Aussage "nicht \(B\)" die Aussage "nicht \(A\)" folgt. Die Negation, formal geschrieben als \(\lnot B \Rightarrow \lnot A\), ist logisch äquivalent zu \(A \Rightarrow B\) und gelegentlich leichter zu beweisen als die ursprüngliche Aussage. Bei Beweisen durch Kontraposition nimmt man also an, dass \(\lnot B\) gilt, und folgert daraus die Richtigkeit von \(\lnot A\).

Beispiel: Beweise durch Kontraposition

1. Sei \(n \in \mathbb{N}\). Wenn \(n^2\) eine ungerade Zahl ist, dann ist auch \(n\) ungerade.
   Beweis: Wir beweisen diese Behauptung durch Kontraposition. Die Negation der Aussage lautet: Wenn \(n\) nicht ungerade ist, dann ist auch \(n^2\) nicht ungerade. Anders ausgedrückt: Wenn \(n\) gerade ist, so ist auch \(n^2\) gerade.
   Sei hierzu \(n\) eine gerade natürliche Zahl. Dann können wir \(n\) darstellen als \(n = 2k\) mit einer natürlichen Zahl \(k \in \mathbb{N}\). Damit folgt \(n^2 = 2^2 \cdot k^2 = 2 \cdot 2 \cdot k^2 = 2k' \text{ mit } k' := 2k^2\). Offenbar ist \(k'\) eine gerade natürliche Zahl und somit auch \(2k'\). Wegen \(n^2 = 2k'\) folgt damit, dass auch \(n^2\) eine gerade natürliche Zahl ist. \(\square\)

Beweis durch Ringschluss

Häufig stehen wir vor der Aufgabe, mehrere äquivalente Aussagen zu beweisen, die sich alle aus einer gemeinsamen Voraussetzung ergeben. Wir müssen dann beispielsweise zeigen, dass Aussagen \(A1, A2 \text{ und } A3\) äquivalent sind und gleichermaßen gelten, wenn eine Voraussetzung \(A\) erfüllt ist. Hierzu könnten wir die Richtigkeit von \(A\) voraussetzen und dann jeweils \(A1 \Rightarrow A2, A2 \Rightarrow A1, A1 \Rightarrow A3, A3 \Rightarrow A1, A2 \Rightarrow A3 \text{ und } A3 \Rightarrow A2\) beweisen.
Das ist jedoch sehr umständlich, weil wir hierzu viele verschiedene Einzelschritte beweisen müssen. Wenn weitere Aussagen hinzukommen, erhöht sich der Aufwand drastisch. Ein effizienteres Vorgehen ist die Anwendung eines Ringschlusses. Hierzu zeigen wir einfach, dass \(A1 \Rightarrow A2, A2 \Rightarrow A3 \text{ und } A3 \Rightarrow A1\) gilt. Dadurch können wir jede Aussage aus jeder anderen folgern, indem wir einfach den Implikationspfeilen folgen. \(A2\) folgt z.B. aus \(A3\) über \(A3 \Rightarrow A1 \Rightarrow A2\).

Beweise durch vollständige Induktion

Das Prinzip der vollständigen Induktion ist ein sogenanntes Axiom, d.h. eine unbeweisbare Grundtatsache. Es dient dazu, eine Aussage für alle natürlichen Zahlen - also für unendlich viele Elemente - zu beweisen. Es besteht aus zwei Schritten: dem Induktionsanfang und dem Induktionsschritt. Die Idee dahinter ist mit dem Domino-Effekt vergleichbar: Im ersten Schritt - dem Induktionsanfang - zeigt man, dass die Aussage, die bewiesen werden soll, für das erste betrachtete Element gilt. Nachdem dies gezeigt wurde, wird dann im Induktionsschritt sukzessive bewiesen, dass die Aussage auch immer für ein nachfolgendes Element gelten muss, wenn sie für das vorhergehende Element gilt. Aus der Richtigkeit der Aussage für das erste Element folgt dann die Richtigkeit der Aussage für das zweite Element, aus der Richtigkeit der Aussage für das zweite Element folgt die Richtigkeit der Aussage für das dritte Element usw. Dadurch entsteht eine (unendlich lange) Kette an Beweisschritten und man beweist die Aussage indirekt für unendlich viele Elemente, ohne dabei jedes einzelne explizit zu betrachten.

Mathematisch präziser lässt sich die vollständige Induktion wie folgt beschreiben:

Sei \(m \in \mathbb{N}_0\) fest gewählt und sei \(A(n)\) eine Aussage für alle \(n \in \mathbb{N}_0\) mit \(n \geq m\). Das Prinzip der vollständigen Induktion besagt: Wenn

1. Induktionsanfang: Die Aussage \(A(m)\) ist richtig
2. Induktionsschritt: Ist für \(n \geq m\) die Aussage \(A(n)\) richtig, so ist auch \(A(n + 1)\) richtig

Der Induktionsanfang stellt dabei sicher, dass die Aussage für das allererste Element \(A(m)\) richtig ist. Im Induktionsschritt nimmt man dann jeweils an, dass die Aussage für \(A(n)\) richtig ist und folgert daraus die Richtigkeit der Aussage für \(A(n + 1)\). Aus der Richtigkeit von \(A(m)\) (die wir im Induktionsanfang bewiesen haben) können wir somit die Richtigkeit von \(A(m + 1)\) folgern. Aus der Richtigkeit von \(A(m + 1)\) können wir dann die Richtigkeit von \(A(m + 2)\) folgern usw. Diese Kette können wir beliebig fortsetzen (nämlich für alle \(n \geq m\)) und damit muss folglich gelten, dass die Aussage \(A(n)\) für alle Elemente \(n \geq m\) richtig ist.

Beispiel: Beweise durch vollständige Induktion

1. Sei \(n \in \mathbb{N}\). Für alle \(n \geq 2\) gilt \(4n + 1 \gt 2n + 2\).
   Beweis:
   Induktionsanfang: Für \(n = 2\) ist die Aussage wegen \(4 \cdot 2 + 1 = 9 \gt 6 = 2 \cdot 2 + 2\) offenbar richtig.
   Induktionsschritt: Wir nehmen an, dass \(4n + 1 \gt 2n + 2\) richtig ist und müssen zeigen, dass dann auch \(4(n + 1) + 1 \gt 2(n + 1) + 2\) richtig ist. Wegen \(4n + 1 \gt 2n + 2\) ist auch \(4n + 1 + 4 \gt 2n + 2 + 4\) und damit gilt \(4(n + 1) + 1 = 4n + 4 + 1 = 4n + 1 + 4 \gt 2n + 2 + 4 \gt 2n + 2 + 2 = 2(n + 1) + 2\). Somit folgt die Behauptung. \(\square\)


2. Sei \(n \in \mathbb{N}\). Für alle \(n \geq 2\) gilt \(n^2 \geq 2n\).
   Beweis:
   Induktionsanfang: Für \(n = 2\) ist die Aussage wegen \(2^2 = 4 \geq 4 = 2 \cdot 2\) offenbar richtig.
   Induktionsschritt: Wir nehmen an, dass \(n^2 \geq 2n\) richtig ist und müssen zeigen, dass dann auch \((n + 1)^2 \geq 2(n + 1)\) richtig ist. Wegen der Annahme, dass \(n^2 \geq 2n\) ist, folgt \((n + 1)^2 = n^2 + 2n + 1 \geq 2n + 2n + 1 = 4n + 1\). Mit dem vorangegangenen Beweis gilt \(4n + 1 \gt 2n + 2 \text{ für } n \geq 2\). Damit folgt insgesamt \((n + 1)^2 \geq 4n + 1 \gt 2n + 2 = 2(n + 1)\). Somit gilt die Behauptung. \(\square\)