Beweis |2^M|=2^|M|, wenn M eine endliche nicht leere Menge ist.

Question

Aufgabe:

Beweis : Wenn M eine endliche nichtleere Menge ist, dann hat M genau 2^|M| verschiedene Teilmengen, dass heißt, |2^M|= 2^|M| .

Problem/Ansatz:

Ich hab keine Idee, was diese Frage meint. Hat das etwas mit Potenzmenge zu tun ?

Danke für eure Unterstützung!

Answer 1

Aloha :)

Es gibt genau \(\binom{n}{k}\) Möglichkeiten, aus einer n-elementigen Menge k Elemente auszuwählen. Damit hast du die Größen der 0-elementigen, 1-elementigen, 2-elementigen, ..., n-elementigen Teilmengen. Alle diese Teilmengen bilden in ihrer Gesamtheit die Potenzmenge. Addition der Größen liefert:$$\sum\limits_{k=0}^n\binom{n}{k}=\sum\limits_{k=0}^n\binom{n}{k}\cdot1^{n-k}\cdot1^k=(1+1)^n=2^n$$Bei der Summation wurde der binomische Lehrsatz verwendet.

Answer 2

ist das etwas mit Potenzmenge zu tun ?

Ja, 2^M ist die Potenzmenge von M.

Der Beweis ist per vollständiger Induktion über |M| möglich, oder indem du zählst wieviele Abbildungen von M nach {0,1} es gibt.