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