Eine n-elementige Menge X besitzt 2^n Teilmengen

Question

Ich versuche die obige Behauptung mit vollständiger Induktion zu beweisen, bleibe aber dann beim Induktionsschritt hängen und komme nicht weiter.

Induktionsanfang:

Sei n_0 = 0. Dann ist #P({ }) = 1 = 2^0. Somit ist die Aussage für n=0 wahr.

Induktionsschritt:

-Angenommen, die Aussage sei für ein festes, aber beliebiges n∈ℕ∪{0} wahr, sodass gilt: #P(X) = 2^n.

-Dann gilt diese Aussage auch für n+1,also #P(X∪{n+1}) = 2^{n+1}

-Dies zeigt man so: #P(X∪{n+1})

= #{A: A⊆ X v A⊆{n+1}}

= #{A: A⊆ X v (A⊆{n+1} ∧ { }⊆{n+1})}

= #{A: (A⊆ X v A⊆{n+1}) ∧ (A⊆ Xv { }⊆{n+1})}

Nur ab hier komm ich nicht weiter und weiß nicht wie ich hiervon ausgehend auf 2^{n+1} kommen soll.

Answer 1

  Mal eine grundsätzliche Antwort, wie ich mir das immer klar gemacht habe.  Für das erste Element e1 der Menge gibt es bei jeder  Teilmenge zwei Möglichkeiten: Gehöre ich dazu oder nicht?  Genau so für das zweite; macht schon 2 * 2 . Und so weiter.  

Comments

Aber was soll mir das jetzt bringen?

Ich habe mir folgendes Beispiel überlegt. Eine endliche Menge A={1,2}. Dann ist P(A)={{ },{1},{2},{1,2}}.

Mit der Menge B={1,2,3} hätte ich dann P(B) = {{ },{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}.

Nur könnte ich das jetzt auch mit zich weiteren Mengen durchführen, hätte aber keine Idee, wie ich allgemein argumentieren kann, dass tatsächlich die Anzahl einer n-elementigen Menge immer 2^n sein soll. Habe zwar nach anderen Lösungen geschaut, als ich keine weitere Idee mehr hatte, wo das auch thematisiert wurde, aber die bringen mich gar nicht weiter. Zum Beispiel wurde einfach gesagt, dass man eine (n+1) elementige Menge hat, nun aber jetzt das (n+1) te Element ausschließt und nun wieder nur 2^n viele Elemente hat. Soweit so gut, aber der Rest ist dann nur noch unverständlicher Salat von weiteren Mengen...

---

Vielleicht ist ja der Induktionsschritt ganz einfach.  Du gehst davon aus, jede Menge  M_n  besitzt  2  ^  n  Teilmengen.  Aber keine von ihnen enthält  Element  x_n+1  .    Gleichzeitig  ist jede dieser  2  ^   n  Untermengen aber auch Teilmenge von M_n+1 .

      Aus diesen Teilmengen generierst du  2  ^ n  neue, indem du jeder noch das Element  x_n+1 hinzu fügst  - wzbw

---

Hallo habakuktibatong,

ich finde diese Idee sehr gut. So rum habe ich mir das noch nicht überlegt gehabt. So ergibt das für mich auch einen nachvollziehbaren Sinn, warum es dann 2^{n+1} Teilmengen sind. :)

Answer 2

Schreibe 2ⁿ⁺¹ als 2*2ⁿ und zeige dass mit einem zusätzlichen element (das man zu jeder der 2ⁿ Teilmengen zufügt nochmal 2ⁿ entstehen.

Gruß lul

Comments

Ich weiß nicht, wie ich das formal aufschreiben soll.

Answer 3

schau mal in diese frühere Antwort von mir:

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

Gruß Wolfgang

Comments

Danke für den Link. Aber ich stolpere auch hier über etwas. Wenn man von einer (n+1) elemtigen Menge ein Element e rausnimmt, dann hat man laut Induktionsvoraussetzung nur 2^n viele Elemente. Aber warum kann man denn jetzt aufeinmal daraus schlussfolgern, dass alle Teilmengen die noch übrig sind vereinigt mit den Teilmengen, wo das Element e drin ist ausgerechnet dann 2^{n+1} betragen soll???

---

Außer den 2ⁿ Teilmengen ohne e (nach Induktionsvoraussetzung) hat man noch einmal 2ⁿ Teilmengen, wenn man in jede der ersteren Teilmengen e hineinwirft. Das sind dann insgesamt 2 * 2^n = 2^{n+1} Teilmengen.

---

Ich habe es nun folgendermaßen formuliert:

Induktionsanfang:

Sei n_0 = 0. Dann ist #P({ }) = 1 = 2^0. Somit ist die Aussage für n=0 wahr.

Induktionsschritt:

-Angenommen, die Aussage sei für ein festes, aber beliebiges n∈ℕ∪{0} wahr, sodass gilt: #P(X) = 2^n.

-Dann gilt diese Aussage auch für n+1,also #P(X∪{n+1}) = 2^{n+1}

-Dies zeigt man so:

Man hat zunächst eine (n+1)-elementige Menge X*=X∪{n+1}. Nach Induktionsvoraussetzung hat aber X*\{n+1} auch wieder 2^n viele Teilmengen. Außerdem gilt X⊂X*, d.h. alle Teilmengen aus X sind auch in X* enthalten. Für X*\X sind dann also nur noch die Teilmengen enthalten, wo das (n+1)-te Element drinsteckt. Insgesamt gibt es davon auch wieder 2^n viele Teilmengen davon. Das bedeutet nun, dass die Vereinigungsmenge X*∪X*\X zusammen 2*2^n viele Teilmengen besirzt, d.h #P(X*)=#P(X∪{n+1})= 2^{n+1}.