Dezember « 2011 « Flos Mathe-Blog

Den Standard-Beweis, dass $\sqrt{2}$ , die Quadratwurzel aus 2, keine Bruchzahl ist, kennt vermutlich fast jeder noch aus der eigenen Schulzeit. In dem vor zwei Jahren veröffentlichten Artikel “Roots of integers” in John D. Cook’s Blog (“The Endeavour“) entdeckte ich heute einen viel schöneren, weil allgemeineren Beweis dieser Tatsache, den ich nicht vorenthalten möchte.

Betrachtet man eine beliebige ganze Zahl $z$ und zieht deren $n$ -te Wurzel (falls $z \ge 0$ oder $n$ ungerade, ansonsten ist die $n$ -te Wurzel von $z$ nicht definiert), so gibt es nur zwei Möglichkeiten: Entweder die Wurzel ist ganzzahlig, oder sie ist eine irrationale Zahl. Ein irgendwie verblüffendes und doch einleuchtendes Resultat. Denkt man eine Weile über diese Aussage nach, so wird schnell intuitiv klar, dass sie richtig ist. Auch der Beweis ist nicht schwierig:

Sei $\frac{a}{b}$ eine vollständig gekürzte rationale Zahl. “Vollständig gekürzt” heißt, dass $a$ und $b$ keine gemeinsamen Teiler mehr haben. (Das ist keine echte Einschränkung, denn andernfalls lässt der Bruch sich um den größten gemeinsamen Teiler von $a$ und $b$ kürzen.) Weiter sei $n$ eine beliebige natürliche Zahl (und insbesondere nicht gleich 0).

Ist nun $\left(\frac{a}{b}\right)^n = \frac{a^n}{b^n}$ eine ganze Zahl, dann muss $b^n$ ein Teiler von $a^n$ sein. Aus dem Satz der eindeutigen Primfaktorzerlegung folgt, dass auch $b$ ein Teiler von $a$ sein muss. Da $a$ und $b$ als teilerfremd vorausgesetzt waren, gilt also $b = 1$ (ein negatives Vorzeichen können wir ggf. im Zähler $a$ des Bruches unterbringen, denn $\frac{a}{-b} = \frac{-a}{b}$ ).

Also ist auch $\frac{a}{b}$ eine ganze Zahl!

Wir können jetzt sofort per Widerspruchsbeweis die Behauptung folgern: Wäre die $n$ -te Wurzel der ganzen Zahl $z$ ein echter Bruch, das heißt $\sqrt[n]{z} = \frac{a}{b}$ für geeignete teilerfremde Zahlen $a \in \mathbb{Z}$ und $b \in \mathbb{N}$ mit $b > 1$ , dann wäre $\left(\frac{a}{b}\right)^n = z$ keine ganze Zahl (denn das geht nur für $b=1$ ).

Es können als Wurzeln von ganzen Zahlen also nur ganze oder irrationale Zahlen auftreten. Da $2$ offenbar keine Quadratzahl ist (denn zwischen $1^2 = 1$ und $2^2 = 4$ gibt es keine weiteren Quadratzahlen), muss $\sqrt{2}$ folglich irrational sein. Dasselbe gilt für alle $n$ -ten Wurzeln (für $n > 1$ ) aus ganzen Zahlen, die nicht Quadratzahlen sind.

Insbesondere sind zum Beispiel die Wurzeln aus Primzahlen immer irrational!

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 $A$ 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 $A$ , das heißt $\neg A$ . Nun versuchen wir, mit Hilfe von bereits bekannten Tatsachen und gültigen Umformungen und Schlussfolgerungen, aus $\neg A$ einen Widerspruch herzuleiten. Gelingt uns dies, dann wissen wir: Wäre die Aussage $A$ 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 $A$ 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).

Ein Schachbrett, auf dem die Felder a1 und h8 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 $P$ und betrachten dann das Produkt

$1 \cdot 2 \cdot 3 \cdot 4 \cdot \ldots \cdot P = P!$

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

Wir wissen aber, dass jede Zahl sich als Produkt von Primzahlen schreiben lässt. Da $P$ die größte Primzahl ist, müsste also eine der Zahlen $1, 2, 3, \ldots, P$ ein Teiler von $P! + 1$ sein.

Wir konnten aus der Annahme, es gäbe nur endlich viele Primzahlen, also sowohl herleiten, dass $P! + 1$ durch eine der ersten $P$ 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

M	D	M	D	F	S	S
« Sep
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Monthly Archive for Dezember, 2011

(Quadrat-)Wurzeln aus ganzen Zahlen