Mächtigkeit der Potenzmenge: #P(M) = 2^n

Question

Hallo ,

Es sei n∈ ℕ und M eine Menge mit n Elementen. Zeigen Sie mit Hilfe vollständigerInduktion
                              #P(M) = 2^n
dass also die Potenzmenge von M die Mächtigkeit 2^n hat.

Also ich habe mit Induktionsanker angefangen:

IA: n= 0

dann aber sieht man das 2^0 =1 ist und kann ich das nicht beweisen.
mit Induktionsschritt geht auch nicht .
Kann mir jemand helfen ? Danke

Grüße MEL

Answer 1

Hi MEL,

 

ℕ ist doch meines Wissens 1, 2, 3, ...

ℕ₀ = 0, 1, 2, 3, ...

Probier deshalb mal die Verankerung mit n = 1

 

Besten Gruß

Comments

Auch mit n = 0 ist 2^0 = 1 richtig. Denn die Potenzmenge einer Menge M ist die Menge aller Teilmengen von M. Und die leere Menge ist auch eine Teilmenge von M. Also enthält die Potenzmenge auch die Menge mit der leeren Menge.

---

Hi,

also bedeutet das man frei entscheiden kann ob man 0,1,2,3 ... benutzen kann.
dann passt ja also aber wie kann ich das beim schritt machen. WIr müssen beim induktionsschritt zeigen dass n->n+1 gilt.
#P(M) =2ⁿ
2ⁿ⁺¹ und dann ?

Grüße MEL

---

Folgender "Beweis" ist wahrscheinlich nicht formal korrekt:

 

Verankerung n = 1

P(M) = 2¹ = 2

{}, {1}

 

Annahme: Es gelte P(M) = 2ⁿ

 

Schluss: Dann gilt auch für n+1: P(M) = 2ⁿ⁺¹

Es gilt laut Annahme P(M) = 2ⁿ, es gibt also 2ⁿ verschiedene Teilmengen aus n Elementen.

Nun kommt ein weiteres Element hinzu. Dieses kann zu jeder Teilmenge aus n Elementen hinzugefügt werden - oder auch nicht. Deshalb verdoppelt sich die Anzahl der Teilmengen von 

2ⁿ auf 2 * 2ⁿ = 2ⁿ⁺¹