Die Unendlichkeit der natürlichen Zahlen und die Beweismethode der vollständigen Induktion

Gliederung

1. Die Unendlichkeit der natürlichen Zahlen
1.1 Begründung hinsichtlich der Peano-Axiome
1.2 Hilberts Hotel
1.3 Mächtigkeit

2. Die Methode der Vollständigen Induktion
2.1 Grundprinzip
2.2 Herleitung des Verfahrens der vollständigen Induktion
2.3 Allgemeiner Aufbau
2.4 Verlagerung des Induktionsanfangs
2.5 Didaktische Darstellung
2.6 Beispiele
2.6.1 Geometrische Beispiele
2.6.2 Beweis der BERNOUILLIschen Ungleichung
2.6.3 Beweis zur Teilbarkeit
2.7 Häufige Fehler

3. Literatur:

1. Die Unendlichkeit der natürlichen Zahlen

1.1 Begründung hinsichtlich der Peano-Axiome

Peano-Axiome (vgl. Padberg 1999, S.26)

Abbildung in dieser Leseprobe nicht enthalten

Die 1 ist eine natürliche Zahl

2. Für alle x [Abbildung in dieser Leseprobe nicht enthalten] N gilt: v(x) [Abbildung in dieser Leseprobe nicht enthalten] 1

Die 1 ist kein Nachfolger irgendeiner natürlichen Zahl

3. Für alle x, y [Abbildung in dieser Leseprobe nicht enthalten]N gilt: Aus x [Abbildung in dieser Leseprobe nicht enthalten]y folgt v(x) [Abbildung in dieser Leseprobe nicht enthalten] v(y)

Verschiedene Zahlen haben verschiedene Nachfolger

4. Ist M eine Teilmenge von N mit 1 [Abbildung in dieser Leseprobe nicht enthalten] M und enthält M zu jedem Element auch

dessen Nachfolger, so gilt M = N

Die Menge der natürlichen Zahlen wird über die Peano-Axiome definiert. Wenn wir nun davon ausgehen, dass alle Axiome erfüllt sind, müssen in dieser Menge sämtliche Elemente der natürlichen Zahlen enthalten sein. Rekursiv lässt sich nach den Axiomen der Bereich der natürlichen Zahlen auch so definieren:

Abbildung in dieser Leseprobe nicht enthalten

Mit dieser Schreibweise kann man erkennen, dass die Menge der natürlichen Zahlen unendlich viele Elemente aufweist, da jede Zahl einen Nachfolger besitzt und deshalb immer eine größere Zahl existiert.

Über das vierte Peano-Axiom kann man hier anmerken, das dieses die Grundlage für die Beweismethode der vollständigen Induktion ist.

1.2 Hilberts Hotel

Um der Unendlichkeit ein wenig ihre Abstraktheit zu nehmen und ihr „in mancher Hinsicht ganz anderes Verhalten als von endlichen Mengen“ (Reis 2005, S. 33) zu erläutern, wird auch gerne das bekannte Beispiel von David Hilbert (1862-1943) benutzen.

„Das Hotel Universum hat die unendlich vielen Zimmer 1, 2, 3, …, die an diesem Tag alle belegt sind. Nun kommt jedoch noch ein Wanderer, der ein Zimmer für die Nacht sucht. Der Hotelier löst dieses Problem geschickt, indem er dem „Neuen“ das Zimmer mit der Nummer 1 zuweist und die übrigen Hotelgäste bittet, in das Zimmer mit der nächst höheren Zimmernummer umzuziehen. So haben alle ein Dach über dem Kopf.“ (vgl. Padberg 1999, S.45)

Mathematisch gesehen haben wir hier „eine Abbildung f : N Abbildung in dieser Leseprobe nicht enthalten N \ {1} auf der Menge der Hotelzimmer definiert mit f : x Abbildung in dieser Leseprobe nicht enthalten x+1“ mit f ist bijektiv.

1.3 Mächtigkeit

Satz 2.2.1 (vgl. Reis 2005, S. 34)

Es gibt genauso viele natürliche Zahlen wie es gerade natürliche Zahlen gibt. Die Mächtigkeit von N ändert sich nicht, wenn man 10, 100, 1000 Zahlen wegnimmt. Sei etwa M = N \ {1,2,3… ,100} dann ist Abbildung in dieser Leseprobe nicht enthalten = Abbildung in dieser Leseprobe nicht enthalten

Der Hotelier konnte sein Problem natürlich nur lösen, da er in seinem Hotel unendlich viele Zimmer zur Verfügung stehen hat. Er könnte auch noch abzählbar unendlich viele Personen in seinem Hotel unterbringen, indem er jeden Hotelgast bittet von seinem Zimmer n in das Zimmer 2n umzuziehen. Nun wären alle Zimmer mit ungerader Nummer unbelegt und frei für die abzählbar unendlich vielen neuen Gäste. Wenn der Hotelier gleich ein „paar“ Zimmer mehr freihaben möchte, so zu sagen als Reserve, könnte er die Hotelgäste von n nicht nach 2n verlegen sondern in die Zimmer 3n oder 5n.

Es gilt allgemein:

Definition 9 (vgl. Padberg 1999, S.46)

Sei M eine Menge. M heißt genau dann unendlich, wenn es eine echte Teilmenge T von M und eine bijektive [Abbildung in dieser Leseprobe nicht enthalten]

F : M [Abbildung in dieser Leseprobe nicht enthalten] T gibt mit f(M) = T.

M heißt genau dann endlich, wenn M nicht unendlich ist.

2. Die Methode der Vollständigen Induktion

2.1 Grundprinzip

Das Verfahren der vollständigen Induktion, beruht auf dem Satz der vollständigen Induktion (vgl. Gorski/ Müller-Philipp 2005, S. 8):

Sei M[Abbildung in dieser Leseprobe nicht enthalten] N und es gelten die beiden folgenden Bedingungen:

Abbildung in dieser Leseprobe nicht enthalten

2. [Abbildung in dieser Leseprobe nicht enthalten] N gilt: n[Abbildung in dieser Leseprobe nicht enthalten]M [Abbildung in dieser Leseprobe nicht enthalten] (n+1)[Abbildung in dieser Leseprobe nicht enthalten]M

Dann gilt M = N

Das heißt also, gibt es eine Menge von natürlichen Zahlen, die die 1 enthält, und wenn zu jedem beliebigem Element n der Menge M auch sein Nachfolger (n+1) gehört, dann muss die Menge M mit der Menge N identisch sein.

Anzumerken ist hier, dass die Beweismethode der vollständigen Induktion nur auf die natürlichen Zahlen anwendbar ist, da auf andere Zahlbereiche keine bijektive Abbildung existiert.

2.2 Herleitung des Verfahrens der vollständigen Induktion

Im Folgenden soll das Prinzip der Beweismethode der vollständigen Induktion an der Ermittlung der Summen aufeinander folgender, ungerader, natürlichen Zahlen ermittelt werden:

Abbildung in dieser Leseprobe nicht enthalten

Die folgende geometrische Darstellung soll diesen Zusammenhang nochmals verdeutlichen:

Aufgrund dieser Ergebnisse lässt sich vermuten, dass sich diese Reihe unendlich fortsetzen lässt, so dass gilt:

A(n): [Abbildung in dieser Leseprobe nicht enthalten] = [Abbildung in dieser Leseprobe nicht enthalten] N

Die Richtigkeit der Vermutung wurde bis jetzt nur für die ersten vier Glieder der Zahlenfolge bewiesen. Es ist somit nicht auszuschließen, dass ein beliebiges n-tes Glied die Vermutung widerlegt. Somit muss die oben genannte Aussage erst bewiesen werden, wozu die allgemeine Nachfolgeeigenschaft der natürlichen Zahlen hinzugezogen wir:

„Wenn eine Aussage A für eine bestimmte Zahl n0 […] gilt und es außerdem zu zeigen gelingt, dass aus der angenommenen Gültigkeit für eine beliebige Zahl k stets die Gültigkeit für die folgende Zahl (k+1) folgt, so erreicht man jede natürliche Zahl.“ (Weber/ Zillmer 1996, S. 44)

[...]