Direkter und indirekter Beweis – „Mathe für Nicht-Freaks“

Es gibt zwei wichtige Arten von Beweisen: direkte Beweise und indirekte Beweise (auch Widerspruchsbeweise genannt).

Beim direkten Beweis wird der zu beweisende Satz ${\displaystyle S}$ direkt bewiesen. Dies bedeutet, dass man mit den Voraussetzungen von ${\displaystyle S}$ beginnt und aus diesen die zu beweisende Aussage direkt durch logische Schlussfolgerungen herleitet. Ein direkter Beweis nimmt also folgende Form an:

${\displaystyle {\begin{array}{c}{\text{Prämissen und Voraussetzungen von }}S\\{\color {Orange}|}\\{\color {Orange}{\text{logische Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\{\text{Konklusion von }}S\end{array}}}$

Betrachten wir ein Beispiel. Stelle dir vor, wir müssen den Satz

beweisen. Dieser Satz lässt sich folgendermaßen als Implikation formulieren:

In dieser Implikation ist „${\displaystyle n}$ ist eine natürliche Zahl“ die Prämisse und „${\displaystyle n+(n+1)+(n+2)}$ ist durch 3 teilbar“ die Konklusion. Ein direkter Beweis hätte also folgende Form:

${\displaystyle {\begin{array}{c}n{\text{ ist eine natürliche Zahl.}}\\{\color {Orange}|}\\{\color {Orange}{\text{logische Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\n+(n+1)+(n+2){\text{ ist durch 3 teilbar.}}\end{array}}}$

Ein solcher Beweis könnte so aussehen (Implikationen der logischen Schlussfolgerungen sind orange):

${\displaystyle {\begin{array}{c}n{\text{ ist eine natürliche Zahl.}}\\{\color {Orange}|}\\{\color {Orange}{\text{Wenn }}n{\text{ eine natürliche Zahl ist, dann ist auch }}n+1{\text{ eine natürliche Zahl.}}}\\{\color {Orange}\downarrow }\\n+1{\text{ ist eine natürliche Zahl.}}\\{\color {Orange}|}\\{\color {Orange}{\text{Ist }}k{\text{ eine natürliche Zahl, dann ist }}3\cdot k{\text{ durch 3 teilbar.}}}\\{\color {Orange}\downarrow }\\3\cdot (n+1){\text{ ist durch 3 teilbar.}}\\{\color {Orange}|}\\{\color {Orange}3\cdot (n+1)=3\cdot n+3}\\{\color {Orange}\downarrow }\\3\cdot n+3{\text{ ist durch 3 teilbar.}}\\{\color {Orange}|}\\{\color {Orange}3\cdot n+3=n+n+n+1+2=n+(n+1)+(n+2)}\\{\color {Orange}\downarrow }\\n+(n+1)+(n+2){\text{ ist durch 3 teilbar.}}\end{array}}}$

Anstatt deinen Beweis so wie obigen zu strukturieren, kannst du ihn auch als Fließtext schreiben (dies ist meistens kompakter):

Neben dem direkten Beweis gibt es eine zweite Art des Beweises, den Widerspruchsbeweis oder indirekten Beweis. Wenn du einen mathematischen Satz ${\displaystyle S}$ indirekt beweisen möchtest, so führst du seine Negation ${\displaystyle \neg S}$ durch logische Schlussfolgerungen zu einem Widerspruch. Dabei nenne ich im Folgendem ${\displaystyle \neg S}$ Widerspruchsannahme. Ein Widerspruchsbeweis hat also folgende Form:

${\displaystyle {\begin{array}{c}{\text{Widerspruchsannahme }}\neg S\\{\color {Orange}|}\\{\color {Orange}{\text{logische Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\{\text{Widerspruch}}\end{array}}}$

Um einen Widerspruchsbeweis erfolgreich durchzuführen, musst du zunächst den zu beweisenden Satz ${\displaystyle S}$ richtig negieren. Wie du dies machen kannst, kannst du im Abschnitt „Aussagen negieren“ nachlesen.

Doch wie haben wir den Satz ${\displaystyle S}$ bewiesen, wenn wir die Widerspruchsannahme ${\displaystyle \neg S}$ zu einem Widerspruch geführt haben? Wenn du die Widerspruchsannahme ${\displaystyle \neg S}$ zu einem Widerspruch geführt hast, so weißt du, dass ${\displaystyle \neg S}$ falsch sein muss, also ${\displaystyle \neg S=\mathrm {F} }$ ist. Damit ist die doppelte Verneinung ${\displaystyle \neg \neg S}$ von ${\displaystyle S}$ wahr (${\displaystyle \neg \neg S=\neg \mathrm {F} =W}$). Nun ist ${\displaystyle \neg \neg S\Leftrightarrow S}$ eine Tautologie, was du an folgender Wahrheitstabelle erkennst:

${\displaystyle S}$	${\displaystyle \neg S}$	${\displaystyle \neg \neg S}$	${\displaystyle \neg \neg S\Leftrightarrow S}$
${\displaystyle \mathrm {W} }$	${\displaystyle \mathrm {F} }$	${\displaystyle \mathrm {W} }$	${\displaystyle \mathrm {W} }$
${\displaystyle \mathrm {F} }$	${\displaystyle \mathrm {W} }$	${\displaystyle \mathrm {F} }$	${\displaystyle \mathrm {W} }$

Da ${\displaystyle \neg \neg S\Leftrightarrow S}$ eine Tautologie ist, ist ${\displaystyle \neg \neg S}$ dann und nur dann wahr, wenn ${\displaystyle S}$ wahr ist (siehe Definition der Äquivalenz). Wir haben durch den Widerspruchsbeweis bewiesen, dass ${\displaystyle \neg \neg S}$ wahr ist (da ${\displaystyle \neg S}$ falsch ist). Damit muss aber wegen obiger Tautologie ${\displaystyle S}$ wahr sein. Genau dies ist zu zeigen, wenn wir den Satz ${\displaystyle S}$ beweisen wollen.

Stelle dir vor, wir wollen den Satz

durch einen Widerspruchsbeweis beweisen (diesen Satz haben wir bereits oben direkt bewiesen). Diesen Satz können wir als Implikation definieren:

Um diese Implikation indirekt zu beweisen, müssen wir zunächst die Widerspruchsannahme formulieren, also die obige Implikation negieren. Wir erhalten:

Diese Annahme müssen wir nun durch logische Schlussfolgerungen zu einem Widerspruch führen. Eine solche Herleitung könnte so aussehen:

${\displaystyle {\begin{array}{c}{\text{Widerspruchsannahme: }}n{\text{ ist eine natürliche Zahl und}}\\n+(n+1)+(n+2){\text{ ist nicht durch 3 teilbar.}}\\{\color {Orange}|}\\{\color {Orange}{\text{Ist }}A\land B{\text{ wahr, so ist }}A{\text{ wahr.}}}\\{\color {Orange}\downarrow }\\n+(n+1)+(n+2){\text{ ist nicht durch 3 teilbar.}}\\{\color {Orange}|}\\{\color {Orange}n+(n+1)+(n+2)=3\cdot n+3}\\{\color {Orange}\downarrow }\\3\cdot n+3{\text{ ist nicht durch 3 teilbar.}}\\{\color {Orange}|}\\{\color {Orange}3\cdot n+3=3\cdot (n+1)}\\{\color {Orange}\downarrow }\\3\cdot (n+1){\text{ ist nicht durch 3 teilbar.}}\\{\color {Orange}|}\\{\color {Orange}{\text{Ist }}3\cdot k{\text{ nicht durch 3 teilbar, so ist }}k{\text{ keine natürliche Zahl.}}}\\{\color {Orange}\downarrow }\\n+1{\text{ ist keine natürliche Zahl.}}\\{\color {Orange}|}\\{\color {Orange}{\text{Ist }}k{\text{ keine natürliche Zahl, so ist }}k-1{\text{ keine natürliche Zahl.}}}\\{\color {Orange}\downarrow }\\(n+1)-1{\text{ ist keine natürliche Zahl.}}\\{\color {Orange}|}\\{\color {Orange}(n+1)-1=n}\\{\color {Orange}\downarrow }\\n{\text{ ist keine natürliche Zahl. Widerspruch!}}\end{array}}}$

Auch diesen Beweis kannst du in einem Fließtext schreiben:

Widerspruchsannahme: Sei ${\displaystyle n}$ eine natürliche Zahl und ${\displaystyle n+(n+1)+(n+2)}$ nicht durch 3 teilbar. Wegen ${\displaystyle n+(n+1)+(n+2)=3\cdot n+3=3\cdot (n+1)}$ ist ${\displaystyle 3\cdot (n+1)}$ nicht durch 3 teilbar. Damit ist ${\displaystyle n+1}$ keine natürliche Zahl, da, wenn ${\displaystyle n+1}$ eine natürliche Zahl wäre, so wäre ${\displaystyle 3\cdot (n+1)}$ durch 3 teilbar. Wenn ${\displaystyle n+1}$ keine natürliche Zahl ist, ist auch ${\displaystyle n}$ keine natürliche Zahl. Dies ist aber ein Widerspruch dazu, dass ${\displaystyle n}$ nach Widerspruchsannahme eine natürliche Zahl ist ↯.