Beweis durch Widerspruch

Der Widerspruchsbeweis ist eine beliebte Beweistechnik. Wenn wir beweisen wollen, dass eine Aussage wahr ist, nehmen wir an, dass sie wahr ist, dann negieren wir sie und versuchen, einen Widerspruch zu finden. Das Ziel ist es zu beweisen, dass die von uns gewählte Annahme zu einem Unsinn führt.

Ein triviales Beispiel

Betrachten wir die Aussage "Es gibt keine kleinste positive rationale Zahl". Wir können diese Aussage durch Disputation beweisen, indem wir zunächst die Aussage "es gibt eine kleinste positive Zahl" negieren und diese Zahl als q bezeichnen. Wenn q die kleinste positive rationale Zahl ist, dann können wir keine kleinere positive rationale Zahl finden - denn dann wäre q nicht die kleinste.

Wir werden dies nutzen, um einen Widerspruch zu finden. Wenn wir eine Zahl finden, die kleiner ist als q, die wir beliebig wählen können, dann haben wir einen Widerspruch gefunden und die ursprüngliche Aussage ist nicht gültig. Wenn wir z. B. 0,1 als kleinste Zahl wählen, sehen wir, dass 0,01 kleiner ist. Danach ist 0,001 noch kleiner, 0,0001 ist wieder kleiner und so weiter. Teilen Sie die angegebene Zahl q einfach durch zehn und Sie erhalten eine kleinere Zahl. Teilen Sie sie einfach durch eine beliebige Zahl, die größer als eins ist, z. B. durch zwei - die Hälfte der Zahl q wird mit Sicherheit kleiner sein als die ganze Zahl q.

Die Zahl q/2 ist also mit Sicherheit kleiner als q, und sie ist auch eine positive Zahl. Dies führt zu einem Konflikt mit der verneinten Aussage, d. h. die verneinte Aussage ist nicht gültig und somit ist die ursprüngliche nicht-negierte Aussage gültig.

Interessante Zahlen

Ein klassischer lustiger Beweis, der das Prinzip des Widerspruchs veranschaulicht, ist das folgende Beispiel. Angenommen, es gibt natürliche Zahlen, die in irgendeiner Weise interessant sind. Zum Beispiel ist die Zahl 2 interessant, weil es stimmt, dass 2 · 2 = 2 + 2 eine eher untypische Eigenschaft ist. Die Zahl 42 ist interessant, weil sie die Antwort auf alles ist. Und so weiter. Die Frage ist - gibt es unendlich viele interessante Zahlen?

Nehmen wir das Gegenteil an, d.h. dass es nur endlich viele interessante Zahlen gibt und einige Zahlen uninteressant sind. Wir ordnen diese uninteressanten natürlichen Zahlen in einer Menge von uninteressanten Zahlen an. Nun wählen wir die kleinste uninteressante Zahl. Moment, die kleinste uninteressante Zahl? Das klingt ziemlich interessant, nicht wahr? :-)

Das bringt uns zu einem Widerspruch, denn die kleinste uninteressante Zahl ist eigentlich ganz interessant, also kann es keine kleinste uninteressante Zahl geben, also muss die Menge der uninteressanten Zahlen zwangsläufig leer sein.

Das ist natürlich Unsinn, wir haben keine richtige Definition für eine interessante Zahl, aber das Beweisverfahren selbst ist in Ordnung.

Der Beweis für die Unendlichkeit der Primzahlen

In diesem Beispiel zeigen wir ein ähnliches Verfahren wie im vorigen Abschnitt, aber dieses Mal ist es in allen Punkten korrekt.

Eine Primzahl ist eine Zahl, die nur durch zwei verschiedene Zahlen - sich selbst und eins - teilbar ist. Beachten Sie, dass die Eins die Definition nicht erfüllt, die Zwei aber schon.

DiePrimzahlzerlegung oder Faktorisierung ist die Zerlegung einer natürlichen Zahl, die nicht eins ist, in ein Produkt von Primzahlen. Das ist eine sehr interessante Eigenschaft der natürlichen Zahlen. Welche natürliche Zahl man auch immer nimmt (außer der Eins), sie lässt sich in das Produkt mehrerer (auch gleicher) Primzahlen zerlegen. Beispiele:

$$\begin{eqnarray} 8&=&2\cdot2\cdot2\\15&=&3\cdot5\\26&=&2\cdot13\\1800&=&2^3\cdot3^2\cdot5^2 \end{eqnarray}$$

Die Aussage über die Primzahlzerlegung wird als Fundamentalsatz der Arithmetik bezeichnet. Er besagt u. a., dass eine solche Zerlegung eindeutig ist, d. h., wir können nicht zwei verschiedene Primzahlzerlegungen einer einzigen natürlichen Zahl finden. Außerdem haben nur Primzahlen eine Primzahlzerlegung, die nur aus einer Zahl besteht - aus sich selbst. Die Primzahlzerlegung von sieben wäre also die Zahl sieben. Wir werden diese Fakten nutzen, um den Beweis der folgenden Aussage zu konstruieren.

Wir werden nun die Aussage beweisen, dass "es unendlich viele Primzahlen gibt". Wir werden die Behauptung: "Es gibt endlich viele Primzahlen" wieder entkräften. Nehmen wir an, dass eine Folge von Zahlen

$$a_1, a_2, a_3,,\ldots,a_n$$

repräsentiert alle Primzahlen, die es gibt. Wenn alle Primzahlen in dieser Folge enthalten sind, dann können wir sicherlich keine Zahl finden, die gleichzeitig eine Primzahl ist und nicht in der Folge enthalten ist. Wir haben alle Primzahlen in der Folge, keine Primzahl kann außerhalb der Folge sein.

Wenn wir also einen Widerspruch finden wollen, müssen wir eine Primzahl konstruieren, die nicht in der Folge enthalten ist. Die Zahl q hilft uns dabei. Wir konstruieren sie, indem wir alle Primzahlen in der Folge multiplizieren und eine hinzufügen:

$$q=a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n+1$$

Nun müssen wir zeigen, dass diese Zahl entweder eine Primzahl ist oder irgendwie eine Primzahl erzeugt. Wir wissen, dass q eine natürliche Zahl ist und dass jede natürliche Zahl als Produkt von Primzahlen ausgedrückt werden kann. Keine Primzahl a_i teilt jedoch die Zahl q ohne Rest, so dass nach der Division immer eine übrig bleibt. Wenn wir versuchen würden, die Zahl q zum Beispiel durch die Primzahl a₂ zu teilen, kämen wir zu folgendem Ergebnis:

$$\frac{a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n+1}{a_2}=\frac{a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1 \cdot a_3 \cdot a_4 \cdot \ldots \cdot a_n+\frac{1}{a_2}$$

Wir teilen den Bruch zunächst in zwei Teile. Im ersten Bruch schneiden wir a₂ ab und erhalten ein Produkt aus Primzahlen, das einfach eine andere, irrelevante ganze Zahl ist. Im zweiten Bruch gibt es nichts abzuschneiden, dieser Bruch wird immer eine Nicht-Ganzzahl sein (weil der Nenner nicht eins sein kann, eins ist keine Primzahl). In der Summe erhalten wir also eine Zahl, die keine ganze Zahl ist, d. h. die Primzahl a₂ teilt die Zahl q nicht.

Dies beweist, dass keine der Primzahlen in der Folge a_n die Zahl q teilt. (Hinweis: Wir haben dies nur für a₂ gezeigt, aber es lässt sich leicht verallgemeinern, wenn wir a₂ durch die allgemeine a_i ersetzen.) Da aber jede natürliche Zahl in ein Produkt von Primzahlen zerlegt werden kann, muss es andere Primzahlen geben, die nicht in der Folge a_n enthalten sind, aber Faktorisierungen von q sind. Die Zahl q selbst kann aber durchaus eine Primzahl sein, und die Primzahlzerlegung betrifft dann nur die Zahl q. Also ein letzter Gedankengang:

1. Jede natürliche Zahl lässt sich als ein Produkt von Primzahlen darstellen.
2. Unter der Annahme, dass die Folge a_n alle existierenden Primzahlen enthält.
3. Ändern wir die erste Aussage dahingehend ab, dass jede natürliche Zahl als Produkt ausgewählter Glieder der Folge a_n ausgedrückt werden kann, da sie alle Primzahlen enthält.
4. Wir haben bewiesen, dass keine Zahl in der Folge a_n die Zahl q teilt.
5. Dies warf einen Streit mit der Annahme $\rightarrow$ auf, wenn wir in der Lage sein müssen, jede natürliche Zahl in ein Produkt von Primzahlen zu zerlegen und die Folge a_n keine Zahl enthält, die q teilt, dann muss es andere Primzahlen geben, die q teilen und Primzahlzerlegungen von q sind.

Dies führt uns zu einem Widerspruch. Die Primzahlzerlegung von q enthält Primzahlen, die nicht in der Folge enthalten sind, von der wir angenommen haben, dass sie alle Primzahlen enthält. Die negierte Behauptung gilt also nicht, die nicht-negierte ursprüngliche Behauptung schon. Es gibt unendlich viele Primzahlen.