lambdas Kosmos

Ja, vollständige Induktion. Was soll dieses scheinbar völlig nichtssagende und lächerliche Beweisverfahren, wo man immer prüfen muss, ob die Formel für 1 gilt? Wird sich der Anfänger fragen. Dieser Artikel richtet sich an all diejenigen, die noch nicht lange genug über vollständige Induktion nachgedacht haben. ;) Zur "Erleuchtung" kommen, dabei soll dieser Artikel helfen.

Also worum geht's? Es gut um ein sehr wichtiges Beweisverfahren in der Mathematik: vollständige Induktion. Wer hätte das gedacht.;) Die Fragen was, wie und  warum sollen jetzt geklärt werden. Grundlage für vollständige Induktion ist die Definition der natürlichen Zahlen, also von dem angeordneten Körper . Vollständige Induktion soll ja gerade zeigen, dass eine Aussage für alle natürlichen Zahlen gilt.

Was sind natürliche Zahlen, wo kommen die her?

Jeder weiß aus der Schule, die Zahlen 1, 2, 3, 4, ... sind natürliche Zahlen also . Manche nehmen die 0 auch noch mit, aber das ist eigentlich total egal. Jetzt wäre es natürlich ein wenig besser, diese Zahlen formaler zu charakterisieren.

Daher mal eine Definition:

Sei K eine Menge und das Mengensystem aller induktiven Teilmengen von K, dann ist die Menge aller natürlichen Zahlen.

Was, wie, wo? Erklärung der einzelnen Worte:

Mengensystem: Ein Mengensystem einer Menge K ist eine Teilmenge der Potenzmenge von K. D.h. diese Menge besteht wiederum aus Mengen. In diesem Fall besteht aus gewissen Teilmengen von K, nämlich aus den induktiven Teilmengen von K.
Nun, und was ist eine induktive Menge? Ganz einfach. Eine induktive Teilmenge von K ist eine Menge, die die 1 enthält und es zu jedem Element der Menge einen "Nachfolger" gibt:

heißt induktiv, wenn

(i)

(ii) und wenn , dann

Das erinnert doch an was! Genau! Da ist wieder die 1 und das "wenn n, dann n+1". Und das genau ist es auch, worauf es hinaus läuft. Denn kommen wir wieder zurück zur Definition der natürlichen Zahlen. Was ist ? Das große 1. Symbol zeigt, dass es etwas mit dem Durchschnitt zu tun hat. Allerdings geht es nicht um den Durchschnit von Mengen. besteht ja aus Mengen. Der Durchschnitt über dieses Mengensystem wird nun so definiert, dass er alle Elemente enthält, die auch in jeder Menge des Mengensystems enthalten sind.

Beispiel:

Sei , dann .

So, und nun können wir auch verstehen, warum ist. besteht ja aus Mengen, die alle induktiv sind. Damit müssen ale Mengen des Systems die 1 und die 2:=1+1 und 3:=1+1+1, etc. enthalten. Das macht ja gerade induktive Mengen aus. Damit haben auch alle Mengen diese Zahlen gemeinsam und daraus folgt: . Das sind gerade die natürlichen Zahlen, also .

Damit können wir nun das Prinzip der vollständigen Induktion formulieren:

Sei eine Teilmenge von mit den Eigenschaften, dass die 1 in liegt und dass für jedes auch sein Nachfolger in liegt, dann ist . ist damit insbesondere induktiv!

Der Beweis ist ganz einfach. Man schaue sich noch mal die Definition der natürlichen Zahlen an. Jedes gehört doch zu jeder induktiven Teilmenge, also auch zu . Das zeigt . Zudem wurde gefordert, also ist .

Jetzt kommt's!

Jetzt haben wir schon unser Beweisverfahren gefunden! Ab hier tut sich manch einer aber schwer, um das Induktionsprinzip mit einer zu beweisenden Formel in Verbindung zu bringen. Man geht daher so vor. Es soll ja gezeigt werden, dass irgendeine Formel oder Aussageform A(n) für alle natürlichen Zahlen gilt. Daher definiert man sich eine Menge und sagt, in diese Menge kommen nur die natürliche Zahlen, für die die Aussageform gilt. D.h. wir haben eine Menge, die über eine Eigenschaft definiert wird:

Wenn wir nun zeigen, dass A(1) eine wahre Aussage ist, kommt die 1 mit in die Menge. Nehmen wir nun ein beliebiges n in die Menge, d.h. wir tun so, als ob A(n) für dieses n gelte. Können wir nun zeigen, dass A(n+1) wahr ist unter eventueller Ausnutzung, dass n wahr ist, dann wäre auch n+1 in unserer Menge. Wir haben als nun eine Menge, die die 1 enthält und mit jedem n auch n+1 enthält, womit das Induktionsprinzip erfüllt ist und damit . Die Aussage A(n) gilt also für alle natürlichen Zahlen!

Ich hoffe, das war einigermaßen verständlich.