n-elementige Menge {1,…,n}

Question

Aufgabe:

Zeigen Sie mittels Angabe einer Bijektion, dass die Menge aller Teilmengen einer n -elementigen Menge und die Menge aller 0,1 -Folgen der Liange n die gleiche Kardinalität besitzen. Tipp: Betrachten Sie als n-elementige Menge {1,…,n}

Comments

Was sind \(1\)-Folgen?

---

0,1 - Folgen sind vermutlich Folgen die nur 0 und 1 annehmen. Anders formuliert: eine 0,1-Folge der Länge n ist eine Abbildung

{1,...,n} → {0,1}

Answer 1

Die betrachtete n-elementige Menge sei  M = {a₁ , a₂ , a₃ , ..... a_n} . Dabei wird natürlich vorausgesetzt, dass alle diese n Elemente paarweise verschieden sein sollen, also a_i ≠ a_j  falls i ≠ j .

Eine beliebige Teilmenge T von M kann eindeutig charakterisiert werden, indem man die Menge  I_T aller Indices jener Elemente  angibt, welche zu T gehören. Weiter kann man jeder solchen Indexmenge eine n-stellige binäre Zahlenfolge f  zuordnen durch die einfache Festlegung  f(i) = 1 falls  i ∈ I_T  und  f(i) = 0  falls  i ∉ I_T .

Zeige nun allenfalls noch etwas ausführlicher, dass diese Zuordnung von Binärfolgen zu den Teilmengen eine bijektive Zuordnung ist, also dass verschiedene Teilmengen zu verschiedenen Binärfolgen führen und dass zu zwei unterschiedlichen Binärfolgen auch zwei unterschiedliche Teilmengen gehören.

Answer 2

Mit dem Tipp ist es vielleicht so:

Es sei M =  {1,…,n} die n-elementige Menge.

Und T eine Teilmenge von M. Dann ist für jedes Element  1,…,n

eindeutig festgelegt, ob es zur Teilmenge gehört oder nicht.

Also gibt es für jede Teilmenge T die Funktion

f_T : T → {0,1}  mit f(x) = 1 für x ∈ T und f(x) = 0 sonst.

Diese Funktion ist also eine   0,1 -Folgen der Länge n

oder auch ein n-Tupel, das nur 0en und 1en enthält,

also ein Elemente aus {0,1}^n .

Damit ist die gesuchte Bijektion

b : P(M) → {0,1}^n 
       T →   f_T .

Die ist Injektiv, denn wenn für zwei Teilmengen S und T von M

gilt  f_T = f_S , dann gilt für jedes Element von x∈M

x∈T <=>  x∈S  also    T=S.

Und surjektiv, denn wenn (x₁,...,x_n) ∈  {0,1}^n

Dann hat ja jedes x_i den Wert 0 oder 1 und damit gibt es

eine Teilmenge T von M mit f_T= (x1,...,xn) , in T sind nämlich genau

die i  ∈ {1,…,n} für die  x_i = 1 ist.