Vollständige Induktion.

Gehen wir in der Menge der rationalen Zahlen $\mathbb {Q}$ von 0 aus und addieren fortgesetzt 1, so erhalten wir die natürlichen Zahlen $\mathbb {N}$ = {0, 1, 2,...}. Es ist also 0 eine natürliche Zahl und mit k ist auch k + 1 eine natürliche Zahl. Ist k $\in$ $\mathbb {N}$, so sind im Intervall [k, k + 1] nur die natürlichen Zahlen k und k + 1. Dies ist nicht sehr aufregend. Aber in der Menge der natürlichen Zahlen gibt es erstaunliche Dinge. Zum Beispiel kann man sich über folgendes wundern.

1 = 1 (1.1)

1 + 3 = 4 (1.2)

1 + 3 + 5 = 9 (1.3)

1 + 3 + 5 + 7 = 16 (1.4)

Wir schauen diese vier Zeilen an, und staunen. ,,Das Staunen ist eine Sehnsucht nach Wissen``. [#!Aquin:Piper!#, Seite 53] Ohne Vermuten kein Wissen und ohne Mut zum Ungewissen keine Vermutung. Also nehmen wir sinnende Haltung ein und vermuten tapfer:

1 + 3 + 5 +...+10001 = 5000²

Die Pünktchen ersetzen all die ungeraden Zahlen, die dort eigentlich hinzuschreiben wären. Die Endlichkeit des Papiers, des Bleistifts, die kurze Spanne unseres Lebens, und nicht zuletzt unser Umweltbewußtsein hindern uns daran selbiges zu tun. Wenn wir jetzt recht eifrig unseren Taschenrechner einen halben Tag lang betätigen oder ein kurzes Programm schreiben, so wird unsere Vermutung sich bestätigen. Wir sind aber nicht wesentlich schlauer als vorher. ,,Von Natur ist es dem Menschen eigen, nach der Erkenntnis der Wahrheit zu verlangen`` [#!Aquin:Piper!#, Seite 52] In diesem Verlangen unterstützt uns leider der Rechner nur wenig. Besser sind da schon unsere eigenen grauen Zellen. Wir bringen sie auf Trab und denken nach. Angenommen wir haben eine Zahl k $\in$ $\mathbb {N}$ für die folgendes gilt:

1 + 3 + 5 + ..... + 2k - 1 = k². (1.5)

Was erhalten wir, wenn wir die nächste ungerade Zahl dazuaddieren? Nach den bis zum Erbrechen bekannten binomischen Formeln gilt:

1 + 3 + 5 + 7.... + 2k - 1 + 2k + 1 = k² +2k + 1 = (k + 1)²

Jezt wissen wir auf einmal viel mehr wie vorher. Und zwar: Gilt die Behauptung für eine Zahl k, dann gilt sie für die darauffolgende Zahl (k + 1). Da die Behauptung für k = 1 gilt, ist sie sicher auch für k = 5000 richtig. Wir brauchen ja nur bis 5000 zählen. Durch einfaches Zählen verlassen wir nicht den Bereich der Zahlen für die die Behauptung gilt. Der Mathematiker betreibt seine Wissenbschaft unter dem Gesichtspunkt der Ewigkeit. Er ist der festen Überzeugung, dass irgendwer, irgendwo genug Zeit hat lange genug zu zählen. Jede natürliche Zahl ist also prinzipiell erreichbar. Für alle von 1 aus erzählbaren Zahlen ist aber unsere Behauptung sicher richtig. Also gilt sie für alle natürlichen Zahlen.

Definition 1.1.1   Eine Teilmenge T $\subset$ $\mbox{$\mathbb N$}$ heißt induktiv genau dann, wenn für alle k $\in$ T auch k + 1 $\in$ T ist. T ist also gegenüber Nachfolgern abgeschlossen.

In der ersten Aussage des nächsten Satzes steckt die Überzeugung, dass irgendwer stets lange genug zählen kann.

Satz 1.1.1   Es sind folgende Aussagen äquivalent:

1. Für jede induktive Teilmenge T von $\mbox{$\mathbb N$}$ gilt: Ist 0 $\in$ T, dann ist T = $\mbox{$\mathbb N$}$.
2. Jede nichtleere Teilmenge von $\mbox{$\mathbb N$}$ hat ein kleinstes Element.

Beweis:1. $\Longrightarrow$2. Sei M eine nichtleere Teilmenge von $\mbox{$\mathbb N$}$. Ist 0 $\in$ M dann ist 0 sicher kleinstes Element. Andernfalls ist 0 nicht aus M und

T = {x| x < yy &isin#in;M }

ist nichtleer. Angenommen M besitzt kein kleinstes Element. Zu x $\in$ T betrachten wir x + 1. Nun ist für beliebiges y $\in$ M x < y und also x + 1$\le$y. Wäre x + 1 $\notin$T, so gäbe es ein y $\in$ M mit x < y$\le$x + 1. Also ist x + 1 = y $\in$ M. Dann wäre aber x + 1 kleinstes Element von M. Das ist ein Widerspruch. Also ist x + 1 $\in$T und damit ist nach Aussage T = $\mbox{$\mathbb N$}$. Damit ist aber M leer. Und das ist ein Widerspruch zur Voraussetzung.

. $\Longrightarrow$. Sei 1 aus der induktiven Menge T. Wäre T $\neq$ $\mbox{$\mathbb N$}$, so wäre M = {x| x $\notin$T} nichtleer. M müßte wegen Teil ein kleinstes Element haben. Wir nennen es Min. Es ist Min > 1. Min - 1 $\notin$M also in T. Damit ist aber wieder Min - 1 + 1 = Min $\in$ T und damit nicht in M. Das ist ein Widerspruch. Also war M doch leer.

$\Box$

Um nun weiter Mathematik betreiben zu können müssen wir eine der beiden Aussagen glauben. Die andere ergibt sich dann rein logisch. Wer überhaupt nichts glaubt muß aufhören Mathematik zu treiben. ,, Ein jeder, der lernt, muß glauben, damit er zu vollkommenem Wissen gelange`` [#!Aquin:Piper!#, Seite 111]

Wir wollen die Aussage des Satzes als Induktionsaxiom bezeichnen. Aus dem Induktionsaxiom ergibt sich nun folgendes

Beweisverfahren.: Wir betrachten irgend eine Eigenschaft E, von der es sinnvoll ist, sie natürlichen Zahlen zuzusprechen. (,,Gelb``) gehört nicht dazu). T ist nun die Menge aller natürlichen Zahlen mit der Eigenschaft E, der sogenannte Gültigkeitsbereich von E. Ist 0 $\in$ T und T induktiv, dann ist T = $\mbox{$\mathbb N$}$. Manche Aussagen gelten erst ab einer gewissen Zahl k. Um auch diesen Fall möglichst glatt formulieren zu können führen wir folgende Sprechweise ein.

Definition 1.1.2   Eine Eigenschaft gilt für fast alle natürlichen Zahlen, wenn sie für höchstens endlich viele Zahlen nicht gilt. In diesem Fall gibt es eine kleinste Zahl n₀ , so dass für alle n$\ge$n₀ die Eigenschaft E gilt.