0 Daumen
13k Aufrufe

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

Avatar von

2 Antworten

+1 Daumen
 
Beste Antwort

Hallo Samira,

du willst folgende Aussage A(n) beweisen:

Für alle n ∈ ℕ0 gilt: Jede Menge mit n Elementen hat 2n 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 ∈ ℕ0  wahr ist, dann ist auch A(z+1) wahr ]

Nachweis:

1)

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

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

2) 

Sei  M1 = { e1 , e2 ,  ..... , ez , ez+1 } eine Menge mit z+1 Elementen

Dann hat M2 = { e1 , e2 ,  ..... , ez }  nach Induktionsvoraussetzung A(z)   2z  Teilmengen

Diese sind alle auch Teilmengen von M1

Jede weitere Teilmengen von M1 erhält man, wenn man eine der Teilmengen von M2 um das Element ez+1 erweitert.

Insgesamt hat M1 also 2 · 2z = 2z+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

Avatar von 86 k 🚀

Dankeschön!!

Warum aber 2 * 2^z ?

2z Teilmengen der reduzierten Menge M2  ( sind auch Teilmengen der "Obermenge" M1)

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

0 Daumen

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,

Avatar von 105 k 🚀

Ich verstehe nicht so ganz was das mir jetzt bringt

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community