Mächtigkeit der Potenzmenge und Summe der Kehrwerte

Question

könnte jemanden mir helfen

(a) Z.z.  : sei M endliche Menge mit m Elementen. Dann ist die Mächtigkeit der Potenzmenge IP(M)I = 2^m.

(b) Sei n eine natürliche Zahl. Man nehme alle nichtleeren Teilmengen der Zahlen von 1bis n. Für jede dieser Teilmengen bilde man das Produkt aller Elemente und nehme den Kehrwert. Zeigen Sie: Die Summe der Kehrwerte ist n.

Comments

Vom Duplikat:

Titel: Vollständige Induktion: Mächtigkeit der Potenzmenge

Stichworte: induktion,vollständige,potenzmenge,mächtigkeit

Da ich zur Zeit unter Zeitdruck stehe, frage ich lieber hier noch einmal:

Ich soll per vollständiger Induktion beweisen:

Für die Kardinalität der Potenzmenge einer endlichen Menge M gilt: | 2^M | = 2^ |M|

Leider habe ich hier gar keine Ahnung...

---

EDIT: Bitte eine Frage / Frage. Dann merkst du schnell, dass deine Frage bereits (mehrmals) beantwortet wurde. Besser noch: Erst mal die Suche bemühen. Vgl. Schreibregeln (ganz unten) .

Bsp. https://www.mathelounge.de/310372/frage-einem-bestimmten-beweises-machtigkeit-potenzmenge

und

https://www.mathelounge.de/369561/induktion-die-potenzmenge-einer-menge-elementen-elemente 

usw.

Answer 1

sei M endliche Menge mit m Elementen. Dann ist die Mächtigkeit derPotenzmenge IP(M)I = 2^m.

Mit vollst. Induktion nach m.

Ind.anf.  m=1   M hat ein Element, also zwei Teilmengen, nämlich ∅ und M.

Sei es nun gültig für m.

==>   Wenn M eine m+1 elementige Menge ist, so wähle ein a∈M (Das gibt es, weil M nicht leer.)

Dann gilt für jede Teilmenge T von M einer der beiden Fälle   a∈T  oder a∉T.

Die Teilmengen von M mit a∉T  sind alle Teilmengen von M \ {a}, das ist eine

m-elementige Menge, also gibt es davon nach Ind.vor,  2^m Stück.

Jede Teilmenge mit   a∈T  wird durch Wegnahme von a zu einer Teilmenge

von M \ {a}  , also gibt es auch davon  2^m Stück.

2^m + 2^m  = 2* 2^m  =  2^m+1 .   q.e.d.

Comments

Vielen dank, hast du ein Tipp für b) ?

Answer 2

Kann zu, ich hab es jetzt so gelöst:

Anfang: n=0

Potenzmenge der leeren Menge enthält nur leere Menge.

Schritt n->n+1

Sie M_n+1 eine Menge mit (n+1) Elementen und M_n eine Teilmenge mit n Elementen.

Die Potenzmenge 2^m_n enthält nach InduktionVoraussetzung genau 2ⁿ Elemente.

Für die Erzeugung von 2^m_n+1 kann 2^m_n verwendet werden, da es eine Teilmenge von 2^m_n+1 ist. Dazu wird jedes Element von 2^m_n mit dem Element e _n+1 vereinigt. So beträgt die Anzahl an Elementen 2ⁿ*2ⁿ = 2*2ⁿ = 2ⁿ⁺¹

Comments

Danke dir.

Hast du vielleicht einen Tipp für b) ?