Dedekind-Peano-Axiome/Zählen/Induktionsprinzip/Minimum/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Eine Visualisierung des Induktionsprinzips. Wenn die Steine nah beieinander stehen und der erste umgestoßen wird, so fallen alle Steine um.

Die folgende Aussage und ihr Beweis begründen das Beweisprinzip der vollständigen Induktion. Wir schreiben für den Nachfolger.



Satz  

Für jede natürliche Zahl sei eine Aussage gegeben. Es gelte

  1. ist wahr.
  2. Für alle gilt: wenn gilt, so ist auch wahr.

Dann gilt für alle .

Beweis  

Es sei

Wir wollen zeigen, dass ist, denn genau dies bedeutet, dass die Aussage für alle gilt. Nach der ersten Bedingung ist

Nach der zweiten Voraussetzung gilt für , dass aus stets folgt. Damit erfüllt beide Voraussetzungen im Induktionsprinzip für Mengen, so dass gilt.


Der Nachweis von (der Gültigkeit von) heißt dabei der Induktionsanfang und der Schluss von auf heißt der Induktionsschluss oder Induktionsschritt. Innerhalb des Induktionsschlusses nennt man die Gültigkeit von auch die Induktionsvoraussetzung. In manchen Situationen ist die Aussage erst für für ein gewisses (definiert oder) wahr. Dann beweist man im Induktionsanfang die Aussage und den Induktionsschritt führt man für alle durch.

Um dieses Beweisprinzip anhand von substantiellem Material demonstrieren zu können, greifen wir etwas vor und setzen die Addition, die Multiplikation und die Größergleichrelation von natürlichen Zahlen voraus. Das folgende Standardbeispiel für einen Induktionsbeweis verwendet das Summenzeichen. Für gegebene (natürliche, reelle) Zahlen bedeutet

Dabei hängen typischerweise die in einer formelhaften Weise von ab. Entsprechend ist das Produktzeichen definiert, nämlich durch


Aufgabe

Beweise durch Induktion die folgende Formel für .


Lösung

Beim Induktionsanfang ist , daher besteht die Summe links nur aus einem Summanden, nämlich der , und daher ist die Summe . Die rechte Seite ist , so dass die Formel für stimmt.

Für den Induktionsschritt setzen wir voraus, dass die Formel für ein gilt, und müssen zeigen, dass sie auch für gilt. Dabei ist beliebig. Es ist

Dabei haben wir für die zweite Gleichheit die Induktionsvoraussetzung verwendet. Der zuletzt erhaltene Term ist die rechte Seite der Formel für , also ist die Formel bewiesen.


Aussagen, die durch Induktion bewiesen werden können, können manchmal auch auf andere Art bewiesen werden. Im vorstehenden Beispiel gibt es die elegantere und einsichtigere Lösung, die Zahlen einmal aufsteigend und einmal absteigend untereinander hinzuschreiben, also

Spaltenweise ergibt sich , und diese Summe kommt -mal vor. Also ist


Aufgabe

Zeige durch vollständige Induktion, dass für jedes die Zahl

ein Vielfaches von ist.


Lösung

Induktionsanfang. Für ist

ein Vielfaches von . Induktionsschritt. Sei nun die Aussage für bewiesen und betrachten wir den Ausdruck für . Dieser ist

wobei im letzten Schritt die Induktionsvoraussetzung verwendet wurde (nämlich die Eigenschaft, dass ein Vielfaches von ist). Daher ist diese Zahl ein Vielfaches von .


Aus dem Induktionsprinzip folgt die nächste wichtige Eigenschaft. Vom intuitiven Standpunkt her ist sie selbstverständlich, wir führen sie aber trotzdem auf das Induktionsprinzip zurück. Es geht in diesem Beweis weniger dadrum, sich über die Satzaussage zu vergewissern, sondern vielmehr Einblicke in mathematisches Argumentieren zu gewinnen. Es ist auch ein Beispiel dafür, wie man eine Aussage über Teilmengen zu einer Aussage über natürliche Zahlen macht, um das Induktionsprinzip anwenden zu können.



Lemma  

Jede nichtleere Teilmenge

besitzt ein Minimum.

Beweis  

Wir betrachten die Aussage

= Alle Teilmengen von , die enthalten, besitzen ein Minimum.

Da jede nichtleere Teilmenge mindestens ein besitzt, ist die Aussage des Satzes äquivalent zur Gültigkeit von für alle . Diese Aussage können wir durch Induktion beweisen. Die Aussage besagt, dass jede Teilmenge , die die enthält, auch ein Minimum enthält. Dies ist aber klar, da dann eben das Minimum ist. Sei die Aussage nun für alle schon bewiesen. Wir müssen beweisen. Sei also eine Teilmenge, die enthält. Wenn auch eine Zahl besitzt, so besitzt nach der Induktionsvoraussetzung ein Minimum. Andernfalls besitzt keine Zahl, die kleiner als ist. Dann ist aber das Minimum von .