Einführung in das mathematische Arbeiten

Lösung für Aufgabe 4.4.5

Beweisen Sie, dass

gilt.

Hinweis: Konstruieren Sie eine Bijektion von M auf die Menge aller Abbildungen M\to\{0,1\}. Finden Sie zu jeder Teilmenge von M eine passende Abbildung.

Sei A\subseteq M gegeben. Wir definieren die Abbildung f_A:M\to\{0,1\} durch

f_A(m) = \begin{cases}1 & m\in A\\0 & m\notin A.\end{cases}

Die Abbildung \phi:\P M\to \{0,1\}^{M} mit \phi:A\mapsto f_A ist eine Bijektion. Ihre Umkehrabbildung ist \phi^{-1}:\{0,1\}^{M}\to\P M mit \phi^{-1}:f\mapsto A_f\subseteq M, wobei

m\in A_f:\liff f(m)=1.

Ist nun eine andere Menge N gegeben mit |M|=|N|, dann sind \{0,1\}^N und \{0,1\}^M gleichmächtig. Es existiert dann nämlich eine Bijektion h:M\to N, und für jede Abbildung f:N\to\{0,1\} können wir die Abbildung h^*(f):=f\o h:M\to\{0,1\} definieren, und zu jeder Abbildung g:M\to\{0,1\} die Abbildung (h^*)^{-1}(g):=g\o h^{-1}:N\to\{0,1\}. Die Abbildung h^*:\{0,1\}^N\to\{0,1\}^M ist also eine Bijektion, was die Bezeichnung 2^{|M|} rechtfertigt und den Beweis beendet.