Potenzmenge < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben sei eine Menge M mit k Elementen [mm] e_{1},,,,,, e_{k}.
[/mm]
M [mm] =\{ e_1,,,,,, e_k \}
[/mm]
a) Begrunden Sie:
Um ein Element von P(M) zu beschreiben, kann man einen k Zeichen langen
String benutzen, der nur aus Nullen und Einsen besteht.
Oder anders formuliert:
Es gibt eine bijektive Abbildung zwischen den Elementen von P(M) und den k-
stelligen Binar-Strings.
b)Beweisen Sie damit, dass gilt: |P(M)|= [mm] 2^{|M|} [/mm] = [mm] 2^{k} [/mm] |
Hallo, kann mir vlt jemand erklären was in der aufgabe verlangt wird? a) versteh ich irgendwie gar nicht und bei b) weiß ich nicht genau wie man das nachweisen solll..
Danke euch schon mal
|
|
| |
|
> Gegeben sei eine Menge M mit k Elementen [mm]e_{1},,,,,, e_{k}.[/mm]
>
> M [mm]=\{ e_1,,,,,, e_k \}[/mm]
> a) Begründen Sie:
> Um ein Element von P(M) zu beschreiben, kann man einen k
> Zeichen langen
> String benutzen, der nur aus Nullen und Einsen besteht.
> Oder anders formuliert:
> Es gibt eine bijektive Abbildung zwischen den Elementen
> von P(M) und den k-stelligen Binär-Strings.
> b)Beweisen Sie damit, dass gilt: |P(M)|= [mm]2^{|M|}[/mm] = [mm]2^{k}[/mm]
> Hallo, kann mir vlt jemand erklären was in der aufgabe
> verlangt wird? a) versteh ich irgendwie gar nicht und bei
> b) weiß ich nicht genau wie man das nachweisen solll..
Hallo,
P(M) ist die Menge aller möglichen Teilmengen von M.
Jedes Element T von P(M) ist also eine bestimmte
Teilmenge von M und ist dadurch definiert, welche
Elemente von M zu T gehören und welche nicht.
Da die Menge M endlich ist und genau k Elemente
enthält, kann man einer beliebigen Teilmenge T
eindeutig eine Folge (bzw. einen String) s aus Nullen
und Einsen der Länge k zuordnen mit
s[i]=1 falls [mm] e_i\in [/mm] T
s[i]=0 falls [mm] e_i\notin [/mm] T
Wenn dir dies klar ist, sollte die Beantwortung der
konkreten Fragen kaum noch ein Problem sein.
LG Al-Chw.
|
|
|
| |
|
doch daswas du erklärst versteh ich,aber irgenwie weiß ich gar nicht was ich da begründen soll??
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:15 Mi 15.07.2009 | | Autor: | Marcel |
Hallo,
> doch daswas du erklärst versteh ich,aber irgenwie weiß
> ich gar nicht was ich da begründen soll??
Du solltest zunächst mal beweisen, dass die von Al angegebene Abbildung bijektiv ist. Also injektiv und surjektiv ist. Und die Menge der [mm] $k\,$-stelligen [/mm] Binär-Strings kannst Du einfach als die Menge aller [mm] $k\,-$Tupel [/mm] mit Werten in [mm] $\{0,1\}$ [/mm] auffasen, d.h.
[mm] $$\{(x_1,\,\ldots,\,x_k) : \forall j \in \{1,\ldots,\,k\}:\;x_j \in \{0,\,1\}\}\,.$$
[/mm]
Bei a) ist also zu zeigen, dass, für [mm] $M=\{e_1,\ldots,\,e_k\}$ [/mm] mit $|M|=k < [mm] \infty$, [/mm] die von Al vorgeschlagene Abbildung
[mm] $$\text{Pot}(M) \to \{(x_1,\,\ldots,\,x_k): \forall j \in \{1,\ldots,\,k\}:\;x_j \in \{0,\,1\}\}$$
[/mm]
bijektiv ist (die Abbildungsvorschrift entnimmst Du Als Post); es ist für diese Abbildung also Injektivität und Surjektivität zu beweisen.
(Zum Verständnis ein Beispiel:
Ist [mm] $M=\{e_1,e_2,e_3\}$ [/mm] 3 elementig, so ist [mm] $T=\{e_1,e_3\} \in \text{Pot}(M) [/mm] $ und Al's Abbildung ordnet der Menge [mm] $T\,,$ [/mm] welche ja ein Element von [mm] $\text{Pot}(M)$ [/mm] ist, da $T [mm] \subseteq [/mm] M$ gilt, gerade den String $[1,0,1]$ bzw. das [mm] $3\,$-Tupel [/mm] $(1,0,1)$ zu. Umgekehrt:
Geben wir uns z.B. den [mm] $3\,$-String [/mm] $[0,1,1]$ (bzw. das [mm] $3\,$-Tupel [/mm] $(0,1,1)$) vor, so wissen wir aus Al's Abbildungsvorschrift, dass dieses zu der Menge [mm] $\tilde{T}=\{e_2,e_3\} \in \text{Pot}(M)$ [/mm] gehört. Und der "Nullstring" gehört dann immer zu [mm] $\emptyset$, [/mm] welche natürlich auch immer ein Element der Potenzmenge einer Menge ist.)
Bei der Aufgabe b):
Wieviele Elemente die Menge [mm] $\{(x_1,\,\ldots,\,x_k): \forall j \in \{1,\ldots,\,k\}:\;x_j \in \{0,\,1\}\}$ [/mm] hat, weißt Du sicher, kannst Du Dir überlegen oder ![[]](/images/popup.gif) hier nochmal nachlesen. (Beachte: [mm] $|\{0,\,1\}|=2$.)
[/mm]
Und da eine Bijektion zwischen [mm] $\text{Pot}(M)$ [/mm] und [mm] $\{(x_1,\,\ldots,\,x_k): \forall j \in \{1,\ldots,\,k\}:\;x_j \in \{0,\,1\}\}$ [/mm] existiert, kannst Du somit auch folgern, wieviele Elemente [mm] $\text{Pot}(M)$ [/mm] enthält. Nämlich genausoviele wie [mm] $\{(x_1,\,\ldots,\,x_k): \forall j \in \{1,\ldots,\,k\}:\;x_j \in \{0,\,1\}\}\,.$
[/mm]
Gruß,
Marcel
|
|
|
|
