TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 101

Sei $\mathbb{M}$ eine nichtleere endliche Menge. Zeigen Sie, dass $\mathbb{M}$ gleich viele Teilmengen mit gerader Elementanzahl wie solche mit ungerader Elementanzahl besitzt, indem Sie ein Verfahren angeben, das aus den Teilmengen der einen Art umkehrbar eindeutig die der anderen Art erzeugt.

Lösung gibts im Informatik Forum SS07!

Nur ohne Angabe des Links nicht auffindbar!

Lösungsvorschlag von M4rS

Die Lösungen im Informatik-forum schaun ja auf den ersten Blick relativ kompliziert aus, und nachdem im Buch das nächste Bsp (88) mehr od weniger "einfach" bewiesen ist, würde ichs mal so versuchen

Jede Menge hat $2^{n}$ Elemente. Wir können uns eine Teilmenge als Kombination von Binärzahlen ${0,1}$ vorstellen.

Z. B. $\mathbb{M}={1,2,3}$

Teilmengen sind $1;2;1,2;2,3;1,2,3$ Die Anzahl können wir immer mit $2^{01}*2^{01}*2^{01}$ darstellen, je nachdem, ob wir das Element in die Teilmenge aufnehmen. Da man bei jedem Element auf diese Weise wählen kann ob man es in die Gruppe aufnimmt od nicht haben wir mMn bewiesen das es gleich viele gerade wie ungerade Teilmengen gibt und auch ein Verfahren gezeigt, mit dem man umkehrbar eindeutig Teilmengen erzeugen kann.

Lösungsvorschlag von Ryus

Kurz gefasst: Man wählt irgendein Element x aus der Menge aus und wendet folgende Funktion auf die Teilmenge an:

$f(A) = A \Delta x$

Wobei $\Delta$ die symmetrische Differenz bezeichnet. Ist $x \in (A \Delta x)$, wird es der Teilmenge A hinzugefügt. Ist hingegen $x \notin (A \Delta x)$, wird es aus A entfernt. So kann man von jeder ungeraden Menge auf eine gerade schließen und umgekehrt. Somit ist eine Bijektion gefunden und gezeigt, dass die Anzahl an ungeraden Mengen gleich der Anzahl an geraden Mengen ist.

--Ryus (Diskussion) 19:52, 25. Mär. 2015 (CET)

Passende Threads

• f.thread:3063
• f.thread:26196
• f.thread:30159