Potenzmenge < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Beweise das die Potenzmenge aus [mm] 2^{n} [/mm] Elementen besteht. |
Folgender Beweis wurde mir vorgestellt, den ich allerdings nicht verstanden habe.
Sei [mm] \Omega={a_{1},...,a_{n}}
[/mm]
Jede Teilmenge von [mm] \Omega [/mm] lässt sich eindeutig als Dualzahl schreiben. Dabei bedeute 1 an der i-ten Stelle das [mm] a_{i} \in [/mm] A und eine 0 das [mm] a_{i} [/mm] kein Element von A ist.
Jetzt kommt der Teil den ich nicht verstehe.
Diese Dualzahlen sind die ganzen Zahlen von 0 bis zu einer größten Zahl N, die als Duahlzahl an jeder der n Stellen eine 1 stehen hat, also N=1111...1. Da sich die [mm] \IN [/mm] selber abzählen, sind dies N+1 Zahlen. N+1 lässt sich als 100...0 schreiben (Warum?). Das ist aber die natürlich Zahl [mm] 2^{n} [/mm] (Den Schluss verstehe ich auch nicht). Somit gibt es [mm] 2^{n} [/mm] Teilmengen von [mm] \omega [/mm] (kapier ich auch nicht).
Damit ist 0 als Repräsentat der [mm] \emptyset [/mm] gemeint und N=1111...1 als [mm] \omega. [/mm] Das sind N+1 Zahlen. Ok.
Ich denke, ein möglicher Beweis wäre, dass ich sage, aus einer n elementigen Menge kann ich in der Anzahl [mm] \summe_{i=1}^{n}=\bruch{n!}{k!(n-k)!} [/mm] verschiedene Mengen erzeugen. Und die Summe ist gerade, beweisbar durch Induktion, [mm] 2^{n}. [/mm]
Ist mein Beweis so ok? und wie funktionieren die obenstehenden Schlüsse. Den Trick würde ich gern verstehen.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:13 So 17.09.2006 | | Autor: | Palin |
Du stelst die Zahl hier im Dualsistem da 010 ist zb = 2 und 3 ist 011;
wenn du jetzt zu 3, 1 addierst fängst du hinten an steht dort eine 1 wird die zur 0 und du gehst ein weiter usw.
also ist 4 = 100
um nun den Werd der dezimal Zahl zu bestimmen kannst du von hinten die stelle zählen an der die 1 steht. Wenn du nun 1 von der Zahl abziest entsprichtes dem n mit welchem 2 hochgenommen werden muss um den Wert an der Stelle zu bestimmen.
Bei 4 => 1 an 3. Stelle von hinten => [mm] 2^2
[/mm]
Wenn du nun eine Zahl hast mit n Stellen die alle 1 sind du 1 draufrechnest werden die 1er alle zur 0 und du hast an der Stelle n+1 eine 1 was im Dezimalsystem wider der Zahl [mm] 2^n [/mm] entspricht.
|
|
|
|
