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 Teilmenge

    dann 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.


Log in to reply