Potenzmenge

Neue Frage »

Constanze Auf diesen Beitrag antworten »
Potenzmenge
Hallo zusammmen,

ich bin total verzweifelt und sitze schon seit Stunden an dieser Aufgaben. Ich hoffe ihr könnt mit schnell helfen, die Aufgabe muss nämlich bis morgen fertig sein...
Nun die Aufgabe:

Man begründe:
Jede Menge M mit n Elementen besitzt genauso viele Teilmengen mit gerader Elementeanzahl wie Teilmengen mit ungerader Elementeanzahl.

Danke schonmal im voraus!!!
irre.flexiv Auf diesen Beitrag antworten »

Nimm dir ein beliebiges aber festes .

Jetzt packst du alle Teilmengen von M in denen x enthalten ist ein eine Menge A (Das ist dann eine Teilmenge der Potenzmenge von M).

Dann ist P(M)/A die Menge aller Teilmengen in denen x nicht enthalten ist.

Jetzt musst du nur noch eine bijektive Abbildung zwischen den beiden angeben die dir das gewünschte Ergebnis liefert.
Constanze Auf diesen Beitrag antworten »

Danke,

aber ich habe gerade erfahren, dass der Mathe dozent wohl gemeint hat, dass man diese Aufgabe mit Hilfe von Binomialkoeffizienten lösen soll. Aber ich weiß echt nicht wie. Jetzt stehe ich wieder genauso da wie vorher...
Leopold Auf diesen Beitrag antworten »

@ irre.flexiv

Vielleicht stehe ich ja auf dem Schlauch. Aber wie folgt aus der Tatsache, daß es genau so viele Teilmengen gibt, die enthalten, wie solche, die nicht enthalten, die Behauptung?


@ Constanze

ist ja die Anzahl der -elementigen Teilmengen. Bekanntlich ist (Beweis z.B. über Anwendung des binomischen Lehrsatzes auf ).

Somit ist nur zu zeigen:



Und das geht z.B., indem man



auf zwei Arten berechnet: erstens direkt, zweitens über Anwendung des binomischen Lehrsatzes.
IchDerRobot Auf diesen Beitrag antworten »

Hallo Leopold,

die "richtige" Bijektion ordnet der Menge m in A die Menge m \ {x} zu und stellt so eine Bijektion zwischen den Mengen gerade und ungerade Mächtigkeit her.

Robot
Leopold Auf diesen Beitrag antworten »

Es wird wohl eher so gehen: Wenn ein ausgezeichnetes Element und die Menge der Teilmengen mit geradzahliger bzw. ungeradzahliger Elementezahl ist, so definiert



eine Bijektion zwischen und .
 
 
IchDerRobot Auf diesen Beitrag antworten »

Hallo Leopold,

ja, das ist das Endergebnis meiner Überlegung.

Sei x in M fest.
Seien A und B die Mengen aller Teilmengen von M mit gerade bzw. ungerade Elementzahl, und seien A' und B' die Mengen aller Teilmengen von M, die x enthalten bzw. nicht enthalten.

f: A' -> B', f(m) = m \ {x} ist die von mir genannte Bijektion.

Ist , so ist .
Ist , so ist .

Die von dir genannte Bijektion phi: A -> B wird also gerade von f vermittelt:
, falls ,
, falls .

Wie gesagt, mein f stellt die gewünschte Bijektion her, f ist nicht die gewünschte Bijektion: Je nachdem, ob m in A' oder in B' liegt, muss man f oder f^{-1} anwenden - die "Paarung" selbst ist aber schon in f gegeben.

Robot
irre.flexiv Auf diesen Beitrag antworten »

@ Leopold

Ich wollte auf folgendes hinaus:

fix

ist die Menge aller Teilmengen von M in denen das m enthalten ist.

Sei mit

Es ist klar das eine Funktion von A in P(M)\A ist.



Sei dann ist

ist also injektiv und surjektiv.

Die Elemente von sind jetzt in jedem Fall Paare aus einer Menge mit gerader Elementanzahl und einer Menge mit ungerader Anzahl.
IchDerRobot Auf diesen Beitrag antworten »

Hallo irre.flexiv,

ich hoffe, genau diese Idee mit meinem vorherigen Beitrag beschrieben zu haben. Wink

Robot
irre.flexiv Auf diesen Beitrag antworten »

Ah, manchmal lohnt es sich doch alle Posts zu lesen. Big Laugh
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »