Widerspruchsbeweis

Der Widerspruchsbeweis ist eine beliebte Beweistechnik. Wenn wir beweisen wollen, dass eine Aussage gilt, verneinen wir sie, nehmen an, dass ihre Negation wahr ist, und versuchen, einen Widerspruch zu erhalten. Das Ziel ist zu zeigen, dass die von uns gewählte Annahme zu etwas Unsinnigem führt.

Triviales Beispiel

Nehmen wir die Behauptung „Es gibt keine kleinste positive rationale Zahl.“ Diese Behauptung beweisen wir durch Widerspruch, indem wir sie zunächst verneinen: „Es gibt eine kleinste positive rationale Zahl“, und diese Zahl nennen wir q. 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.

Das nutzen wir bei der Suche nach einem Widerspruch. Wenn wir doch eine Zahl finden, die kleiner als ein beliebig gewähltes q ist, dann sind wir zu einem Widerspruch gekommen und die verneinte Aussage gilt nicht. Wenn wir zum Beispiel 0,1 als kleinste Zahl wählen, sehen wir, dass 0,01 kleiner ist. Weiter ist 0,001 noch kleiner, 0,0001 ist wieder kleiner und so weiter. Es genügt, die Zahl q durch zehn zu teilen, und wir erhalten eine kleinere Zahl. Im Grunde genügt es, sie durch irgendeine Zahl zu teilen, die größer als eins ist, zum Beispiel durch zwei – die Hälfte der Zahl q ist sicher kleiner als q selbst.

Die Zahl q/2 ist also sicher kleiner als q und zugleich eine positive rationale Zahl. Damit sind wir zu einem Widerspruch mit der verneinten Aussage gekommen, die verneinte Aussage gilt also nicht und folglich gilt die ursprüngliche, nicht verneinte Aussage.

Interessante Zahlen

Ein klassischer Scherzbeweis, der das Prinzip des Widerspruchs veranschaulicht, ist das folgende Beispiel. Nehmen wir an, es gibt natürliche Zahlen, die auf irgendeine Weise interessant sind. Zum Beispiel ist die Zahl 2 interessant, weil 2 · 2 = 2 + 2 gilt, das ist eine ziemlich untypische Eigenschaft. Die Zahl 42 ist interessant, weil sie die Antwort auf alles ist. Und so weiter. Die Frage lautet: Gibt es unendlich viele interessante Zahlen?

Nehmen wir das Gegenteil an, nämlich dass es nur endlich viele interessante Zahlen gibt und einige Zahlen uninteressant sind. Diese uninteressanten natürlichen Zahlen fassen wir zu einer Menge der uninteressanten Zahlen zusammen. Nun wählen wir die kleinste uninteressante Zahl aus. Moment, die kleinste uninteressante Zahl? Das klingt doch ziemlich interessant, oder? :-)

Damit sind wir zu einem Widerspruch gekommen, denn die kleinste uninteressante Zahl ist in Wirklichkeit ziemlich interessant, es kann also keine kleinste uninteressante Zahl geben, folglich muss die Menge der uninteressanten Zahlen notwendigerweise leer sein.

Das ist natürlich Unsinn, wir haben nicht ordentlich definiert, was eine interessante Zahl ist, aber das Beweisverfahren selbst ist in Ordnung.

Beweis der Unendlichkeit der Primzahlen

In diesem Beispiel zeigen wir ein ähnliches Vorgehen wie im vorherigen Kapitel, diesmal ist es aber in jeder Hinsicht korrekt.

Eine Primzahl ist eine Zahl, die nur durch zwei verschiedene Zahlen teilbar ist – durch sich selbst und durch eins. Beachte, dass die Eins die Definition nicht erfüllt und die Zwei sie erfüllt.

Die Primfaktorzerlegung ist die Zerlegung einer natürlichen Zahl, außer der Eins, in ein Produkt von Primzahlen. Das ist eine ziemlich interessante Eigenschaft der natürlichen Zahlen. Egal welche natürliche Zahl du nimmst (außer der Eins), es gilt, dass sie sich in ein Produkt mehrerer (auch gleicher) Primzahlen zerlegen lässt. Beispiele:

$$\begin{array}{rcl}8& =& 2\cdot 2\cdot 2\\ 15& =& 3\cdot 5\\ 26& =& 2\cdot 13\\ 1800& =& 2^3\cdot 3^2\cdot 5^2\end{array}$$

Die Aussage über die Primfaktorzerlegung heißt Fundamentalsatz der Arithmetik. Er sagt uns unter anderem, dass eine solche Zerlegung eindeutig ist, d. h., wir finden keine zwei verschiedenen Primfaktorzerlegungen einer natürlichen Zahl. Außerdem besteht nur bei Primzahlen die Primfaktorzerlegung aus einer einzigen Zahl – nämlich aus ihnen selbst. Die Primfaktorzerlegung der Sieben wäre also die Zahl sieben. Diese Fakten nutzen wir beim Aufbau des Beweises der folgenden Behauptung.

Nun beweisen wir die Behauptung „Es gibt unendlich viele Primzahlen“. Die Behauptung verneinen wir wieder: „Es gibt nur endlich viele Primzahlen.“ Nehmen wir an, dass die Folge von Zahlen

$$a_1,a_2,a_3,\dots ,a_n$$

alle existierenden Primzahlen darstellt. Wenn in dieser Folge alle Primzahlen stehen, dann gilt sicher, dass wir keine Zahl mehr finden können, die eine Primzahl wäre und zugleich nicht in dieser Folge stünde. Alle Primzahlen haben wir in der Folge, außerhalb der Folge darf keine Primzahl mehr vorkommen.

Wenn wir zu einem Widerspruch kommen wollen, müssen wir also eine Primzahl konstruieren, die nicht in dieser Folge steht. Dabei hilft uns die Zahl q. Diese konstruieren wir, indem wir alle Primzahlen der Folge multiplizieren und eins addieren:

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

Jetzt 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 sich jede natürliche Zahl als Produkt von Primzahlen darstellen lässt. Allerdings teilt keine Primzahl a_i die Zahl q ohne Rest, nach der Division bleibt immer eins übrig. Wenn wir versuchten, die Zahl q zum Beispiel durch die Primzahl a₂ zu teilen, ergäbe sich Folgendes:

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

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

Den Bruch zerlegen wir zunächst in zwei. Im ersten Bruch kürzen wir a₂ und es bleibt ein Produkt von Primzahlen übrig, das einfach irgendeine andere unwesentliche ganze Zahl ist. Im zweiten Bruch gibt es nichts zu kürzen, dieser Bruch ist immer eine nicht ganze Zahl (weil der Nenner nicht eins sein kann, die Eins ist keine Primzahl). In der Summe erhalten wir also eine Zahl, die nicht ganz ist, also teilt die Primzahl a₂ die Zahl q nicht.

Damit haben wir bewiesen, dass keine der Primzahlen aus der Folge a_n die Zahl q teilt. (Anmerkung: Wir haben es zwar nur für a₂ gezeigt, aber es lässt sich leicht verallgemeinern, wenn wir a₂ durch ein allgemeines a_i ersetzen.) Da sich aber jede natürliche Zahl in ein Produkt von Primzahlen zerlegen lässt, muss es andere Primzahlen geben, die nicht in der Folge a_n stehen, aber in der Faktorisierung der Zahl q vorkommen. Dabei kann die Zahl q selbst durchaus eine Primzahl sein, und die Primfaktorzerlegung enthält dann nur die Zahl q. Noch einmal der letzte Gedankengang:

1. Jede natürliche Zahl lässt sich als Produkt von Primzahlen darstellen.
2. Nach der Annahme enthält die Folge a_n alle existierenden Primzahlen.
3. Wir formen die erste Aussage so um: Jede natürliche Zahl lässt sich als Produkt ausgewählter Glieder der Folge a_n darstellen, weil diese alle Primzahlen enthält.
4. Wir haben bewiesen, dass keine Zahl aus der Folge a_n die Zahl q teilt.
5. Damit entstand ein Widerspruch zur Annahme → wenn wir jede natürliche Zahl in ein Produkt von Primzahlen zerlegen können müssen und die Folge a_n keine Zahl enthält, die q teilt, dann muss es andere Primzahlen geben, die q teilen und die Primfaktorzerlegung der Zahl q bilden.

Damit sind wir zu einem Widerspruch gekommen. Die Primfaktorzerlegung der Zahl q enthält Primzahlen, die nicht in der Folge stehen, von der wir angenommen haben, dass sie alle Primzahlen enthält. Die verneinte Aussage gilt also nicht, es gilt die ursprüngliche, nicht verneinte Aussage. Es gibt unendlich viele Primzahlen.