Kombinatorisches Argument: Sei M eine endliche Menge |M| = n. Zeigen Sie |P(M)| = 2^n.

Question

Aufgabe:

Sei  eine endliche Menge mit |M| = n. Zeigen Sie: |P(M)| = \(2^{n}\). Es reicht ein kombinatorisches Argument.

Problem/Ansatz:

Meine Frage ist, was ein komb. Argument ist und wie ich dieses hierzu aufstelle.

Mir ist klar, dass:

|M|	|P(M)|
0	1 = \( 2^{0} \)
1	2 = \(2^{1}\)
2	4 = \(2^{2}\)
3	8 = \(2^{3}\)

 usw.

Ich bedanke mich schon einmal im Voraus :)

Comments

Formal vgl. https://www.mathelounge.de/164145/potenzmenge-endliche-menge-elementen-endliche-elementen

Answer 1

Betrachte eine beliebige Menge M_n mit n Elementen. Die Mächtigkeit ihrer Potenzmenge P(M_n) sei k.

Wenn jetzt ein weiteres Element z zu M_n hinzugefügt wird, entsteht M_n+1. Deren Potenzmenge enthält 2k, also doppelt so viele Elemente wie P(M_n), da zu jeder Teilmenge T⊆M_n eine weitere Teilmenge T∪{z} hinzukommt.

Wenn man jetzt mit der leeren Menge anfängt, deren Potenzmenge ja genau ein Element enthält, ergibt sich die Folge der Zweierpotenzen.

Answer 2

Vielleicht hilft diese Überlegung: Jedes der n Elemente aus M kann in einem Element aus P(M) entweder enthalten sein oder nicht enthalten sein. Das sind 2 mögliche Zustände für jedes der n Elemente aus M.

Comments

Vielen Dank für die Antwort.

Leider hilft mir das jedoch nicht dabei wie ich es korrekt aufschreiben...

---

Du wolltest kombinatorisch argumentieren. Da musst du ein paar Sätze hinschreiben und keine Formeln / Rechnungen. Das hat az0815 getan.

Jedes der n Elemente aus M kann in einem Element aus P(M) entweder enthalten sein oder nicht enthalten sein. Das sind 2 mögliche Zustände für jedes der n Elemente aus M.

Daher kann man rechnen

2 Möglichkeiten für Element Nummer 1

und dann

2 Möglichkeiten für Element Nummer 2

und

2 Möglichkeiten für Element Nummer 3

und dann

usw.

2 Möglichkeiten für Element Nummer n

D.h. 2*2*2*...*2 (n Faktoren) = 2^n.