Mächtigkeit der Potenzmenge < naiv < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:27 Do 31.01.2008 | | Autor: | cReam |
| Aufgabe | Zeigen Sie, dass für eine Menge A mit |A|=n gilt:
[mm] |\mathcal{P}(A)|=2^{n} [/mm] |
Hallo,
nun zu meiner Frage: :)
Wir haben dieses Beweis folgendermaßen gelöst:
1.) Indiktionsanfang: [mm] n_{0} [/mm] = 1
[mm] \Rightarrow [/mm] |A|=1
[mm] \Rightarrow |\mathcal{P}(A)|=|{\emptyset;a}|=2
[/mm]
und [mm] 2^{1}=2 [/mm]
[mm] \Rightarrow [/mm] richtig.
2.) Induktionsannahme:
[mm] |\mathcal{P}(A)|=2^{n}
[/mm]
3.) Induktionsschritt:
Für n+1
Die Teilmengen von B lassen sich in 2 Gruppen einteilen:
a) die, die b enthalten
b)die, die b nicht enthalten
[mm] |\mathcal{P}(B)|=\underbrace{|\mathcal{P}(A)|}_{=2^{n}} [/mm] + [mm] \underbrace{|{V\cup{b}: V\subset|\mathcal{P}(A)|}}_{=2^{n}} [/mm] = [mm] 2*2^{n} [/mm] = [mm] 2^{n+1}
[/mm]
Die erstens zwei Schritte verstehe ich, aber die Gleichung die wir aufstellen verstehe ich leider überhaupt nicht...
Vielen Dank für eure Hilfe!
Grüße
Cream
|
|
| |
|
Hallo cReam,
Betrachte die Potenzmenge von [mm]A:=\{2\}[/mm]. Diese lautet:
[mm]\{\{2\},\emptyset\}[/mm]
Willst du nun noch das Element [mm]\{1\}[/mm] zu [mm]A\![/mm] hinzufügen, mußt du entsprechend alle Elemente der ursprünglichen Potenzmenge mit diesem Element vereinigen. Da aber diese neue Menge [mm]A'\![/mm] noch die ursprüngliche Menge [mm]A\![/mm] beinhaltet, hast du auch immer noch die ursprünglichen Konstruktionsmöglichkeiten der Potenzmenge von [mm]A\![/mm] ohne das neue Element. Also gilt:
[mm]\mathcal{P}(\{1,2\}) = \{\{2\}\cup\{1\},\emptyset\cup\{1\}\}\cup\{\{2\},\emptyset\}[/mm]
Grüße
Karl
|
|
|
|
