Archive for the 'Paradoxa' Category

Was ist der Beweis durch Widerspruch?

Um eine Aussage zu verifizieren kann man sich in der Mathematik vieler allgemeiner Beweis-Methoden bedienen. Eine davon ist etwa das sehr intuitive Schubfachprinzip. Auch der Beweis durch Widerspruch ist eine recht anschauliche Beweis-Methode, die in vielen Fällen Verwendung findet.

Oft ist dabei der Beweis durch Widerspruch, oder auch “indirekter Beweis”, sogar leichter zu führen als der “direkte”.

Und wie funktioniert das?

Nehmen wir einmal an, wir wollen die Aussage beweisen (zum Beispiel: “Es gibt unendlich viele Primzahlen” oder “Ein Schachbrett, auf dem zwei gegenüberliegende Ecken verdeckt sind, lässt sich nicht lückenlos mit 2×1-Dominosteinen überdecken”). Der direkte Beweis, das heißt die “direkte” Folgerung der Aussage aus anderen, schon bekannten Aussagen, will uns dabei aber nicht gelingen oder ist zu aufwändig. Dann können wir einen Umweg gehen, und die Gültigkeit der Aussage A indirekt beweisen. Die Artikelüberschrift verrät, dass ein Widerspruch dabei die zentrale Rolle spielt.

Wir betrachten dazu die Negation der Aussage , das heißt . Nun versuchen wir, mit Hilfe von bereits bekannten Tatsachen und gültigen Umformungen und Schlussfolgerungen, aus einen Widerspruch herzuleiten. Gelingt uns dies, dann wissen wir: Wäre die Aussage nicht wahr, dann könnten wir – mit gültigen Schlüssen – widersprüchliche Aussagen beweisen.

Gehen wir davon aus, dass die Mathematik widerspruchsfrei ist (So gutgläubig [1] muss man sein, auch wenn das nachgewiesenermaßen nicht beweisbar ist.), so muss dann die Aussage wahr sein!

Ein erstes Beispiel

Als Anwendung zeigen wir nun, dass sich ein Schachbrett nicht lückenlos mit Dominosteinen überdecken lässt, die 2×1 Felder groß sind, wenn zwei gegenüberliegende Ecken des Brettes nicht belegt werden dürfen (z.B. weil sie verdeckt oder ausgeschnitten sind).

Zwei gegenüberliegende Ecken fehlen dem Schachbrett

Wir nehmen dazu an, das Schachbrett ließe sich mit solchen 2×1-Dominos lückenlos überdecken. Betrachten wir das Brett nicht nur als ein 8×8 Felder großes Raster, sondern beachten auch die abwechselnd schwarz und weiß (bzw. rot und blau, Schach ist bunt!) gefärbten Felder, so stellen wir fest: Jeder Dominostein bedeckt genau ein Feld jeder Farbe, das heißt in unserem Fall genau ein rotes und ein blaues Feld. Zählen wir die roten und blauen Felder, dann bemerken wir dabei auch schnell, dass es 32 blaue, aber nur 30 rote Felder gibt. (Zählen müssen wir gar nicht, und auch die konkreten Anzahlen sind unwichtig: Auf dem normalen Schachbrett, bevor wir die Eckfelder ausgeschnitten haben, gibt es gleich viele Felder jeder Farbe, die beiden entfernten Eckfelder waren beide rot. Also gibt es jetzt zwei rote Felder weniger als blaue, mehr müssen wir nicht wissen.)

Und das ist auch schon unser Widerspruch! Mit jedem Dominostein verdecken wir ein rotes und ein blaues Feld, niemals jedoch zwei blaue. Die angenommene lückenlose Überdeckung kann es nicht geben, da sonst (mindestens) ein Dominostein mehr blaue als rote Felder überdecken müsste.

Ein zweites Beispiel

In diesem zweiten Beispiel wird noch klarer, was der Widerspruch eigentlich bedeutet. (Im ersten Beispiel hätte man mit Hilfe der Farben der Felder auch noch “direkter” vorgehen können.) Wir wollen zeigen, dass es unendlich viele Primzahlen gibt.

Unsere Annahme ist jetzt also, es gäbe nur endlich viele Primzahlen. Dann muss es auch eine größte Primzahl geben, denn könnten wir zu jeder Primzahl eine noch größere finden, dann gäbe es eben mehr als endlich viele Primzahlen. Wir nennen diese (hypothetisch existierende) größte Primzahl und betrachten dann das Produkt

aller Zahlen von 1 bis einschließlich (siehe: Fakultät). Addieren wir zu dieser (riesig großen) Zahl nun noch dazu, so erhalten wir eine Zahl , die durch keine der Zahlen teilbar ist. Denn beim Teilen durch eine dieser Zahlen lässt offenbar immer den Rest .

Wir wissen aber, dass jede Zahl sich als Produkt von Primzahlen schreiben lässt. Da die größte Primzahl ist, müsste also eine der Zahlen ein Teiler von sein.

Wir konnten aus der Annahme, es gäbe nur endlich viele Primzahlen, also sowohl herleiten, dass durch eine der ersten natürlichen Zahlen teilbar ist, als auch, dass dies nicht der Fall ist. Ein Widerspruch!

Die anfängliche Annahme kann also nicht richtig sein, es muss demnach unendlich viele Primzahlen geben.

Mit einem Zitat von G. H. Hardy (Schachspieler und Mathematiker) zum Beweis durch Widerspruch schließt sich der Kreis in Bezug auf das erste Beispiel: “[Er] ist eine der schärfsten mathematischen Waffen. Dies ist ein weit kühnerer Zug als jedes Gambit im Schach; ein Schachspieler opfert dabei einen Bauern oder eine Figur, ein Mathematiker riskiert das ganze Spiel.”

Fußnoten

[1] “Gott existiert, weil die Mathematik widerspruchsfrei ist, und der Teufel existiert, weil wir das nicht beweisen koennen.” – André Weil