Zeige: |Ρ(M)| = 2^|M|

Question

Aufgabe:

Sei M eine endliche Menge und P die Potenzmenge. Zeige: |Ρ(M)| = 2^{|M|}

Problem/Ansatz:

Kann mir jemand sagen wie ich das ganze Beweisen soll, bzw. was der Gedanke hierbei ist

Answer 1

Aloha :)

Es sei \(n\coloneqq|M|\) die Anzahl der Elemente in der Menge \(M\). Die Potenzmenge \(P(M)\) enthält alle möglichen Teilmengen der Menge \(M\). Wir haben \(\binom{n}{k}\) Möglichkeiten, aus den \(n\) Elementen genau \(k\) auszuwählen. Das heißt, es gibt genau \(\binom{n}{k}\) \(k\)-elementige Teilmengen. Die Anzahl an Teilmengen insgesamt ist daher die Summe

$$|P(M)|=\sum\limits_{k=0}^n\binom{n}{k}=\sum\limits_{k=0}^n\binom{n}{k}\cdot1^{n-k}\cdot1^k\stackrel*=(1+1)^n=2^n\quad\checkmark$$

Bei dem Umformungsschritt mit dem Sternchen über dem Gleichheitszeichen haben wir den binomischen Lehrsatz verwendet.

Comments

ahhhh danke :-)