Der Fall das \( M \) endlich ist offensichtlich. Sei also \( M \) abzählbar unendlich. Es gibt also eine Injektion \( f \) von \( M \) nach \( \mathbb{N} \) und somit können wir eine totale Ordnung auf \( M \) wie folgt definieren
\( x<_{M} y \Longleftrightarrow f(x)<f(y), \quad x, y \in M \)
Wir können nun einfach eine Injektion von \( \{0,1\}^{\infty} \) (semi-unendlichen Binärsequenzen, also nach rechts unbeschränkt) in die Potenzmenge von \( M \) geben, mit
\( \varphi:\{0,1\}^{\infty} \rightarrow \mathcal{P}(M), \quad \varphi(w)=\left\{x \mid x=m_{i} \wedge w_{i}=1\right\} \)
wobei \( m_{i} \) das \( i \) te Wort in der totalen Ordnung \( \leq_{M} \) und \( w_{i} \) das \( i \) te Bit des Binärstrings \( w \) ist. Nun ist \( \{0,1\}^{\infty} \) jedoch überabzählbar (Cantor Diagonalisierung) und somit auch \( \mathcal{P}(M) \)
