Beweisen mittels Vollständiger Induktion

Question

Aufgabe:

Für eine Menge A ist die Potenzmenge P(A) von A die Menge aller Teilmengen von A.

Für A={a,b} gilt beispielsweise P(A)={∅,{a},{b},{a,b}}.

Beweis mittels vollständiger Induktion (Induktionsanfang, Induktionhypothese, Induktionsschritt), dass für alle n ∈ ℕ gilt : Wenn S eine endliche Menge mit Kardinalität n ist, dann hat die Potenzmenge P(S) Kardinalität 2ⁿ .

Problem/Ansatz:

Habe ziemliche Schwierigkeiten mit der Aufgabe. Die Rechenwege mit Erklärung wäre sehr hilfreich.

Answer 1

Wenn dir eine gegebene Menge A (mit n Elementen) und ihre vollständige Potenzmenge P(A) (mit einer gewissen Anzahl m von Elementen) vorliegen, kannst du dir überlegen, wie viele Elemente die Menge A'  sowie die zugehörige Potenzmenge P(A') haben müssten - für den Fall, dass A' einfach ein Element mehr besitzt als die Menge A.

A' besitzt also  n+1  Elemente.

Die gesamte Potenzmenge P(A')  erhältst du, indem du von P(A)  ausgehst. Natürlich enthält P(A')  zunächst einmal alle Mengen, die schon zu P(A)  gehören. Alle weiteren Elemente der Menge P(A') entstehen, indem man zu einem beliebigen Element von P(A) noch das neue, zusätzliche Element e dazufügt. Insgesamt muss deshalb  P(A')  genau doppelt so viele Elemente wie P(A) besitzen, also 2m Elemente.

Hilft dies etwas weiter ?