Bijektion Potenzmenge < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:16 Sa 12.05.2012 | | Autor: | rollroll |
| Aufgabe | a) Sei X eine Menge und {0,1} ^{X} die Menge aller Abbildungen von X in die zweielementige Menge {0,1}.
Zeige, dass die Potenzmenge P(X) die gleiche Mächtigkeit hat wie {0,1} ^{X} (indem Sie eine Bijektion explizit angeben)
b) Bestimme m.H. von a) die Elementzahl von P(X) für ein endliches X.
c) Bestimme für ein endliches X und k [mm] \in IN_0 [/mm] die Anzahl N(k,X) der A [mm] \in [/mm] P(X) mit |A|=k und folgere eine Formel für die Summe der N(k,X) über k. |
a) Also allgemein gibt es ja [mm] n^k [/mm] Abbildungen von k nach n. Ich weiß , dass die Potenzmenge die Mächtigkeit [mm] 2^{|X|} [/mm] hat. Also muss auch {0,1} ^X diese Mächtigkeit besitzen. Wie gibt man aber nun die Bijektion an?
b) Genügt es hier mit Induktion zu beweisen, dass die Potenzmenge die Mächtigkeit [mm] 2^{|M|} [/mm] hat? Bin mir aber unsicher, weil man dann ja nicht wirklich Teil A) benutzt hat...
c) Habe ich bisher keinen Ansatz.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:21 Sa 12.05.2012 | | Autor: | cycore |
Hallo rollroll,
> a) Sei X eine Menge und {0,1} ^{X} die Menge aller
> Abbildungen von X in die zweielementige Menge {0,1}.
> Zeige, dass die Potenzmenge P(X) die gleiche Mächtigkeit
> hat wie {0,1} ^{X} (indem Sie eine Bijektion explizit
> angeben)
>
> b) Bestimme m.H. von a) die Elementzahl von P(X) für ein
> endliches X.
>
> c) Bestimme für ein endliches X und k [mm]\in IN_0[/mm] die Anzahl
> N(k,X) der A [mm]\in[/mm] P(X) mit |A|=k und folgere eine Formel
> für die Summe der N(k,X) über k.
> a) Also allgemein gibt es ja [mm]n^k[/mm] Abbildungen von k nach n.
Meinst du damit, daß es [mm]n^k[/mm] Abbildungen von einer [mm]n[/mm]-elementigen in eine [mm]k[/mm]-elementige Menge gibt?
> Ich weiß , dass die Potenzmenge die Mächtigkeit [mm]2^{|X|}[/mm]
> hat. Also muss auch {0,1} ^X diese Mächtigkeit besitzen.
> Wie gibt man aber nun die Bijektion an?
Nunja, eine Abbildung [mm]X\to\{0,1\}[/mm] ist doch eindeutig dadurch bestimmt, welche Elemente von [mm]X[/mm] auf eins abgebildet werden (, denn die anderen werden dann auf null abgebildet und die Abbildung ist wohlerklärt). Mit anderen Worten, jede Abbildung [mm]X\to\{0,1\}[/mm] ist von der Form
[mm]\chi_A\colon x\mapsto\begin{cases} 1, & \mbox{falls } x\in A \\
0, & \mbox{sonst, d.h. falls } x\in X\setminus A \end{cases}[/mm] für eine Teilmenge A von X; und je zwei verschiedene Teilmengen liefern verschiedene Abbildungen. Das musst du jetzt nurnoch übersetzen.
> b) Genügt es hier mit Induktion zu beweisen, dass die
> Potenzmenge die Mächtigkeit [mm]2^{|M|}[/mm] hat? Bin mir aber
> unsicher, weil man dann ja nicht wirklich Teil A) benutzt
> hat...
Da du ja ausdrücklich a) benutzen sollst: Du weißt doch nach a), daß genausoviele Abbildungen [mm]X\to\{0,1\}[/mm] existieren, wie X Teilmengen besitzt. Wenn du nun schon wüsstest wie viele Abbildungen existieren, dann würdest du auch die Mächtigkeit der Potenzmenge kennen.
> c) Habe ich bisher keinen Ansatz.
Umformuliert lautet die Frage doch "Wie viele k-elementige Teilmengen besitzt eine n-elementige Menge?". Tipp: Was ist [mm](a+b)^n[/mm] und was bedeutet der Koeffizient von [mm]a^k b^{n-k}[/mm]?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:18 Mo 14.05.2012 | | Autor: | rollroll |
Meinst du damit, daß es [mm] n^k [/mm] Abbildungen von einer n-elementigen in eine k-elementige Menge gibt? Ja, so war das gemeint. Also die Anzahl aller Abbildungen von {1,...k}-->{1,...n}
Habe ich es richtig verstanden, dass
Quelltext $ [mm] \chi_A\colon x\mapsto\begin{cases} 1, & \mbox{falls } x\in A \\ 0, & \mbox{sonst, d.h. falls } x\in X\setminus A \end{cases} [/mm] $
die Bijektion angeben soll?
Es gibt doch genau [mm] 2^X [/mm] Abbildungen von X in die Menge {0,1}, oder? und [mm] 2^{|x|} [/mm] entspricht doch dann genau der Mächtigkeit der Potenzmenge.
zu c) [mm] (a+b)^n= \summe_{k=0}^{n}\vektor{n \\ k}a^{n-k}b^k.
[/mm]
Der Koeffizient ist der Binomialkoeffizient. Also [mm] \vektor{n \\ k}= \bruch{n!}{k!(n-k)!} [/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:41 Mo 14.05.2012 | | Autor: | fred97 |
> Meinst du damit, daß es [mm]n^k[/mm] Abbildungen von einer
> n-elementigen in eine k-elementige Menge gibt? Ja, so war
> das gemeint. Also die Anzahl aller Abbildungen von
> {1,...k}-->{1,...n}
>
> Habe ich es richtig verstanden, dass
> Quelltext [mm]\chi_A\colon x\mapsto\begin{cases} 1, & \mbox{falls } x\in A \\ 0, & \mbox{sonst, d.h. falls } x\in X\setminus A \end{cases}[/mm]
> die Bijektion angeben soll?
Du sollst doch eine Bijektion [mm] \phi [/mm] von P(X) auf [mm] \{0,1\}^X [/mm] angeben.
Dieses [mm] \phi [/mm] leistet das Gewünschte:
[mm] \phi(A):= \chi_A
[/mm]
FRED
>
> Es gibt doch genau [mm]2^X[/mm] Abbildungen von X in die Menge
> {0,1}, oder? und [mm]2^{|x|}[/mm] entspricht doch dann genau der
> Mächtigkeit der Potenzmenge.
>
> zu c) [mm](a+b)^n= \summe_{k=0}^{n}\vektor{n \\ k}a^{n-k}b^k.[/mm]
>
> Der Koeffizient ist der Binomialkoeffizient. Also [mm]\vektor{n \\ k}= \bruch{n!}{k!(n-k)!}[/mm]
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:02 Mo 14.05.2012 | | Autor: | rollroll |
Ok, danke, wie sieht's mit den Teilen b) und c) aus?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:09 Mo 14.05.2012 | | Autor: | Marcel |
Hallo,
> Ok, danke, wie sieht's mit den Teilen b) und c) aus?
erstens noch zu a):
Du solltest Freds Behauptung auch noch beweisen! (Also dass [mm] $\phi: [/mm] A [mm] \mapsto \phi(A):=1_A$ [/mm] eine Bijektion $Pot(X) [mm] \to \{0,1\}^X=\{f: X \to \{0,1\}: f\text{ ist Abbildung}\}$ [/mm] ist. Das geht meines Erachtens am Einfachsten, indem man zeigt, dass [mm] $\phi$ [/mm] injektiv ist und surjektiv ist! Es sollte auch erwähnt werden, dass bzw. warum wirklich ein $A [mm] \subseteq [/mm] X$ auf eine Funktion von $X [mm] \to \{0,1\}$ [/mm] abgebildet wird!)
Zweitens: zu b):
Nun ja, wenn für eine endliche Menge [mm] $X\,$ [/mm] die Potenzmenge [mm] $P(X)\,$ [/mm] gleichmächtig ist zu der Menge [mm] $\{0,1\}^X=\{f: X \to \{0,1\}: f \text{ ist Abbildung}\}$:
[/mm]
Wieviele Abbildungen $X [mm] \to \{0,1\}$ [/mm] gibt es denn?
Tipp: Sei [mm] $n:=|X|\,$ [/mm] die Anzahl der Elemente von [mm] $X\,.$ [/mm] Dann existiert eine Bijektion [mm] $\phi: \{1,...,n\} \to X\,.$ [/mm] Betrachte $f [mm] \circ \phi: \{1,...,n\} \to \{0,1\}\,.$
[/mm]
1.) Wieso kann man, indem man die Anzahl der möglichen Abbildungen $f [mm] \circ \phi$ [/mm] "zählt", auch die Anzahl aller Abbildungen $f: X [mm] \to \{0,1\}$ [/mm] "zählen"?
2.) Wie kann man überhaupt die Anzahl aller Abbildungen [mm] $\{1,...,n\} \to \{0,1\}$ [/mm] "zählen"?
Hinweis zu 2.):
Nun ja: Zwei Abbildungen $p,q [mm] \in M:=\{0,1\}^{\{1,...,n\}}$ [/mm] unterscheiden sich genau dann, wenn sie (mind.) einen Funktionswert unterschiedlich haben (d.h. es gibt (mindestens) ein $m [mm] \in \{1,...,n\}$ [/mm] mit $p(m) [mm] \not=q(m)$). [/mm]
Daher überlege nun:
Ist $h [mm] \in M\,,$ [/mm] so gibt es für [mm] $h(1)\,$ [/mm] genau zwei Möglichkeiten (es kann entweder [mm] $h(1)=0\,$ [/mm] oder [mm] $h(1)=1\,$ [/mm] sein) - jede dieser zwei Möglichkeiten kann mit [mm] $h(2)\,$ [/mm] kombiniert werden, wobei es für [mm] $h(2)\,$ [/mm] ja auch wieder genau zwei Möglichkeiten gibt. Etc. pp..
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:24 Mo 14.05.2012 | | Autor: | rollroll |
danke erstmal für die Antwort!
Nun ja, ich hatte ja schon geschrieben, dass es 2^|N| Abbildungen gibt (bzw. [mm] n^k [/mm] Abbildungen von von {1,...,k} nach {1,...,n}, dass dem so ist wurde schon in der VL bewiesen)
Es gibt ja für {0,..,n} immer jeweils 2 Möglichkeiten auf {0,1} abgebildet zu werden.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:33 Mo 14.05.2012 | | Autor: | rollroll |
War das was ich zur c) geschrieben hatte eigentlich korrekt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:05 Di 15.05.2012 | | Autor: | Marcel |
Hallo,
> War das was ich zur c) geschrieben hatte eigentlich
> korrekt?
Du hast geschrieben, dass Du bisher keinen Ansatz hattest ( das war sicher korrekt :P ) und dann noch die bin. Formel und den Binomialkoeffizienten aufgeschrieben (auch die Formel ist korrekt).
Kennst Du den "kombinatotischen" Beweis der bin. Formel? Dann kannst Du mit letzterem auch was bei Deiner Aufgabe anfangen (wenn Dir dieser Bezug klar ist)...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:14 Di 15.05.2012 | | Autor: | rollroll |
Ja, diesen Beweis kenne ich. Aber einen Zusammenhang sehe ich nicht wirklich...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:23 Di 15.05.2012 | | Autor: | Marcel |
Hallo,
> Ja, diesen Beweis kenne ich. Aber einen Zusammenhang sehe
> ich nicht wirklich...
für festes [mm] $n\,$ [/mm] und festes $k [mm] \le [/mm] n$:
Du wendest ja das Distributivgesetz (und auch Kommutationgesetz) an, wenn Du [mm] $(a+b)^n=(a+b)*...*(a+b)$ [/mm] schreibst. Dann sortiert man doch gerade die Summanden [mm] "$a^kb^{n-k}$" [/mm] zusammen: Das heißt, man zählt,wieviele von denen es gibt - nennen wir die Anzahl solcher Summanden mal [mm] $anz(n,k)\,.$
[/mm]
D.h. man schreibt zunächst mal etwa
[mm] $$(a+b)^n=\sum_{k=0}^n anz(n,k)a^kb^{n-k}\,.$$
[/mm]
Induktiv sieht man mit der Definition des Bin.-Koeff. ${n [mm] \choose [/mm] k}=n!/(k!*(n-k)!)$ aber auch
[mm] $$(a+b)^n=\sum_{k=0}^n [/mm] {n [mm] \choose k}a^kb^{n-k}\,.$$
[/mm]
Etc. pp..
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:57 Di 15.05.2012 | | Autor: | rollroll |
Ok, dass zu c) habe ich soweit verstanden. Nochmal zur b) Ich hatte ja schon geschrieben, dass es [mm] 2^{|N|} [/mm] Abbildungen gibt (bzw. [mm] n^k [/mm] Abbildungen von von {1,...,k} nach {1,...,n}, dass dem so ist, wurde schon in der VL bewiesen)
Es gibt ja für {0,..,n} immer jeweils 2 Möglichkeiten auf {0,1} abgebildet zu werden. Also ist [mm] 2^n [/mm] die Elementanzahl und da es eine Bijektion (Teil a)) gibt, ist das dann auch die Elementanzahl der Potenzmenge?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:29 Di 15.05.2012 | | Autor: | Marcel |
Hallo,
> Ok, dass zu c) habe ich soweit verstanden. Nochmal zur b)
> Ich hatte ja schon geschrieben, dass es [mm]2^{|N|}[/mm] Abbildungen
> gibt (bzw. [mm]n^k[/mm] Abbildungen von von {1,...,k} nach
> {1,...,n}, dass dem so ist, wurde schon in der VL bewiesen)
strenggenommen brauchst Du hier, dass es [mm] $(k+1)^{n}$ [/mm] Abbildungen [mm] $\{1,...,n\} \to \{0,...,k\}$ [/mm] gibt. Da es aber eine triviale Bijektion [mm] $\{0,...,k\} \to \{1,...,k+1\}$ [/mm] gibt, folgt das schnell mit Deinem Wissen aus der Vorlesung.
> Es gibt ja für {0,..,n}
Da muss
[mm] $$\{\red{1},...,n\}$$
[/mm]
stehen, sonst passt
> immer jeweils 2 Möglichkeiten auf
> {0,1} abgebildet zu werden. Also ist
> [mm]2^n[/mm] die Elementanzahl
das hier nicht mehr.
> und da es eine Bijektion (Teil a)) gibt, ist das dann auch
> die Elementanzahl der Potenzmenge?
Ja! Sollte man sauber aufschreiben, aber mehr steckt da nicht dahinter!
Gruß,
Marcel
|
|
|
|
