Aufgabe 22

Sei X eine n-elementige Menge.

(a) Geben Sie eine bijektive Abbildung der Menge aller binären Folgen der Länge n auf die Menge aller Teilmengen von X an.

(b) Geben Sie damit einen neuen Beweis für die Tatsache |P(X)|=2^n an.

Hinterlasse einen Kommentar

2 Kommentare auf "Aufgabe 22"

Benachrichtige mich zu:
Iris
Mitglied
Iris

(a) Die Elemente von X werden bezeichnet mit x_1, x_2, x_3, \dots x_n. Jeder binären Folge wird die Teilmenge von X zugeordnet, die genau die Elemente enthält, für die das entsprechende Glied der Folge 1 ist. Beispielsweise ist x_1 in den Bildern von genau den Folgen enthalten, deren erstes Element eine 1 ist. So kann jeder Folge eine Teilmenge von X zugeordnet werden und es wird auch jeder Folge eine andere Menge zugeordnet, denn wenn sich zwei Folgen in einem Glied unterscheiden, dann ist das entsprechende Element aus X im Bild einer dieser Folgen enthalten, in dem der anderen jedoch nicht.

(b) Wie in Aufgabenteil (a) gezeigt, gibt es eine Bijektion zwischen der Menge aller binären Folgen der Länge n und der Potenzmenge P(X) einer n-elementigen Menge X, also müssen diese Mengen gleichmächtig sein. Die Menge der binären Folgen hat die Mächtigkeit 2^n (das war in Aufgabe 21 gefragt). Da die Potenzmenge von X die gleiche Mächtigkeit hat, muss |P(X)| = 2^n gelten.