Reductio ad absurdum

Grundidee des Widerspruchsbeweises

Die Reductio ad absurdum ist eine Schlussfigur und Beweistechnik der Logik. Eine Aussage wird dabei widerlegt, indem aus ihr ein logischer Widerspruch oder ein Widerspruch zu einer bereits anerkannten These folgt.

Als „indirekter Beweis“, „Widerspruchsbeweis“ oder „Beweis durch Widerspruch“ beweist man eine Aussage nicht unmittelbar. Stattdessen nimmt man ihr kontradiktorisches Gegenteil an, also dass die Aussage nicht zutrifft, und widerlegt diese Annahme. In der klassischen zweiwertigen Logik ist jede Aussage entweder wahr oder falsch. Ist ihr Gegenteil widerlegt, gilt die ursprüngliche Aussage daher als korrekt.

Anschauliche Erklärung und Beispiele

Um zu zeigen, dass nicht alle Menschen Griechen sind, kann man zunächst annehmen, alle Menschen seien Griechen. Dann wäre auch Cicero Grieche. Da bekannt ist, dass Cicero kein Grieche, sondern Römer war, entstünde der Widerspruch, dass Cicero zugleich Grieche und kein Grieche wäre. Die Annahme ist damit widerlegt; folglich sind nicht alle Menschen Griechen.

Ein bedeutendes mathematisches Beispiel ist eine Beweisvariante zum Satz des Euklid: Es gibt keine größte Primzahl, also gibt es zu jeder Primzahl eine größere. Dies wird gezeigt, indem die Annahme einer größten Primzahl zum Widerspruch führt. Als weiteres bekanntes Beispiel wird der Beweis der Irrationalität der Wurzel aus 2 bei Euklid genannt.

Die Rechtfertigung lautet: Folgt aus einer Annahme ein Widerspruch, wäre bei wahrer Annahme auch der Widerspruch wahr. Ein Widerspruch kann jedoch niemals wahr sein. Die Annahme muss deshalb falsch sein.

Formale Grundform

Die formale Form des Widerspruchsbeweises lautet:

Γ ∪ {A} ⊢ B und Γ ∪ {A} ⊢ ¬B, dann Γ ⊢ ¬A.

Dabei ist Γ eine Aussagenmenge, A eine zusätzlich angenommene Aussage, B eine Aussage und ¬ die Negation. Wenn aus Γ zusammen mit A sowohl B als auch nicht-B folgt, dann folgt aus Γ nicht-A. Im Kalkül des natürlichen Schließens heißt dieser Schluss Negationseinführung.

Klassische und intuitionistische Form

Eine zweite Form lautet:

Γ ∪ {¬A} ⊢ B und Γ ∪ {¬A} ⊢ ¬B, dann Γ ⊢ A.

Hier wird aus der Annahme nicht-A ein Widerspruch hergeleitet; daraus wird direkt auf A geschlossen. Kurz: Eine Behauptung gilt als bewiesen, wenn aus ihrer Negation ein Widerspruch folgt.

Die erste Form führt aus A und einem Widerspruch auf ¬A. Die zweite führt aus ¬A und einem Widerspruch auf A. Die Überführung der ersten in die zweite benötigt in der klassischen Logik die Negationsbeseitigung: Gilt Γ ⊢ ¬¬A, so gilt auch Γ ⊢ A. Dieses Gesetz gilt jedoch nicht allgemein in der intuitionistischen Logik. Dasselbe gilt für eine Herleitung mit dem Satz vom ausgeschlossenen Dritten. Deshalb ist die zweite Form des Widerspruchsbeweises intuitionistisch nicht allgemein gültig.

Diese Ablehnung bewirkt, dass die intuitionistische Mathematik die Existenz bestimmter Objekte der klassischen Mathematik nicht anerkennt.