Mathe für Nicht-Freaks: Fallunterscheidung und Kontraposition

{{#invoke:Mathe für Nicht-Freaks/Seite|oben}}

Neben den verschiedenen Arten mathematischer Beweise gibt es einige Methoden, die du in Beweisen verwenden kannst: die vollständige Fallunterscheidung, der Beweis durch Kontraposition und die vollständige Induktion. Diese Liste ist nicht vollständig und es gibt gewiss vielfältige Wege einen Beweis zu führen. Dennoch kann dir der nachfolgende Abschnitt als Inspirationsquelle für eigene Beweise dienen.

Vollständige Fallunterscheidung Vorlage:Anker

Bei vollständiger Fallunterscheidung wird der Beweis in eine endliche Anzahl von Fällen ${\mathrm{F}}_1,{\mathrm{F}}_2,\dots {\mathrm{F}}_n$ aufgeteilt. Für jeden der Fälle muss der zu beweisende Satz unter zusätzlicher Annahme der Fallbedingung ${\mathrm{F}}_k$ bewiesen werden. Ein Beweis durch vollständige Fallunterscheidung hat damit folgende Form:

Mit dem einfachsten Fall kann man beginnen; manchmal fließen die hierbei gewonnenen Erkenntnisse bei der Bearbeitung anderer Fälle ein. Insofern kann eine relativ schwierige Gesamtaufgabe in mehrere leichter zu lösende Teilaufgaben reduziert werden gemäß dem Motto: teile und herrsche!

Zu achten ist darauf, dass bei der Aufteilung des Beweises in unterschiedliche Fälle der zu beweisende Satz vollständig abgedeckt wird. So kann z. B. beim Beweis eines Satzes, der für alle ganzen Zahlen gelten soll, eine Aufteilung in positive und negative Zahlen sinnvoll sein. Dann muss aber auch das Auftreten der Zahl Null als dritter Fall bewiesen werden.

Beispiel

Als Beispiel beweisen wir folgenden Satz mit Hilfe vollständiger Fallunterscheidung (Quelle: Wikipedia-Artikel „Beweis (Mathematik)“):

Wir werden folgende vier Fälle unterscheiden:

1. $p=4k$
2. $p=4k+1$
3. $p=4k+2$
4. $p=4k+3$

Da $p$ eine natürliche Zahl ist (nur natürliche Zahlen können per Definition Primzahlen sein), muss einer der obigen vier Fälle auftreten. Unsere Fallunterscheidung ist damit vollständig. Betrachten wir nun die vier Fälle:

In jedem der Fälle konnten wir beweisen, dass unter der Bedingung der jeweiligen Fallunterscheidung die zu beweisende Implikation wahr ist. Da unsere Fallunterscheidung vollständig ist, ist die zu beweisende Implikation unabhängig vom jeweiligen Fall wahr.

Beweis durch Kontraposition Vorlage:Anker

Der Beweis durch Kontraposition ist eine Beweismethode, die für Beweise von Implikationen der Form $A\Rightarrow B$ verwendet werden können. Diese Beweismethode basiert auf der Tautologie $(A\Rightarrow B)\iff (\mathrm{\neg }B\Rightarrow \mathrm{\neg }A)$.

Die Aussage $(A\Rightarrow B)\iff (\mathrm{\neg }B\Rightarrow \mathrm{\neg }A)$ ist also eine Tautologie und damit immer wahr. Dies bedeutet, dass $A\Rightarrow B$ dann und nur dann wahr ist, wenn $\mathrm{\neg }B\Rightarrow \mathrm{\neg }A$ wahr ist. Wenn wir also einen Satz der Form $A\Rightarrow B$ beweisen wollen, können wir alternativ auch die Aussage $\mathrm{\neg }B\Rightarrow \mathrm{\neg }A$ beweisen. Beim Beweis durch Kontraposition macht man genau dies: Anstatt einen Satz der Form $A\Rightarrow B$ direkt zu beweisen, wird die Aussage $\mathrm{\neg }B\Rightarrow \mathrm{\neg }A$ bewiesen.

Um also Kontraposition erfolgreich anwenden zu können, musst du wissen, wie man Aussagen richtig negiert. Dies kannst du im Abschnitt „Aussagen negieren“ nachlesen.

Beispiel

Als Beispiel wollen wir folgenden Satz mit Hilfe der Kontraposition beweisen (im Folgenden gehe ich davon aus, dass $n$ eine Quadratzahl, also ein Element der Menge $\{k^2|k\in \mathbb{N}\}$ ist):

Dieser Satz hat die Form einer Implikation $A\Rightarrow B$ mit:

Um diesen Satz durch Kontraposition beweisen zu können, müssen wir erst einmal die Aussage $\mathrm{\neg }B\Rightarrow \mathrm{\neg }A$, also die Negation der Aussagen $A$ und $B$ bestimmen:

Damit erhalten wir für $\mathrm{\neg }B\Rightarrow \mathrm{\neg }A$:

Diesen Satz werden wir direkt beweisen. Wir suchen also einen Beweis der Form

Beweis: Sei $\sqrt[2]{n}$ eine natürliche Zahl und ungerade. Wir müssen nun zeigen, dass $n$ ungerade ist. Da $\sqrt[2]{n}$ ungerade ist, gibt es eine natürliche Zahl $k\ge 0$ mit $\sqrt[2]{n}=2\cdot k+1$. Damit ist

Also ist $n$ eine ungerade Zahl. q. e. d.

Vollständige Induktion Vorlage:Anker

Die Vollständige Induktion wird im nächsten Abschnitt dieses Buches ausführlich vorgestellt. Zur Vollständigkeit nenne ich hier nur das Prinzip dieser Beweismethode:

{{#invoke:Mathe für Nicht-Freaks/Seite|unten}}