Hallo,
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: '
Ö
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 (
K
urz
U
nd
S
ehr
S
chö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.
