Beweis der Mächtigkeit einer Potenzmenge
-
Hi!
Wie kann man beweisen, das die Mächtigkeit einer Potenzmenge 2n ist?
Ich habe mir etwas überlegt, kann man die Beweisführung so machen, guckst du hier:Es gibt eine Menge Mn mit den Elementen { E1, E2, ... En } und der Mächtigkeit n;
Die Potenzmenge von P(Mn), hat die Teilmengen { T1, T2, ... Tz }, die Mächtigkeit von P(Mn) ist somit z.Annahme: z = 2n.
Für eine Menge Mn+1 mit der Mächtigkeit n+1, muss nun gezeigt werden das gilt: |P(Mn+1)| = 2 n+1.
Füge der Menge Mn ein Element En+1 hinzu, es gibt nun eine Menge Mn+1 mit den Elementen { E1, E2, ... En, En+1 } und der Mächtigkeit n+1.
Die Menge aller Teilmengen von P(Mn+1) enthält alle Teilmengen von P(Mn) + ( En+1 U Ti ). Mit i = 1...z.
Wir erhalten |P(Mn+1)| = |P(Mn)| + |( En+1 U Ti )| = z + z = 2z.Nach obiger Annahme ist z = 2n, also ist |P(Mn+1)| = 2*2n = 2n+1.
qed.
-
Der Induktionsanfang fehlt.
-
Naja, Induktion hatte ich noch nicht. Das kommt bestimmt noch.
-
Dann ist der Beweis halt total käse.
-
Dann muss ich wohl noch üben :p , Induktion kommt in meinem Skript auch noch irgendwann dran, vielleicht klappt das ja dann richtig.
-
wieso nicht per Induktion ?
für die leere Mengen stimmt es: 2^0=1
Stimmt die Behauptung für n-elementige Mengen, dann nimmt man sich eine Menge M mit n+1 Elementen vor und greift sich ein Element x aus M heraus.
Jede Teilmenge M' von M enthält entweder x oder nicht.
Nach Induktionsannahme hat M 2^n Teilmengen, die x nicht enthalten.
Fügt man zu jeder dieser Teilmengen x hinzu, erhält man weitere 2^n Teilmengen, die x enthalten. Andere Teilmengen hat M nicht.Und 2^n + 2^n = 2^(n+1).
-
Dann hätte ich also bloß noch an einem Beispiel zeigen müssen, das z = 2n wahr ist, z.B. anhand einer Leeren Menge und dann wäre es mathematisch ok?
-
nicht irgendein beispiel, sondern fuer das kleinste n.
-
Ok, thx.
-
naja einleuchtender finde ich ja folgenden Beweis
man kodiere die Zugehörigkeit der Element in den Teilmengen
durch eine binärzahl der Länge n (anzahl der Elemente)
0 = Element ist nicht in Teilmenge
1 = Element ist in Teilmengedann gibt es genausoviele Teilmenge wie sich binär-Zahlen
codieren lassen = 2^n
-
und daß es 2^n Binärzahlen gibt, beweist du wieder mit einer Induktion. Ist doch gehupft wie gesprungen.