Teilmengen und Mächtigkeit

Question

Sei M eine nichtleere endliche Menge. Zeigen Sie, dass M genauso viele
Teilmengen mit gerader wie mit ungerader Mächtigkeit besitzt. Bestimmen Sie die Anzahl dieser Teilmengen.

Answer 1

Hallo,

wie wäre es mit einem einfachen Induktionsbeweis: Für natürliche Zahlen n (größer gleich 1):

$(A_n)$: Die Anzahl der Teilmengen von $M(n):=\{1, \ldots,n\}$ mit gerader Mächtigkeit ist $2^{n-1}$.

Wenn für eine natürliche Zahl n die Aussage $A_n)$ gilt, dann zählen wir die Teilmengen X von $M(n+1)$ mit gerader Mächtigkeit. Es ist

ENTWEDER: $X \sube M(n)$ mit $|X|$ gerade. Das sind $2^{n-1}$

ODER $X \cup \{n+1\}$ mit $X \sube M(n)$ und $|X|$ ungerade. Das sind $2^{n-1}$.

Zusammen also $2^n$ Teilmengen.

Gruß Mathhilf