 Es gibt zwei Arten des Widerspruchsbeweises.
Die Unterschiede möchte ich erklären. Die beiden möglichen Varianten nenne ich die Echte und die Pseudo.
Die Unterscheidung zwischen Echt und Pseudo treffe ich anhand des Widerspruchs, der sich erweist. Die Behauptung (A=>B) soll bewiesen werden. Der Pseudo-Widerspruchsbeweis Man setzt A voraus und nimmt an, daß ¬B gilt.
Durch geeignete Argumentation kommt man zu dem Ergebnis, daß dann A nicht gelten kann. Eigentlich handelt es sich bei diese Variante aber nicht um einen Widerspruchsbeweis, sondern um den direkten Beweis der Kontraposition.
Denn hätte man A nicht vorausgesetzt, dann hätte man aus ¬B auch schon ¬A folgern können, und somit den direkten Beweis der Kontraposition (¬B=>¬A) gegeben.
Den 'direkten Beweis der Kontraposition' nennt man 'indirekten Beweis'.
[Die Kontraposition (Umkehrung) der Aussage (A=>B) lautet (¬B=>¬A), und beide Aussagen sind logisch äquivalent.] Der echte Widerspruchsbeweis Man setzt A voraus und nimmt an, daß ¬B gilt. Daraus folgert man durch geeignete Argumentation, daß auch B gilt. An diesem Widerspruch muß die Annahme ¬B schuld sein.
Wenn aber ¬B nicht gelten kann, dann muß (in einer zweiwertigen Logik) eben B gelten. Beispiel Wurzel-2 Zur Verdeutlichung dieser Unterscheidung erinnere ich an den Beweis der Behauptung: '$\sqrt{2}$ ist irrational'. Zunächst fällt auf, daß in der Behauptung keine Folgerung enthalten ist, wenigstens ist diese nicht deutlich.
Ich formuliere darum anders: (x²=2) => x ist irrational Beweisidee: Zeige (x²=2 Ù x ist rational => Widerspruch).
Der Widerspruch könnte darin bestehen, daß sich ergibt, daß dann x²¹2 ist (das wäre die erste, pseudo Variante), oder, daß x nicht rational sein kann (die zweite, echte Variante).
Im bekannten Beweis dieser Behauptung ergibt sich der Widerspruch gegen die Annahme, daß Wurzel 2 rational ist - der Wurzel-2-Beweis ist ein echter Widerspruchsbeweis. Zusammenfassung Wenn sich bei einem Widerspruchsbeweis der Behauptung (A=>B) ein Widerspruch (AÙ¬A) ergibt, dann handelt es sich im Grunde um einen direkten Beweis der Kontraposition (so etwas bezeichne ich als Pseudo-Widerspruchsbeweis).
Ergibt sich aber der Widerspruch (BÙ¬B), dann ist es ein echter Widerspruchsbeweis. Kann man denn immer beide Wege gehen? Nein, in den seltensten Fällen. Ein Widerspruchsbeweis ist unumgänglich, quasi obligatorisch, wenn gezeigt werden soll, daß eine bestimmte Eigenschaft nicht vorliegt. Es bleibt einfach keine Wahl, wenn man für die behauptete Eigenschaft keine positiven Kriterien kennt (Beispiel: irrational), aber das Gegenteil der Behauptung zuverlässig erkennen kann. Nur in den wenigsten Fällen kann man beide Varianten an einer Behauptung vorführen.
Heute habe ich ein solches multiples Beispiel gefunden und werde nun beide Varianten ausführen. Beispiel: "ungerade" Behauptung: Wenn n³ durch 2 teilbar ist, dann ist auch n durch 2 teilbar Zuerst der naheliegende Pseudo-Widerspruchsbeweis Sei n³ gerade.
Angenommen n ist ungerade, dann ist n = (2k+1), mit einem k aus IN.
Dann ist n³ = (2k+1)³ = 8k³ + 12k² + 6k + 1.
Die Summanden 8k³, 2k² und 6k sind alle gerade.
Eine gerade Zahl plus 1 ergibt eine ungerade Zahl, und das bedeutet einen Widerspruch zur Voraussetzung, daß n³ gerade ist. Soweit der Pseudo-Widerspruchsbeweis. Nun ein Echter Widerspruchsbeweis Sei n³ gerade. Angenommen n ist nicht gerade.
(Diesmal will ich folgern, daß die Annahme nicht haltbar ist.) Es ist n³ gerade, wenn es durch 2 teilbar ist (= beim Teilen durch 2 den Rest 0 läßt).
Also ist n³/2 eine ganze Zahl, und darum kann man eine ganze Zahl k finden, mit der gilt: n³ = 2k. Es ist n³ = n*n² = 2k <=> (n*n²)/2 = k Das k ist eine ganze Zahl. n ist nach Annahme ungerade, darum nicht durch 2 teilbar. Also ist n² durch 2 teilbar, denn wenn ein Produkt durch 2 teilbar ist, dann muß einer der Faktoren durch 2 teilbar sein. Wenn n² durch 2 teilbar ist, dann gibt es eine ganze Zahl m, für die gilt: n² = 2m. Somit ist n² = n*n = 2m. <=> (n*n)/2 = m. Das m ist eine ganze Zahl. n ist nach Annahme ungerade, darum nicht durch 2 teilbar. Da nun aber keiner der beiden Faktoren (n und n) durch 2 teilbar ist, erweist sich, daß die Annahme, daß n nicht durch 2 teilbar ist, nicht zu halten ist. In diesem Beispiel sind beide Varianten des Widerspruchsbeweisen möglich, weil sowohl die positive Eigenschaft (gerade) als auch die negative Eigenschaft (nicht gerade = ungerade) genau erkannt und charakterisiert werden können. Ist der Pseudo-Widerspruchsbeweis denn kein Beweis? Doch, es ist ein Beweis - kein Zweifel. Kann man die Kontraposition beweisen, dann ist die ursprüngliche Behauptung damit bewiesen. Oft enthält ein mathematischer Beweis mehrere Beweistechniken in bunter Mischung.
Manchmal sind die Übergänge fließend, vielleicht auch, weil der Autor nicht beabsichtigt hat, eine reine Anwendung der einen oder anderen Technik vorzuführen. Nun gilt für Beweise in der Mathematik (möglichst) das KUSS-Ideal (Kurz Und Sehr Schön), und es bleibt dem Leser überlassen, kurz und schön gegeneinander abzuwägen und seine persönliche Entscheidung zu treffen. Matroid 2002 PS: Auch der echte Widerspruchsbeweis macht keinen Gebrauch von Sätzen der Zahlentheorie über Primfaktorzerlegungen.
|
