Zeigen mit vollständiger Induktion

prozeus

Hallo,

folgende Aufgabe weiß ich leider nicht wie ich sie lösen kann:
Genau gesagt, ich habe keinen Plan.

Zeigen Sie mit Hilfe von vollständiger Induktion: Die Potenzmenge P(M)
einer Menge M mit n Elementen hat 2ⁿ Elemente.

Ich wäre sehr dankbar über eure Hilfe.

mfg
prozeus

Taurin

Hast du denn schon irgendwas? Den Indunktionsanfang? Was ist die Mächtigkeit der Potenzmenge der leeren Menge?

Für den Induktionsschritt hätte ich spontan folgenen Ansatz:

Sei $M_n$ eine Menge mit n Elementen.
$|P(M_{n+1})| = |P(M\_n) \cup (P(M\_{n+1}) - P(M_n))|$
$= |P(M\_n)| + |P(M\_{n+1}) - P(M_n)| = ...$

Hmm, interessanterweise war diese Aufgabe auf unserem letzten "Ubungszettel.

Ich will dir mal einen kleinen Hinweis geben.
F"ur den Induktionsanfang w"urde ich die M"achtigkeit der Potenzmenge von $M_0$ zeigen:

$|P(M_0)| = |P(\emptyset)| = 1 = 2^0$

Fuer den Induktionsschritt kannst du dir folgendes "uberlegen: Die Menge $M_n$ unterscheidet sich von der Menge $M_{n+1}$ nur in einem Element:
$M_{n+1} = M_n \cup \{q\}$

Jetzt "uberlege mal, wie viele Teilmengen (alle *ohne* q) es von $M_n$ gibt. Nun "uberlege, wie viele weitere Teilmengen es von $M_{n+1}$ mit $q$ gibt?
Wenn du auf diese beiden Zahlen zusammenaddierst (alle Teilmengen von $M_n$ sind ja auch Teilmengen von $M_n+1$ , bekommst du die Anzahl aller Teilmengen (M"achtigkeit der Potenzmenge) von $M_{n+1}$ .