Bijektive Abbildung: Menge aller binären Folgen (Länge n)? P(X) (|X| = n)

14.03.2013, 19:25	Luke94	Auf diesen Beitrag antworten »
Bijektive Abbildung: Menge aller binären Folgen (Länge n)? P(X) (\|X\| = n) Meine Frage: Sei $\begin{eqnarray} \textbf{X} \end{eqnarray}$ eine n-elementige Menge. Geben Sie eine bijektive Abbildung der Menge aller binären Folgen der Länge n auf die Menge aller Teilmengen von $\begin{eqnarray} \textbf{X} \end{eqnarray}$ an. Meine Frage bezieht sich nun darauf, wie man die Abbildung mathematisch darstellt. Meine Ideen: Ich habe die binäre Folge als n-Tupel aufgefasst und diese folgender Weise den jeweiligen Teilmengen der Potenzmenge von $\begin{eqnarray} \textbf{X} \end{eqnarray}$ zugeordnet: $\begin{eqnarray} \left(0, 0, 0, 0, ...\right) \longmapsto \left\{\ \right\} \end{eqnarray}$ $\begin{eqnarray} \left(1, 0, 0, 0, ...\right) \longmapsto \left\{1 \right\} \end{eqnarray}$ $\begin{eqnarray} \left(0, 1, 0, 0, ...\right) \longmapsto \left\{2 \right\} \end{eqnarray}$ $\begin{eqnarray} \left(0, 0, 1, 0, ...\right) \longmapsto \left\{3 \right\} \end{eqnarray}$ $\begin{eqnarray} \left(1, 1, 0, 0, ...\right) \longmapsto \left\{1, 2 \right\} \end{eqnarray}$ $\begin{eqnarray} \left(0, 1, 1, 0, ...\right) \longmapsto \left\{2, 3 \right\} \end{eqnarray}$ $\begin{eqnarray} \left(1, 1, 1, 0, ...\right) \longmapsto \left\{1, 2, 3 \right\} \end{eqnarray}$ usw. Ich denke das Prinzip dürfte klar sein. Mein Problem besteht nun darin die zugehörige Funktion zu definieren. Zunächst habe ich mir eine Menge $\begin{eqnarray} \mathcal{A} \end{eqnarray}$ für die binären Folgen definiert: $\begin{eqnarray} \mathcal{A}:= \left\{ (a_{i})_{i=1}^{n}: a_{i} \in \left\{0, 1\right\} \right\} \end{eqnarray}$ Dann ist die Abbildung $\begin{eqnarray} f \end{eqnarray}$ : $\begin{eqnarray} f:\mathcal{A}\rightarrow P(X), (a_{i})_{i=1}^{n} \longmapsto \left\{i, i, i, ...\right\} (a_{i}=0 \Rightarrow i \ nicht \ auffuehren) \end{eqnarray}$ Das soll heißen, man soll das jeweilige $\begin{eqnarray} i \end{eqnarray}$ des $\begin{eqnarray} a \end{eqnarray}$ immer nur dann aufführen, wenn $\begin{eqnarray} a_{i}=1 \end{eqnarray}$ gilt. Also ist z.B. $\begin{eqnarray} a_{1}=0, \ a_{2}=1, a_{3}=1 \end{eqnarray}$ und die restlichen $\begin{eqnarray} a_{i}=0 \end{eqnarray}$ , dann soll die entsprechende Teilmenge der Potenzmenge so aussehen: $\begin{eqnarray} \left\{2, 3\right\} \end{eqnarray}$ Da für das zweite und dritte $\begin{eqnarray} i \end{eqnarray}$ die Bedingung $\begin{eqnarray} a_{i}=1 \end{eqnarray}$ erfüllt ist. Kann man das nun so aufschreiben oder ist das so falsch? Danke für eure Hilfe schonmal im Voraus!
14.03.2013, 23:42	RavenOnJ	Auf diesen Beitrag antworten »
Du identifizierst die n-elementige Menge mit der Zahlenmenge von 1 bis n. Das ist ok, da es eine eineindeutige Abbildung zwischen den beiden Mengen gibt. Deine Abbildungsvorschrift zwischen der n-elementigen Menge und den binären n-Tupeln ist auch ok. Du müsstest jetzt nur noch Injektivität und Surjektivität zeigen.
12.04.2013, 09:06	Luke94	Auf diesen Beitrag antworten »
Okay, vielen Dank!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »