bijektive Abbildung von P({1, 2, . . . , n}) nach {0, 1}^n

Question

Aufgabe:

Sei n ∈ N. Die Potenzmenge P({1, 2, . . . , n}) und das n-fache kartesische Produkt von
{0, 1} sind gleichmächtige Mengen.

Finden Sie eine bijektive Abbildung von P({1, 2, . . . , n}) nach {0, 1}ⁿ

Meine Idee wäre dies:

1 |-> (0,0)
2 |-> (0,1)
3 |-> (1,0)
4 |-> (1,1)
5 |-> (0, (0,0)
6 |-> (0, (0,1))
7 |-> (0, (1,0))
8 |-> (0, (1,1))
9 |-> (1, (0,0))
...

Weiss aber nicht wie man da eine Abbildungsvorschrift formalisieren soll..

Comments

Du hast den Zahlen 1,...,n versucht Elemente des kartesischen

Produktes zuzuordnen. Es ging aber darum den \(2^n\) verschiedenen

Teilmengen von 1,...,n ein n-Tupel aus 0 und 1 umkehrbar eindeutig

zuzuordnen.

Answer 1

Sei \(M \in P(\{1,...,n\})\). Dann definiere \((f(M)_i)_{i=1,\cdots,n}\) durch

\(f(M)_i=1\text{, falls } i\in M, =0 \text{, falls } i \notin M\).

Comments

Könnte ich das ganze so schreiben?
A ∈ P({1, 2, . . . , n})
A |-> {(a₁ , a_i , ... , a_n) | a_i = 1 wenn i ∈ A, a_i = 0 wenn i ∉ A für i = 0, ... , n}

---

Ja. Fast so kannst du es schreiben. Aber die Mengenklammer gibt keinen Sinn, lieber so:

\(A\mapsto (a_1,\cdots,a_n)\), wobei \(a_i=1\), wenn \(i \in A\)
und \(a_i=0\), wenn \(i\notin A\).

Answer 2

Es geht ja um die Potenzmenge von {1, 2, . . . , n}, also um alle

möglichen Teilmengen. Du kannst dann ja die Abbildung so gestalten,

dass du zu jeder Teilmenge M von {1, 2, . . . , n} ein n-tupel

konstruierst, das an der i-ten Stelle eine 1 hat, wenn i∈M

und sonst eine 0.

Comments

Könnte ich das ganze so schreiben?

A ∈ P({1, 2, . . . , n})

A |-> {(a₁ , a_i , ... , a_n) | a_i = 1 wenn i ∈ A, ai = 0 wenn i ∉ A für i = 0, ... , n}

---

Na das sieht doch gut aus .