9. Widerspruchsbeweise

Euklids Beweis ist häufig mit den sich widersprechenden Prädikaten „Widerspruchsbeweis“, „kein Widerspruchsbeweis“, „konstruktiv“, „nicht konstruktiv“ belegt worden. Wir wollen diese Eigenschaften nun genauer betrachten und den Beweis entsprechend einordnen.

Wir beginnen mit den Widerspruchsbeweisen. Ein Widerspruchsbeweis hat folgende logische Form:

Struktur eines Widerspruchsbeweises, Version I

(1)	Wir machen eine Annahme A. Die Annahme A ist eine beliebige mathematische Aussage.

(2)	Wir leiten einen Widerspruch her. Dabei verwandeln wir die Annahme A mit Hilfe von Axiomen und bereits bewiesenen Sätzen durch Anwendung logischer Schlussregeln schrittweise in einen Widerspruch.

(3)	Es ergibt sich (durch einen letzten logischen Schluss) ein Beweis der Aussage ¬ A (der Negation von A).

Ein Widerspruch ist eine beliebige widersprüchliche Aussage wie 0 = 1 oder „Es gibt ein n mit n ≠ n“. Wir folgen einer Tradition der mathematischen Logik und führen ein eigenes Zeichen für einen Widerspruch ein, das sog. Falsum ⊥. Der Leser kann es als Abkürzung für die Aussage „0 = 1“ ansehen, letztendlich kann das Falsum aber den Rang eines festen Bestandteils der mathematischen Sprache geltend machen, in Analogie zu den Junktoren

nicht (¬), und (∧), oder (∨), impliziert (→), äquivalent (↔),

den Quantoren

für alle (∀), es existiert mindestens ein (∃),

und den Variablensymbolen

x, y, z, …

Mit Hilfe des Falsums können wir die drei Schritte eines Widerspruchsbeweises kurz wie folgt angeben:

Struktur eines Widerspruchsbeweises, Version II (mit Falsum)

(1)	Annahme einer Aussage A.

(2)	Wir leiten ⊥ her.

(3)	Wir haben ¬ A bewiesen.

Wir betrachten diese drei Schritte nun genauer.

Schritt 1

Einen Widerspruchsbeweis beginnen wir einfach mit dem Satz

„Wir nehmen an, dass A gilt.“

oder kurz Annahme A. Darüber hinaus ist nichts zu tun. Die Annahme A steht uns im Folgenden wie eine Voraussetzung, ein bereits bewiesener Satz oder ein Axiom zur Verfügung. Sie ist gegeben und darf frei verwendet werden. Verwenden wir sie, so schreiben wir: „Nach Annahme A gilt …“.

Schritt 2

Dieser Teil verläuft wie jeder andere mathematische Beweis. Die Besonderheit ist, dass unser Beweisziel das Falsum ⊥ ist. Wir versuchen also, mit Hilfe der Annahme A irgendeinen Unsinn wie 0 = 1 oder 2 ≠ 2 zu erzeugen. Dieser Beweisteil endet mit dem Wort Widerspruch.

Schritt 3

Dieser Schritt entfällt in der Praxis meistens, sodass der Beweis mit dem erzeugten Widerspruch endet. Aus logischer Sicht ist aber noch ein letzter Schritt nötig: Wir müssen uns von der Annahme A wieder befreien, um zu einem Ergebnis zu kommen, das nicht mehr von unserer Annahme abhängt. Auch hierzu ist nicht viel zu tun. Wir können zum Beispiel einfach schreiben:

„Also ist unsere Annahme A widerlegt und damit ¬ A bewiesen.“

Dieser Zusatz darf entfallen, da er immer derselbe ist. In der Logik spielt er aber eine wichtige Rolle und er wird dort als Abbinden der Annahme A bezeichnet. Ohne dieses Abbinden haben wir lediglich ⊥ mit Hilfe der Annahme A bewiesen. Nach dem Abbinden haben wir ¬ A ohne Annahme bewiesen. Und wir wollen ja nicht das Falsum beweisen, sondern ¬ A.

Widerspruchsbeweise eignen sich ihrer Natur nach hervorragend zum Beweis einer Aussage, die mit einer Negation beginnt. Ist unser Beweisziel von der Form ¬ A, so ist es nur natürlich, A anzunehmen und einen Widerspruch herzuleiten. Wir wollen ja zeigen, dass A nicht gelten kann. Das ist in der konstruktiven Mathematik ganz genauso wie in der klassischen Mathematik − doch dazu kommen wir später. Jetzt wollen wir uns der Frage zuwenden:

Wird die Unendlichkeit der Primzahlen durch Widerspruch gezeigt?

Die Antwort ist: Dies ist abhängig von der Formulierung des Satzes (und der dieser Formulierung entsprechenden Beweisführung) und weiter von den Definitionen der im Satz verwendeten Begriffe „endlich“ und „unendlich“. In der folgenden Version ist der Satz von Euklid ein Paradebeispiel für eine negierte Aussage:

Satz (Unendlichkeit der Primzahlen)

Die Menge der Primzahlen ist nicht endlich.

In dieser Form bietet sich wie oben diskutiert ein Widerspruchsbeweis an: „Annahme, die Menge der Primzahlen ist endlich.“ Wir erzeugen einen Widerspruch und haben damit gezeigt, dass die Annahme falsch und damit die Menge der Primzahlen nicht endlich ist.

Gleiches gilt für einen weiteres fundamentales Ergebnis der Mathematik:

Satz (Irrationalität der Quadratwurzel aus 2)

$\sqrt{2}$ ist irrational (d. h. nicht rational).

Beweis

Annahme, $\sqrt{2}$ ist rational. Dann gibt es natürliche Zahlen n, m ≥ 2 mit $\sqrt{2}$ = n/m. Durch Kürzen des Bruchs können wir erreichen, dass n und m teilerfremd sind. Durch Quadrieren und Umformen erhalten wir

2m² = n².

Damit ist n² gerade, sodass n gerade ist. Dann ist aber n² durch 4 teilbar. Da m und n teilerfremd sind, ist m ungerade und damit m² ungerade. Folglich ist 2m² gerade, aber nicht durch 4 teilbar, während n² durch 4 teilbar ist. Also gilt 2m² ≠ n². Damit ist der Widerspruch erreicht. Dies zeigt, dass $\sqrt{2}$ irrational ist.

Wie der Begriff der Irrationalität wird der Begriff der Unendlichkeit in der Mathematik meistens nicht direkt, sondern als Negation der Endlichkeit eingeführt. Dies zu tun fällt in das Gebiet der Mengenlehre. Der heute übliche Standardzugang lautet:

Definition (endlich, unendlich)

Sei A eine Menge. Dann heißt A endlich, wenn es eine natürliche Zahl n ≥ 0 und eine Bijektion f : { 1, …, n } → A gibt, d. h. eine Funktion f von { 1, …, n } nach A derart, dass es für jedes a  ∈  A genau ein k  ∈  { 1, …, n } gibt mit f (k) = a. Andernfalls heißt A unendlich.

Ist A die leere Menge, so ist n = 0 und die leere Funktion f = { } geeignet, die Endlichkeit von A zu bezeugen. Die leere Menge ist damit endlich, wie es sein soll.

Die Verwendung von Bijektionen können wir vermeiden, indem wir die Definition äquivalent umformulieren: Eine Menge A ist genau dann endlich, wenn sie von der Form

A = { a₁, …, a_n } = { a | a = a₁ ∨ … ∨ a = a_n }

ist. Die Endlichkeit von A bedeutet also, dass wir die Elemente von A mit Hilfe der natürlichen Zahlen durchzählen oder indizieren können. Für die Unendlichkeit erhalten wir:

Satz (Charakterisierung der unendlichen Mengen)

Sei A eine Menge. Dann sind äquivalent:

(1)	A ist unendlich, d. h. es gibt keine natürliche Zahl n und a₁, …, a_n  ∈  A mit A = { a₁, …, a_n }.

(2)	Für alle natürlichen Zahlen n und alle a₁, …, a_n  ∈  A gibt es ein a  ∈  A mit a ≠ a₁, …, a_n.

Wir könnten diesen Satz als „offensichtlich“ einstufen und den Beweis überschlagen. Er lässt sich auch mit Hilfe der allgemeinen Verneinungsregeln für Quantoren einsehen. In der Tat wäre seine Diskussion bei einem Erstkontakt mit dem Satz von Euklid didaktisch eher hinderlich. Da es uns hier aber auf eine logische Detailanalyse der Beweisführung des Satzes von Euklid ankommt, geben wir einen ausführlichen Beweis.

Beweis

(1) impliziert (2):

Sei A unendlich. Weiter seien a₁, …, a_n  ∈  A (mit einer beliebigen natürlichen Zahl n). Wir zeigen:

(+) A ≠ { a₁, …, a_n }.

Hieraus folgt, dass ein a  ∈  A existiert mit a ≠ a₁, …, a_n, sodass (2) bewiesen ist.

Die Aussage (+) ist eine negierte Aussage (der Form „nicht gleich“), die wir durch einen Widerspruchsbeweis beweisen: Annahme, A = { a₁, …, a_n }. Dann ist A endlich nach Definition der Endlichkeit, im Widerspruch zur Voraussetzung der Unendlichkeit von A.

(2) impliziert (1):

Es gelte (2). Wir zeigen, dass A unendlich ist. Hierzu verwenden wir erneut einen Widerspruchsbeweis: Annahme, A ist endlich. Dann gibt es ein n und a₁, …, a_n mit A = { a₁, …, a_n }. Dies steht im Widerspruch zur Gültigkeit von (2).

Nach diesen Vorbereitungen betrachten wir nun den Satz von Euklid in der uns vertrauten Version:

Satz (Unendlichkeit der Primzahlen)

Sei n ≥ 1, und seien p₁, …, p_n Primzahlen. Dann gibt es eine Primzahl p, die von allen Primzahlen p₁, …, p_n verschieden ist.

In dieser Form lässt sich der Satz mit dem p₁ · … · p_n + 1 Argument beweisen, ohne dass dabei eine Annahme und ein zugehöriger Widerspruch auftauchen würde. Im Beweis des obigen Charakterisierungssatzes tauchen jedoch Widerspruchsbeweise auf. Wenn wir den Satz des Euklid in der Formulierung

Satz (Unendlichkeit der Primzahlen)

Die Menge der Primzahlen ist unendlich.

beweisen wollen, so verwenden wir in natürlicher Weise einen Widerspruchsbeweis, da „unendlich“ als „nicht endlich“ definiert ist. Damit ist unsere Ausgangsfrage, wie es sein muss, auf die Definitionen der Begriffe „endlich“ und „unendlich“ zurückgeführt. Oft werden diese Begriffe nicht definiert, was zu endlosen Diskussionen führen kann. Wir müssen also, wenn wir an den logischen Details des Beweises interessiert sind, nachfragen, welche Definition der Endlichkeit zugrunde liegt. Wer Unendlichkeit wie folgt definiert, kann die Unendlichkeit der Primzahlen ohne Annahme und Widerspruch beweisen:

Definition (Unendlichkeit, alternative Definition)

Eine Menge A heißt unendlich, falls für alle natürlichen Zahlen n und alle a₁, …, a_n  ∈  A ein a  ∈  A existiert mit a ≠ a₁, …, a_n.

Gleiches gilt für:

Definition (Unendlichkeit, alternative Definition II)

Eine Menge A natürlicher Zahlen heißt unendlich, falls für jede natürliche Zahl n₀ ein n  ∈  A existiert mit n ≥ n₀.

In der Mathematik einigt man sich in der Regel auf eine Definition, die aus gewissen Gründen als vorteilhaft angesehen wird. Ein Beispiel hatten wir mit der Frage, ob die 1 eine Primzahl ist oder nicht, schon diskutiert. Die oben angegebene mengentheoretische Definition der Endlichkeit ist der aktuelle Standard, und die Unendlichkeit wird hier durch „nicht endlich“ eingeführt. Die alternativen Definitionen sind äquivalent zu dieser Definition, aber in den Beweisen der Äquivalenzen können Beweismethoden versteckt sein, die bei der Anwendung der Äquivalenzen nicht mehr erkennbar sind.

Was ist nun so schlimm an Widerspruchsbeweisen, dass sie eine derartige Detailanalyse verdienen würden? Die Antwort ist: Nichts ist schlimm an Widerspruchsbeweisen. Aber jede Beweismethode der Mathematik verdient zum rechten Zeitpunkt eine genauere Betrachtung. Und im Fall der Widerspruchsbeweise ist diese Analyse oft mit der wesentlich gehaltvolleren Frage verbunden, ob ein Beweis konstruktiv ist oder nicht. Dieser Frage wollen wir uns nun zuwenden.