Induktion: Die Potenzmenge einer Menge mit n Elementen hat 2^n Elemente

Question

Kann mir jemand bei dieser Aufgabe helfen. Ich verstehe die Aussage nicht so ganz bzw. Weissagung nicht man wie beweist.

Beweisen sie mit vollständiger Induktion ( n ∈ ℕ, n>=1) gilt:

Die potenzmenge einer menge mit n elementen hat 2 ^n elemente.

Dankeschön

Answer 1

Hallo Samira,

du willst folgende Aussage A(n) beweisen:

Für alle n ∈ ℕ₀ gilt: Jede Menge mit n Elementen hat 2ⁿ Teilmengen.

Dazu musst du zeigen:

1) Induktionsbasis:  A(0) ist wahr

2) Induktionsschluss:  A(z) ⇒ A(z+1)

    [ Wenn A(z) für irgendein z ∈ ℕ₀  wahr ist, dann ist auch A(z+1) wahr ]

Nachweis:

1)

 A(0) ⇔ eine Teilmenge mit 0 Elementen hat 2⁰ = 1  Teilmengen

     Das ist wahr, weil die leere Menge nur sich selbst als Telimenge hat.

2) 

Sei  M₁ = { e₁ , e₂ ,  ..... , e_z , e_z+1 } eine Menge mit z+1 Elementen

Dann hat M₂ = { e₁ , e₂ ,  ..... , e_z }  nach Induktionsvoraussetzung A(z)   2^z  Teilmengen

Diese sind alle auch Teilmengen von M₁

Jede weitere Teilmengen von M₁ erhält man, wenn man eine der Teilmengen von M₂ um das Element e_z+1 erweitert.

Insgesamt hat M₁ also 2 · 2^z = 2^z+1 Teilmengen

A(z+1) ist also wahr.

------------

Oder kürzer:

 https://www.mathelounge.de/300587/wie-zeige-ich-das-die-potenzmenge-genau-2-n-elemente-enthalt

Gruß Wolfgang

Comments

Dankeschön!!

Warum aber 2 * 2^z ?

---

2^z Teilmengen der reduzierten Menge M₂  ( sind auch Teilmengen der "Obermenge" M₁)

+ 2^z zusätzliche Teilmengen von M₁ , die man erhält, wenn man zu jeder der ersten Teilmengen das Element e_z+1 dazugibt     = 2^z + 2^z = 2 · 2^z = 2^z+1  Teilmengen von M₁

Answer 2

Die leere Menge hat genau eine Teilmenge.

Die Teilmengen der Menge {1,2,3,...,n+1} kann man in zwei Kategorien einteilen:

    - Teilmengen, die n+1 nicht enthalten (also Teilmengen von {1,2,3,...,n}).

    - Teilmengen, die n+1 enthalten,

Comments

Ich verstehe nicht so ganz was das mir jetzt bringt