TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 105

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.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

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