Unendlicher Abstieg

Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Bitte hilf mit, die Mängel dieses Artikels zu beseitigen, und beteilige dich bitte an der Diskussion!

Das Prinzip des Unendlichen Abstiegs ist ein mathematisches Beweisverfahren. Es wird verwendet, um Aussagen zu widerlegen. Hierbei wird ausgenutzt, dass jede Teilmenge der Natürlichen Zahlen ein kleinstes Element besitzt.

Ursprung

Die Methode des unendlichen Abstiegs wurde im 17. Jahrhundert von Pierre de Fermat entwickelt. Er nutzte das Prinzip, um viele seiner mathematischen Ergebnisse zu beweisen. Unter anderem wurde ein Spezialfall (n = 4) von Fermats großem Satz mit dieser Methode bewiesen.

Allgemeines Vorgehen

Die Aufgabe besteht darin, zu beweisen, dass ein gegebenes mathematisches Problem keine Lösung in den natürlichen Zahlen besitzt. Bekannt ist, dass jede nicht leere Teilmenge der natürlichen Zahlen ein kleinstes Element hat. Da die Lösungsmenge eine solche Teilmenge der natürliche Zahl darstellt, muss es, falls es eine Lösung gibt, eine kleinste geben. Der Beweis startet nun mit der Annahme der Existenz einer hypothetischen Lösung. Daraus folgt sofort, dass es eine kleinste Lösung m geben muss. Aus dieser Lösung, von der angenommen wurde, dass es die kleinste ist, konstruiert man mit Hilfe der Eigenschaften der natürlichen Zahlen und der Problemstellung eine noch kleinere Lösung. Diesen Prozess kann man wiederholen und erhält immer kleinere Lösungen in natürlichen Zahlen. Aus dem Widerspruch zur Annahme, dass m die kleinste Lösung ist, folgt, dass von einer falschen Annahme ausgegangen wurde. Die einzige Annahme die getroffen wurde, war die der Existenz einer Lösung. Dies ist somit die einzig mögliche Fehlerquelle. Folglich existiert keine Lösung für dieses Problem.

Induktiver Beweis für nicht-Existenz einer Lösung

Wir nehmen an, wir könnten aus einer angeblich kleinsten Lösung eine kleinere konstruieren. Dies ist genau das entscheidende Fragment, auf dem das Prinzip des unendlichen Abstiegs beruht, und für einen konkreten Beweis gefunden werden muss.

• Induktionsanfang. Sei 0 die kleinste Lösung. Dann gibt es eine natürliche Zahl kleiner 0, die eine Lösung darstellt. Widerspruch — 0 kann also nicht die kleinste Lösung sein.
• Induktionsannahme: Für alle $k\leq k_0$ haben wir gezeigt, dass sie nicht die kleinste Lösung sein können.
• Induktionsschritt: k₀ + 1 ist ebenfalls nicht die kleinste Lösung, denn die unter dieser Annahme konstruierte kleinere Lösung ist Element von $\{0,\ldots, k_0\}$, und wenn überhaupt eine Lösung, dann nicht die kleinste.

Alles zusammengenommen existiert also keine kleinste Lösung, und damit gar keine.

Beispiele

Die Wurzel aus 2 ist irrational

Beweis:

Annahme: Die Wurzel aus 2 ist rational.

Dies bedeutet (weil $\sqrt 2$ gewiss positiv ist), dass es natürliche Zahlen x,y gibt mit $\sqrt{2}=\tfrac{x}{y}$. Diese Zahlen sind dadurch gleichzeitig Lösung der Gleichung $x^2 = 2\cdot y^2$. Aus solch einer Lösung lässt sich eine kleinere Lösung x₁,y₁ konstruieren, und zwar kleiner in dem Sinne, dass y₁ < y gilt.

Wegen x² = 2y² > y² ist gewiss x > y, also ist y₁: = x − y eine natürliche Zahl. Ebenso ist wegen $(2y)^2 > 2\cdot y^2 = x^2$ gewiss 2y > x und somit x₁: = 2y − x eine natürliche Zahl. Aus 2y > x folgt außerdem noch wie gewünscht y > x − y = y₁.

Nun rechnet man unter Benutzung von x² = 2y² nach: $x_1^2 = (2y-x)^2 = 4 y^2 - 4 x y + x^2 = 2 y^2 + x^2 - 4x y + x^2 = 2\cdot(y^2-2 x y +x^2) = 2\cdot (x-y)^2 = 2 y_1^2$, also ist (x₁,y₁) tatsächlich eine Lösung obiger Gleichung, bzw. es gilt auch $\sqrt 2 = \tfrac{x_1}{y_1}$.

Wenn es jedoch überhaupt eine Lösung der Gleichung gibt, dann gibt es unter allen Lösungen auch eine mit minimalem y. Die Konstruktion einer kleineren Lösung liefert somit einen Widerspruch. Die Annahme, das $\sqrt 2$ rational ist, ist also falsch. Folglich ist die Wurzel aus 2 irrational.

Man kann ähnlich auch dann schließen, wenn man nicht davon ausgeht, dass die ursprüngliche Lösung (x,y) minimal ist: Man konstruiert wie oben eine Lösung mit y₁ < y, daraus auf dieselbe Weise eine mit y₂ < y usw. Es ergibt sich eine unendlich absteigende Folge von Nennern $y>y_1 >y_2 >y_3>\ldots$, was innerhalb der natürlichen Zahlen nicht möglich ist, also wiederum einen Widerspruch bedeutet.

Quellen

• "Das kleine Einmaleins des klaren Denkens: 22 Denkwerkzeuge für ein besseres Leben" von Christian Hesse, Verlag: Beck; Auflage: 2 (14. Mai 2009)
• Matroids Matheplanet: Der unendliche Abstieg