Indirekter Beweis
Der indirekte Beweis ist eine Beweistechnik, bei der eine Aussage angenommen wird, die widerlegt werden soll. Aus dieser Aussage wird ein Widerspruch hergeleitet, ihre Falschheit ist damit erwiesen.
Intuitive Erläuterung
Ein einfaches Beispiel: Wir wollen zeigen, dass nicht alle Menschen Griechen sind. Was wir annehmen ist das genaue Gegenteil, nämlich dass alle Menschen Griechen sind. Aus dieser Annahme folgt, dass Cicero ein Grieche ist. Wir wissen aber, dass Cicero kein Grieche ist (sondern Römer). Dass Cicero aber gleichzeitig ein Grieche und kein Grieche sein sollte, ist ein Widerspruch. Also haben wir gezeigt, was wir wollten, nämlich, dass nicht alle Menschen Griechen sind.
Ein weniger triviales Beispiel für einen indirekten Beweis und vielleicht das bekannteste Beispiel überhaupt für einen solchen, ist der Satz von Euklid, bei dem gezeigt wird, dass es keine größte Primzahl geben kann (dass es also zu jeder Primzahl eine größere gibt), indem die Annahme, es gebe eine größte, widerlegt wird.
Der indirekte Beweis lässt sich wie folgt intuitiv rechtfertigen: Wenn sich aus einer Annahme ein Widerspruch herleiten lässt, dann gilt, dass, wenn die Annahme wahr ist, auch der Widerspruch wahr ist. Ein Widerspruch kann aber niemals wahr sein. Die Annahme kann daher nicht wahr sein, muss also falsch sein
Formale Darstellung
Formal lässt sich der Widerspruchsbeweis wie folgt darstellen:
Gilt 
und 
dann gilt: 
.
Lies: Gilt, dass aus der Aussagenmenge Γ zusammen mit der Aussage A sowohl die Aussage B als auch die Aussage nicht-B folgt, so folgt aus Γ nicht-A.
Dieser Zusammenhang ist im Kalkül des natürlichen Schließens auch als Negationseinführung bekannt.
Wahlweise ist auch folgende Formulierung möglich:
Gilt 
, wobei b eine Elementaraussage ist, die weder in Γ noch in A noch in einem Axiom vorkommt, dann gilt: .
Klassischer und intuitionistischer Widerspruchsbeweis
Vom indirekten Beweis gibt es noch eine zweite Form, die in der Auseinandersetzung zwischen klassischer und intuitionistischer Logik wichtig ist:
Gilt 
und 
dann gilt: 
.
Der Unterschied zwischen den beiden Formen ist, dass in der ersten aus einer Aussage und einem Widerspruch auf die Negation der Aussage geschlossen wird, während in der zweiten aus der Negation und einem Widerspruch auf die Aussage selbst geschlossen wird.
Die erste Form lässt sich mittels der klassischen Negationsbeseitigung in die zweite überführen:
Gilt 
so gilt auch: .
Da dieses Gesetz aber eben nur klassisch, nicht intuitionistisch gültig ist, ist auch die unten genannte Form des indirekten Beweises intuitionistisch nicht allgemein gültig. Dies hat zur Folge, dass in der intuitionistischen Mathematik die Existenz gewisser Objekte der klassischen Mathematik nicht anerkannt wird, siehe auch Konstruktivismus.
Kategorie:Logik