Es gibt keine größte gerade Zahl

Beweise, dass es keine größte gerade Zahl gibt.

Schreibe die Negation als erste Zeile: Angenommen, es gibt eine größte gerade Zahl $N$ = Annahme: $N$ ist gerade und $N \ge$ jede gerade Zahl

Verwende die Definition von gerade: $N = 2k$ für eine ganze Zahl $k$, also $N + 2 = 2k + 2 = 2(k + 1)$ = $N + 2$ ist gerade

Vergleiche die beiden Zahlen: $N + 2 > N$ = Es gibt eine gerade Zahl, die größer als $N$ ist

Erkenne den Widerspruch und folgere: $N$ ist die größte gerade Zahl, aber $N + 2$ ist eine größere gerade Zahl = Die Annahme ist falsch

Answer: Die Annahme führt zu einem Widerspruch, also gibt es keine größte gerade Zahl. q. e. d.

Zwei von 13 Personen haben im selben Monat Geburtstag

Beweise, dass in jeder Gruppe von 13 Personen mindestens zwei im selben Monat geboren sind.

Schreibe die Negation: Angenommen, alle 13 Personen sind in verschiedenen Monaten geboren = Annahme: 13 verschiedene Monate

Zähle, was die Annahme braucht: 13 Personen ohne wiederholten Monat brauchen mindestens 13 verschiedene Monate = Mindestens $13$ Monate nötig

Vergleiche mit den Tatsachen: Ein Jahr hat nur $12$ Monate, und $13 > 12$ = Unmöglich

Folgere: Die Annahme ist falsch = Zwei Personen teilen einen Monat

Answer: Mindestens zwei der 13 Personen sind im selben Monat geboren. Das ist das Schubfachprinzip: 13 Tauben, 12 Schläge. q. e. d.

Es gibt keine kleinste positive rationale Zahl

Beweise, dass es keine kleinste positive rationale Zahl gibt.

Schreibe die Negation: Angenommen, $r$ ist die kleinste positive rationale Zahl = Annahme: $r > 0$, $r$ rational, nichts ist kleiner

Bilde eine neue Zahl: Wenn $r = \frac{a}{b}$, dann ist $\frac{r}{2} = \frac{a}{2b}$ ein Bruch aus ganzen Zahlen = $\frac{r}{2}$ ist rational

Prüfe ihre Größe: $r > 0$, also $0 < \frac{r}{2} < r$ = $\frac{r}{2}$ ist positiv und kleiner als $r$

Erkenne den Widerspruch und folgere: $r$ war die kleinste, aber $\frac{r}{2}$ ist kleiner = Die Annahme ist falsch

Answer: Es gibt keine kleinste positive rationale Zahl. Behauptet zum Beispiel jemand $\frac{1}{1000}$, dann ist $\frac{1}{2000}$ kleiner. q. e. d.

Die Wurzel aus 2 ist irrational

Beweise, dass $\sqrt{2}$ irrational ist.

Schreibe die Negation: Angenommen, $\sqrt{2}$ ist rational: $\sqrt{2} = \frac{a}{b}$ mit ganzen Zahlen $a, b$, $b \neq 0$, und der Bruch ist vollständig gekürzt = $a$ und $b$ haben keinen gemeinsamen Teiler

Quadriere beide Seiten: $2 = \frac{a^2}{b^2}$, also $a^2 = 2b^2$ = $a^2$ ist gerade

Folgere, dass a gerade ist: Wäre $a$ ungerade, dann wäre $a^2$ ungerade (bewiesen in der Lektion zum direkten Beweis) = $a = 2k$ für eine ganze Zahl $k$

Setze ein: $(2k)^2 = 2b^2$, also $4k^2 = 2b^2$, also $b^2 = 2k^2$ = $b^2$ ist gerade, also ist $b$ gerade

Erkenne den Widerspruch: $a$ und $b$ sind beide gerade, also beide durch $2$ teilbar = Das widerspricht "vollständig gekürzt"

Answer: Die Annahme, dass $\sqrt{2}$ rational ist, führt zu einem Widerspruch, also ist $\sqrt{2}$ irrational. q. e. d.

Es gibt unendlich viele Primzahlen (Euklid)

Beweise, dass es unendlich viele Primzahlen gibt.

Schreibe die Negation: Angenommen, es gibt nur endlich viele Primzahlen: $p_1, p_2, \ldots, p_n$ = Die Liste enthält jede Primzahl

Bilde eine neue Zahl: $N = p_1 \cdot p_2 \cdots p_n + 1$ = $N > 1$

Teile N durch jede Primzahl der Liste: $N$ ist um eins größer als ein Vielfaches jedes $p_i$ = Der Rest ist immer $1$, also teilt kein $p_i$ die Zahl $N$

Verwende eine bekannte Tatsache: Jede ganze Zahl größer als $1$ hat mindestens einen Primfaktor = $N$ hat einen Primfaktor, der nicht auf der Liste steht

Erkenne den Widerspruch: Die Liste sollte jede Primzahl enthalten = Die Annahme ist falsch

Answer: Es gibt unendlich viele Primzahlen. Vorsicht: $N$ selbst muss keine Primzahl sein. Mit den Primzahlen bis 13 ist $N = 30031 = 59 \times 509$, und 59 und 509 sind Primzahlen, die auf der Liste fehlen. q. e. d.

Mistake: "Es gibt unendlich viele Primzahlen" verneinen als "Es gibt keine Primzahlen"

Why: Das Gegenteil von "unendlich viele" ist nicht "keine". Die Negation muss jeden Fall abdecken, in dem die Aussage nicht gilt, und das ist "nur endlich viele".

Correct: Nimm an: "Es gibt nur endlich viele Primzahlen". Ebenso ist die Negation von "jede Primzahl ist ungerade" die Aussage "mindestens eine Primzahl ist nicht ungerade", nicht "jede Primzahl ist gerade".

Mistake: $x > 5$ verneinen als $x < 5$

Why: Der Fall $x = 5$ wird vergessen. Wenn der Beweis nur $x < 5$ ausschließt, ist die Zahl $5$ noch möglich.

Correct: Die Negation von $x > 5$ ist $x \le 5$, und die Negation von $x \ge 5$ ist $x < 5$.

Mistake: "Vollständig gekürzt" im Beweis vergessen, dass $\sqrt{2}$ irrational ist

Why: Ohne diese Bedingung ist es gar kein Widerspruch, dass $a$ und $b$ beide gerade sind: $\frac{4}{2}$ hat einen geraden Zähler und Nenner.

Correct: Schreibe $\sqrt{2} = \frac{a}{b}$ vollständig gekürzt. Jeder Bruch lässt sich kürzen, das kostet also nichts, und genau diese Tatsache wird später verletzt.

Mistake: Ein überraschendes Ergebnis für einen Widerspruch halten

Why: Ein Ergebnis, das seltsam aussieht (eine sehr große Zahl, ein unerwarteter Bruch), ist nicht unmöglich. Ein Widerspruch muss mit der Annahme oder mit einer bekannten Tatsache kollidieren.

Correct: Nenne die beiden Aussagen, die sich widersprechen, zum Beispiel "$r$ ist die kleinste" und "$\frac{r}{2} < r$", und schreibe dann die Folgerung auf.

Passende Socken im Dunkeln

Das Schubfachprinzip, durch Widerspruch bewiesen, sagt dir, wie viele Dinge du mindestens brauchst, damit sich eines garantiert wiederholt.

In einer Schublade liegen schwarze, weiße und graue Socken. Könntest du 4 Socken in lauter verschiedenen Farben nehmen, bräuchtest du 4 Farben, es gibt aber nur 3. Also enthalten 4 Socken immer ein passendes Paar.

Hash-Kollisionen in der Informatik

Computer geben Dateien kurze Codes, sogenannte Hashes. Da es mehr mögliche Dateien als Codes gibt, müssen zwei verschiedene Dateien manchmal denselben Code teilen.

Ein System gibt jeder Datei einen Code von 00 bis 99. Wären bei 101 Dateien alle Codes verschieden, bräuchte man 101 Codes, es gibt aber nur 100, also teilen zwei Dateien einen Code.

Warum ein Taschenrechner nie die exakte Wurzel aus 2 zeigt

Weil $\sqrt{2}$ irrational ist, endet ihre Dezimaldarstellung nie und wiederholt sich nie. Jede Dezimalzahl auf dem Display ist nur eine Näherung, und das müssen Ingenieure beim Berechnen von Diagonalen beachten.

Eine quadratische Fliese mit 1 m Seitenlänge hat die Diagonale $\sqrt{2} \approx 1{,}4142$ m. Der Wert 1,4142 ist nah dran, aber nicht exakt.

Q: Warum reicht es, einen Widerspruch zu erreichen?

A: Korrektes Schließen aus wahren Aussagen liefert immer nur wahre Aussagen. Erreichen wir etwas Unmögliches, war mindestens ein Ausgangspunkt falsch, und der einzige Ausgangspunkt, den wir selbst hinzugefügt haben, war die Annahme $\neg P$. Also ist $\neg P$ falsch und $P$ wahr.

Q: Wann sollte ich einen Widerspruchsbeweis verwenden?

A: Er ist eine gute Wahl, wenn die Aussage behauptet, dass etwas nicht existiert (keine größte Zahl, kein Bruch gleich $\sqrt{2}$), oder dass es unendlich viele von etwas gibt. Dann liefert dir die Annahme des Gegenteils ein konkretes Objekt, mit dem du arbeiten kannst.

Q: Ist ein Widerspruchsbeweis dasselbe wie ein Beweis durch Kontraposition?

A: Nein. Ein Beweis durch Kontraposition zeigt "wenn nicht q, dann nicht p" direkt und endet bei "nicht p". Ein Widerspruchsbeweis nimmt an, dass die Aussage falsch ist, und darf bei irgendeiner Unmöglichkeit enden. Jeder Beweis durch Kontraposition lässt sich als Widerspruchsbeweis umschreiben, aber nicht jeder Widerspruchsbeweis ist ein Beweis durch Kontraposition.

Q: Was bedeutet q. e. d., und was ist "reductio ad absurdum"?

A: q. e. d. (quod erat demonstrandum, "was zu beweisen war", auf Deutsch auch w. z. b. w.) markiert das Ende eines Beweises. Reductio ad absurdum, "Zurückführung auf das Absurde", ist der lateinische Name des Widerspruchsbeweises.