Mächtigkeit der Potenzmenge

Erklärung

Die Potenzmenge $\mathcal{P}(M)$ enthält alle Teilmengen von $M$, auch die leere Menge $\emptyset$ und $M$ selbst. Hat $M$ genau $n$ Elemente, so hat $\mathcal{P}(M)$ genau $2^n$ Elemente.

Begründung: Um eine Teilmenge festzulegen, entscheidet man für jedes der $n$ Elemente unabhängig, ob es dazugehört oder nicht. Das sind $2 \cdot 2 \cdot \ldots \cdot 2 = 2^n$ Möglichkeiten. Gleichwertig entspricht jede Teilmenge genau einem 0-1-Wort der Länge $n$.

Zählt man die Teilmengen nach ihrer Größe $k$, erhält man die Zeilensumme im Pascalschen Dreieck:

Für unendliche Mengen gilt der Satz von Cantor: Die Potenzmenge ist immer echt mächtiger als die Menge selbst. Deshalb schreibt man die Potenzmenge auch als $2^M$.

Beispiele

$M = \{a, b, c\}$ hat $2^3 = 8$ Teilmengen:

Nach Größe sortiert sind das $1 + 3 + 3 + 1 = 8$.

Eine Pizzeria bietet $10$ Beläge an. Jede Auswahl von Belägen, auch gar keiner, ergibt eine andere Pizza: $2^{10} = 1024$ Möglichkeiten.

Die Potenzmenge von $\mathcal{P}(\{1, 2\})$ hat $2^{2^2} = 16$ Elemente.

Typische Fehler

• Leere Menge oder $M$ selbst vergessen. Wer nur die echten, nichtleeren Teilmengen zählt, erhält $2^n - 2$, bei $\{a, b, c\}$ also $6$ statt $8$.
• $\mathcal{P}(\emptyset)$ für leer halten. Die leere Menge hat genau eine Teilmenge, sich selbst: $\mathcal{P}(\emptyset) = \{\emptyset\}$ mit $2^0 = 1$ Element.
• Elemente und Teilmengen verwechseln. $a \in M$, aber $\{a\} \in \mathcal{P}(M)$ und $\{a\} \subseteq M$.