Lösung für Aufgabe 4.4.5
Beweisen Sie, dass $|\P M|=2^{|M|}$ gilt.Hinweis: Konstruieren Sie eine Bijektion von $\P 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.