4. Beweise

Aussagen beweisen

Es gibt verschiedene Beweistechniken. Du lernst sie im Folgenden anhand einer durchgängigen, sehr einfachen Aussage kennen. Später dann wendest du die Beweistechniken auf bedeutsamere Aussagen an.

Direkter Beweis

Der direkte Beweis entspricht dem Schema

Du gehst von einer wahren Aussage $A$ aus und zeigst, dass daraus die Behauptung $B$ folgt. Damit hast du die Behauptung $B$ bewiesen.

Beispiel

Du willst zeigen: Wenn eine beliebige Zahl $n$ ungerade ist, dann ist auch ihr Quadrat $n^2$ ungerade.

Die Aussage $A$ ist hier also "$n$ ist ungerade". Die Behauptung $B$ ist hier "$n^2$ ist ungerade".

Über mehrere Zwischenschritte zeigst du $A \Rightarrow B$ folgendermaßen:

$n ~\text{ist ungerade}~ ~ \Rightarrow ~ n = 2m + 1 ~  \Rightarrow ~ n^2 = 4m^2 + 4m + 1 ~~ \Rightarrow$

$n^2 = 2(2m^2 + 2m) + 1 ~~\Rightarrow ~ n^2 ~ \text{ist ungerade}$

Hierbei benutzt du die Tatsache, dass die ungeraden Zahlen definitionsgemäß genau diejenigen Zahlen sind, die sich als Vielfaches von 2 plus 1 darstellen lassen.

Indirekter Beweis: Kontraposition

Die Kontraposition entspricht dem Schema

Du willst $A \Rightarrow B$ zeigen, aber stattdessen beweist du die äquivalente Aussage $\neg B \Rightarrow \neg A$.

Beispiel

Wieder ist die Aussage $A$ hier "$n$ ist ungerade" und die Behauptung $B$ hier "$n^2$ ist ungerade". Die Aussage "$n^2$ ist gerade" entspricht also $\neg B$. Eine gerade Quadratzahl hat die Form $n^2 = 4m^2$. Damit ist $n = 2m$ gerade. Also gilt $\neg A$.

Indirekter Beweis: Widerspruchsbeweis

Der Widerspruchsbeweis entspricht dem Schema

Etwas Falsches ($0$ entspricht false) kann aber nur aus etwas Falschem folgen, also ist $\neg B$ falsch und $B$ damit wahr.

Du führst den Beweis, dass die Behauptung $B$ gilt, indem du die Annahme machst, dass $\neg B$ gelte. Dann führst du die Annahme zum Widerspruch, d. h. du leitest aus der Annahme etwas ab, das nicht sein kann, also etwas Falsches. Damit ist die Annahme falsch und die Behauptung wahr.

Beispiel

Wieder ist die Aussage $A$ hier "$n$ ist ungerade" und die Behauptung $B$ hier "$n^2$ ist ungerade".

Es sei $n$ ungerade, also $n=2m+1$ und damit $n^2 = 4m^2 + 4m + 1$.

Behauptung: $n^2$ ist ungerade.

Annahme des Gegenteils: $n^2$ ist gerade.

Dann hat $n^2$ die Form $n^2=2k$ und es gilt

$4m^2 + 4m + 1 ~=~ 2k$

$\Rightarrow ~ 1 ~=~ 2k - 2(2m^2 +2m) ~=~ 2(k-2m^2-2m)$

$\Rightarrow ~ ½ ~=~ k-2m^2-2m$

Links steht ½, aber rechts steht eine ganze Zahl, dies ist ein Widerspruch. Damit ist die Annahme falsch und die Behauptung wahr. Also gilt: $n^2$ ist ungerade.

Beweis mit vollständiger Induktion

Vollständige Induktion eignet sich immer dann, wenn du eine Aussage beweisen möchtest, die für alle $n$ gilt.

Dein Beweis besteht aus zwei Schritten:

• Du beweist, dass die Aussage für $n=1$ gilt (Induktionsanfang);

• du beweist, dass unter der Voraussetzung, dass die Aussage für beliebiges $n$ gilt, sie auch für $n+1$ gilt (Induktionsschritt).

Du kannst dir vorstellen, dass ein Induktionsbeweis wie eine Kette umfallender Dominosteine durchklappert: Alle Dominosteine fallen um, wenn du dafür sorgst, dass

• der erste Dominostein umfällt (Induktionsanfang),

• unter der Voraussetzung, dass ein beliebiger Dominostein umfällt, stets auch der folgende Dominostein umfällt (Induktionsschritt).

Beispiel

Du willst die Aussage "$n^2$ ist ungerade" für alle ungeraden Zahlen $n$ per vollständiger Induktion zeigen. Dies tust du in zwei Schritten:

• Du beweist, dass die Aussage für $n = 1$ gilt (Induktionsanfang),

• du beweist, dass unter der Voraussetzung, dass die Aussage für eine beliebige ungerade Zahl $n$ gilt, sie auch für die nächste ungerade Zahl $n+2$ gilt (Induktionsschritt).

Und hier ist nun der Beweis:

Induktionsanfang: Für die ungerade Zahl $n=1$ gilt $n^2 = 1$ ist ungerade.

Induktionsschritt: Für die auf eine beliebige ungerade Zahl $n$ folgende ungerade Zahl $n+2$ gilt $(n+2)^2 = n^2 + 4n + 4$ ist ungerade, da nach Induktionsvoraussetzung $n^2$ ungerade ist und das Ergebnis nach Addition der zwei geraden Zahlen $4n$ und $4$ ungerade bleibt.

Beweistechniken richtig anwenden

Welchen der vier angegebenen Beweise findest du am besten? Den direkten Beweis? Oder die Kontraposition oder den Widerspruchsbeweis? Womöglich gar den Induktionsbeweis?

Meist ist der direkte Beweis der eleganteste - so auch hier für die Aussage dieses Beispiels. Die indirekten Beweise und der Induktionsbeweis sind hier eher umständlich. Aber manchmal ist es auch anders. Manchmal ist ein direkter Beweis nicht möglich oder zu umständlich oder zu wenig anschaulich, und eine andere Beweistechnik ist eleganter.

Beispiel für einen Widerspruchsbeweis

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

Annahme des Gegenteils: $\sqrt{2}$ ist rational. Dann lässt sich $\sqrt{2}$ darstellen als gekürzter Bruch $\frac{p}{q}$ mit ganzen, teilerfremden Zahlen $p$ und $q$:

Durch Quadrieren der Gleichung ergibt sich

und damit $2q^2 = p^2$. Da links eine gerade Zahl steht, muss $p^2$ gerade sein und damit auch $p$, also $p=2r$. Damit gilt $2q^2 = 4r^2$ oder $q^2 = 2r^2$. Damit ist $q^2$ gerade und damit auch $q$.

Hieraus ergibt sich ein Widerspruch zur Annahme, dass $p$ und $q$ teilerfremd sind. Denn wenn $p$ und $q$ beide gerade sind, dann sind sie nicht teilerfremd, sondern enthalten 2 als gemeinsamen Teiler.

Also ist die Annahme falsch und die Behauptung ist wahr: $\sqrt{2}$ ist irrational.

Beispiel für vollständige Induktion

Behauptung: Für jedes $n\in \mathbb{N}$ gilt: Die Summe der ersten $n$ ungeraden Zahlen ist gleich $n^2$:

Induktionsanfang: $n=1$

Induktionsschritt: Die Behauptung sei für beliebiges $n$ wahr. Dann gilt sie auch für $n+1$:

Aufgaben