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.

2

Hinterlasse einen Kommentar

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.

Autor

Stefan Hartmann

Richtig. Die Abbildung sollte man vielleicht noch formal angeben mit $f(x_1,\ldots, x_n)=\{x \in X: x(i)=1\}$ , wenn man die Elemente aus $X$ mit $x(i)$ für $i=1,\ldots, n$ bezeichnet.

2 Hinterlasse einen Kommentar

2

Hinterlasse einen Kommentar