lambdas Kosmos

Vollständige Induktion klar gemacht - für Anfänger

Juni 28th, 2010

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 $\mathbb N$ . 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 $\mathbb N= \{1, 2, 3, ...\}$ . 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 $\mathcal M$ das Mengensystem aller induktiven Teilmengen von K, dann ist $\mathbb N:= \bigcap \mathcal M$ 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 $\mathcal M$ 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:

$M\subset K$ heißt induktiv, wenn

(i) $1\in M$

(ii) und wenn $n\in M$ , dann $n+1\in M$

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 $\bigcap \mathcal M$ ? Das große 1. Symbol zeigt, dass es etwas mit dem Durchschnitt zu tun hat. Allerdings geht es nicht um den Durchschnit von Mengen. $\mathcal M$ besteht ja aus Mengen. Der Durchschnitt über dieses Mengensystem $\bigcap \mathcal M$ wird nun so definiert, dass er alle Elemente enthält, die auch in jeder Menge des Mengensystems enthalten sind.

Beispiel:

Sei $\mathcal M=\{\{1,2\},\{1,3\},\{1,4\},\{1,5\}\}$ , dann $\bigcap\mathcal M=\{1\}$ .

So, und nun können wir auch verstehen, warum $\mathbb N=\bigcap \mathcal M$ ist. $\mathcal M$ 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: $\bigcap \mathcal M=\{1, 1+1, 1+1+1, 1+1+1+1,\dots \}=\{1,2,3,4,\dots\}$ . Das sind gerade die natürlichen Zahlen, also $\mathbb N=\bigcap \mathcal M$ .

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

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

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

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:

$N=\{n\in \mathbb N \;|\; \text{A(n) gilt fuer n}\}$

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 $N=\mathbb N$ . Die Aussage A(n) gilt also für alle natürlichen Zahlen!

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

Schlagworte: induktionsprinzip, induktive teilmenge, natürliche zahlen, prinzip der vollständigen induktion, vollständige induktion

Veröffentlicht in Mathematik | Sende Feedback »

Linksammlung

Mai 21st, 2010

Physik

Astronomie/Lexika/FAQs

Astrophysik/Kosmologie

video lectures

Was man wissen sollte

HOW to BECOME a GOOD THEORETICAL PHYSICIST

Veröffentlicht in Links | Sende Feedback »

Elementarfragen

Mai 15th, 2010

Ich habe eben in einem anderen Blog gesehen, dass es eine neue Plattform für Podcasts über die "elementarsten Fragen" gibt. Es nennt sich Elementarfragen. Scheint ganz interesasant zu sein. Habe mir (bzw. schaue noch) eben das erste Podcast angesehen. Dort wird Florian Freistetter, welcher auch der Blogger des genannen Blogs ist, über Astronomie und Physik befragt. Das ganze geht knapp 2 Stunden.

EF01 (Astronomie I)

Veröffentlicht in Astronomie | Sende Feedback »

Feynman hat Geburtstag

Mai 13th, 2010

Eigentlich hatte er schon am 11. Mai Geburtstag. Er ist einer der sympathischsten Physiker, der einen auf hohem Niveau unterhalten kann.

Alles Gute zum 92. Mr. Feynman!

Sehr zum Empfehlen sind auch seine Bücher.

Veröffentlicht in Interessantes | Sende Feedback »

Wahrhaft schöner Anblick :)

Mai 8th, 2010

Zu sehen ist hier ein vollmondgroßer Himmelsausschnitt, der lange belichtet wurde und so Licht einfangen konnte, welches über 8 Milliarden Jahre auf dem Weg war. Etwa in der Mitte sind viele hundert gelbliche Galaxien zu sehen, welche den Galaxienhaufen Abell 315 bilden. Alle hellen Punkte auf dem Bild sind Galaxien bis auf einzelne Vordergrundsterne (kreuzförmige Strahlen) und rote, grüne, blaue Striche (das waren vorüberziehende Asteroiden).
Es sind sogar auch Spiralgalaxien zu sehen und sich verschlingende Galaxien sog. Merger-Galxien. Das ist doch schön. *hüpf*

wysiwyg image
Bild: ESO/J. Dietrich

Wer will kann sich auch hier eine "kleine" 100 MB Datei des Bildes runterladen, um schön reinzoomen zu können.