Zeigen Sie, dass |2M | = 2|M|

Question

Aufgabe:

Sei M eine endliche Menge, 2^M die Potenzmenge von M

(a) Zeigen Sie, dass |2^M | = 2^|M|   

(b) Zeigen Sie, dass keine surjektive Abbildung M → 2^M existiert.

Keine Ahnung wie man das Lösen könnte. Gerne auch mit Rechenweg. Danke

Comments

a) geht doch mit vollst. Induktion über |M|.

Answer 1

a) Vollständige Induktion über \(n \coloneqq |M|\). Jede Teilmenge von \(\{1, 2, \dots, n\}\) ist entweder

• eine Teilmenge von \(\{1, 2, \dots, n-1\}\) oder
  
• eine Menge der Form \(T \cup \{n\}\) wobei \(T\) eine Teilmenge von \(\{1, 2, \dots, n-1\}\) ist.

b) Sei \(f:\,M\to 2^M\). Zeige dass \(\{m\in M| m\notin f(M)\}\) nicht im Bild von \(f\) ist.