www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Analysis-Sonstiges" - Bijektion Potenzmenge
Bijektion Potenzmenge < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Bijektion Potenzmenge: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

        
Bezug
Bijektion Potenzmenge: Antwort
Status: (Antwort) fertig Status 
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]?


Bezug
                
Bezug
Bijektion Potenzmenge: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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]


Bezug
                        
Bezug
Bijektion Potenzmenge: Antwort
Status: (Antwort) fertig Status 
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]
>  


Bezug
                                
Bezug
Bijektion Potenzmenge: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:02 Mo 14.05.2012
Autor: rollroll

Ok, danke, wie sieht's mit den Teilen b) und c) aus?

Bezug
                                        
Bezug
Bijektion Potenzmenge: zu b)
Status: (Antwort) fertig Status 
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

Bezug
                                                
Bezug
Bijektion Potenzmenge: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                                        
Bezug
Bijektion Potenzmenge: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:33 Mo 14.05.2012
Autor: rollroll

War das was ich zur c) geschrieben hatte eigentlich korrekt?

Bezug
                                                                
Bezug
Bijektion Potenzmenge: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                                        
Bezug
Bijektion Potenzmenge: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 00:14 Di 15.05.2012
Autor: rollroll

Ja, diesen Beweis kenne ich. Aber einen Zusammenhang sehe ich nicht wirklich...

Bezug
                                                                                
Bezug
Bijektion Potenzmenge: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                                                        
Bezug
Bijektion Potenzmenge: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                                                                                
Bezug
Bijektion Potenzmenge: Antwort
Status: (Antwort) fertig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]