Angenommen man hat drei Zahlen (1,2,3) und man hat Ereignisse, die Anzahl der Teilmengen sieht dann wie folgt aus:
1. Leere Menge
2. 1 ; 2 ; 3;
3. 12; 23; 13;
und 4. 123
Das gibt insgesamt 8 Teilmengen (2 hoch 3)
Bei n Zahlen gilt 2 hoch n Teilmengen?
Wie kann man dies z.B durch vollständige Induktion (denk ich mir mal) beweisen?
Hi,
Angenommen man hat drei Zahlen (1,2,3) und man hat Ereignisse,
die Anzahl der Teilmengen sieht dann wie folgt aus:
[...]
Das gibt insgesamt 8 Teilmengen (2 hoch 3)
Bei n Zahlen gilt 2 hoch n Teilmengen?
Wie kann man dies z.B durch vollständige Induktion (denk ich
mir mal) beweisen?
- Beweis durch Ausprobieren bis n=1 (z.B.)
- Induktionsschritt n->n+1: "Zähle", wie viele Teilmengen zu den bestehenden dazu kommen - relativ zu diesen also.
- Forme die Summe (2^n + neue) so um, daß 2^(n+1) rauskommt.
Im Prinzip ganz einfach :-)
Cheatah
Vielen Dank für die Ausführung, Cheatah!
So weit komme ich im Grunde jedoch auch, aber bei der Aufstellung der vollständigen Induktion habe ich meine.. Probleme
Vielen Dank für die Ausführung, Cheatah!
So weit komme ich im Grunde jedoch auch, aber bei der
Aufstellung der vollständigen Induktion habe ich meine..
Probleme
Induktionsanfang:
m[0]= Menge, die aus null Elementen besteht (leere Menge)
M[0] = "Ereignisraum", der sich aus m[0] bilden lässt (Menge aller Teilmengen)
Die einzige Teilmenge der leeren Menge m[0] ist die leere Menge. Also besteht M[0] aus genau einem Element.
2 hoch 0 = 1
Das heisst, die Richtigkeit der Aussage
(*) "Die Menge M[n] besteht aus 2 hoch n Elementen" ist für n=0 richtig.
Induktionsvoraussetzungen:
Die Menge m[n] enthalte n Elemente.
Die Aussage (*) sei für n richtig, d.h. M[n] als die Menge aller Teilmengen von m[n] enthalte 2 hoch n Elemente.
Wir beweisen nun, dass die Aussage (*) dann auch für n+1 richtig ist:
Die Menge m[n+1] besteht aus den Elementen der Menge m[n] und einem weiteren Element [n+1].
Die Menge M[n+1] ist die Menge aller Teilmengen von m[n+1].
Sie enthält zunächst wieder alle Teilmengen von m[n], also die Menge M[n] (laut Induktionsvoraussetzung besteht diese aus 2 hoch n Elementen), und als weitere Elemente alle Paare, die aus jeweils einem Element von M[n] und dem neuen Element [n+1] gebildet werden können. Es sind dies aufgrund der Induktionsvoraussetzung abermals 2 hoch n solche Paare. Insgesamt enthält M[n+1] also 2 * (2 hoch n) = 2 hoch (n+1) Elemente. Das war es, was wir beweisen wollten. (q.e.d.)
Richtig so, im allgemeinen wird der "Ereignisraum" allerdings Potenzmenge genannt.
Zu beachten ist in diesem Zusammenhang, daß die Potenzmenge eine Menge ist, die selbst wiederum Mengen enthält, d.h.
P(leere Menge)={leere Menge} und nicht etwa die leere Menge selbst.
aber das nur am Rande