Potenzmenge < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:22 Di 08.03.2011 | | Autor: | Mandy_90 |
| Aufgabe | | Man beweise mittels vollständiger Induktion, dass die Potenzmenge p(X) einer n-elementigen Menge genau [mm] 2^{n} [/mm] Elemente hat. |
Guten Abend liebe Mitglieder^^
Ich bin bei dieser Aufgabe bei dem Induktionsschritt nicht mehr weitergekommen und hoffe ihr könnt mir helfen.
Zunächst ist die Potenzmenge definiert als [mm] p(X)=\{y:y \subset X\}, [/mm] wobei [mm] X=\{x_{1},...x_{n}\} [/mm] eine Menge ist.
Für n=1 gilt die Behauptung. Die IV ist jetzt gegeben.
IS: Für n+1 ist die Menge [mm] X=\{x_{1},...,x_{n+1}\} [/mm] und das ist das gleiche wie [mm] X_{1}=\{x_{1},...,x_{n}\} \cup \{x_{n+1}\}=X_{2}.
[/mm]
[mm] p(X_{1}) [/mm] hat nach IV [mm] 2^{n} [/mm] Elemente und [mm] p(X_{2}) [/mm] hat 2 Elemente.
Jetzt muss eigentlich rauskommen,dass p(X) [mm] 2^{n+1} [/mm] Elemente hat. Dafür müsste ich [mm] 2^{n}*2=2^{n+1} [/mm] rechnen. Ich versteh aber nicht wieso. Ich hätte jetzt [mm] 2^{n}+2 [/mm] gerechnet, aber das ist nicht [mm] 2^{n+1}.
[/mm]
Vielen Dank
lg
|
|
| |
|
Hallo,
> Man beweise mittels vollständiger Induktion, dass die
> Potenzmenge p(X) einer n-elementigen Menge genau [mm]2^{n}[/mm]
> Elemente hat.
> Guten Abend liebe Mitglieder^^
>
> Ich bin bei dieser Aufgabe bei dem Induktionsschritt nicht
> mehr weitergekommen und hoffe ihr könnt mir helfen.
>
> Zunächst ist die Potenzmenge definiert als [mm]p(X)=\{y:y \subset X\},[/mm]
> wobei [mm]X=\{x_{1},...x_{n}\}[/mm] eine Menge ist.
>
> Für n=1 gilt die Behauptung. Die IV ist jetzt gegeben.
>
> IS: Für n+1 ist die Menge [mm]X=\{x_{1},...,x_{n+1}\}[/mm] und das
> ist das gleiche wie [mm]X_{1}=\{x_{1},...,x_{n}\} \cup \{x_{n+1}\}=X_{2}.[/mm]
>
> [mm]p(X_{1})[/mm] hat nach IV [mm]2^{n}[/mm] Elemente und [mm]p(X_{2})[/mm] hat 2 Elemente.
Das ist Unsinn. Die Menge [mm] X_{n+1} [/mm] selbst hat n+1 Elemente. Es kommt doch beim Induktionsschritt eins dazu. Die Potenzmenge [mm] p(X_N) [/mm] der Menge [mm] X_n [/mm] mit n Elementen hat nach Induktionsvoraussetzung [mm] 2^n [/mm] Elemente.
> Jetzt muss eigentlich rauskommen,dass p(X) [mm]2^{n+1}[/mm]
> Elemente hat. Dafür müsste ich [mm]2^{n}*2=2^{n+1}[/mm] rechnen.
> Ich versteh aber nicht wieso. Ich hätte jetzt [mm]2^{n}+2[/mm]
> gerechnet, aber das ist nicht [mm]2^{n+1}.[/mm]
Tipp für den Induktionsschritt:
Nimm das neu hinzugekommene Element [mm] x_{n+1} [/mm] als "Fixpunkt".
Betrachte getrennt die Anzahl der Teilmengen von [mm] X_{n+1}, [/mm] die
a) [mm] x_{n+1} [/mm] enthalten
b) [mm] x_{n+1} [/mm] nicht enthalten.
Wie viele sind das jeweils?
>
> Vielen Dank
> lg
LG
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:22 Fr 11.03.2011 | | Autor: | Mandy_90 |
Hallo, erstmal danke für deine Hilfe.
> > Für n=1 gilt die Behauptung. Die IV ist jetzt gegeben.
> >
> > IS: Für n+1 ist die Menge [mm]X=\{x_{1},...,x_{n+1}\}[/mm] und das
> > ist das gleiche wie [mm]X_{1}=\{x_{1},...,x_{n}\} \cup \{x_{n+1}\}=X_{2}.[/mm]
>
> >
> > [mm]p(X_{1})[/mm] hat nach IV [mm]2^{n}[/mm] Elemente und [mm]p(X_{2})[/mm] hat 2
> Elemente.
> Das ist Unsinn. Die Menge [mm]X_{n+1}[/mm] selbst hat n+1 Elemente.
> Es kommt doch beim Induktionsschritt eins dazu. Die
> Potenzmenge [mm]p(X_N)[/mm] der Menge [mm]X_n[/mm] mit n Elementen hat nach
> Induktionsvoraussetzung [mm]2^n[/mm] Elemente.
Ok, ich versteh aber nicht ganz, wieso ich die Menge [mm] X_{n+1} [/mm] nicht als Vereiningung schreiben darf ?
> Tipp für den Induktionsschritt:
> Nimm das neu hinzugekommene Element [mm]x_{n+1}[/mm] als
> "Fixpunkt".
> Betrachte getrennt die Anzahl der Teilmengen von [mm]X_{n+1},[/mm]
> die
> a) [mm]x_{n+1}[/mm] enthalten
> b) [mm]x_{n+1}[/mm] nicht enthalten.
> Wie viele sind das jeweils?
a) Das müssten n! Elemente sein.
b) Das müssten nach IV [mm] 2^{n} [/mm] Elemente sein.
Muss ich jetzt [mm] n!+2^{n} [/mm] rechnen? Das kann nicht stimmen. Ich glaube die n! stimmt nicht, aber wie krieg ich das denn jetzt raus? Ich komm grad nicht mehr weiter.
lg
|
|
|
| |
|
Hallo,
> Hallo, erstmal danke für deine Hilfe.
> > > Für n=1 gilt die Behauptung. Die IV ist jetzt
> gegeben.
> > >
> > > IS: Für n+1 ist die Menge [mm]X=\{x_{1},...,x_{n+1}\}[/mm] und das
> > > ist das gleiche wie [mm]X_{1}=\{x_{1},...,x_{n}\} \cup \{x_{n+1}\}=X_{2}.[/mm]
>
> >
> > >
> > > [mm]p(X_{1})[/mm] hat nach IV [mm]2^{n}[/mm] Elemente und [mm]p(X_{2})[/mm] hat 2
> > Elemente.
> > Das ist Unsinn. Die Menge [mm]X_{n+1}[/mm] selbst hat n+1
> Elemente.
> > Es kommt doch beim Induktionsschritt eins dazu. Die
> > Potenzmenge [mm]p(X_N)[/mm] der Menge [mm]X_n[/mm] mit n Elementen hat nach
> > Induktionsvoraussetzung [mm]2^n[/mm] Elemente.
>
> Ok, ich versteh aber nicht ganz, wieso ich die Menge
> [mm]X_{n+1}[/mm] nicht als Vereiningung schreiben darf ?
Kannst du gerne machen.
Aber es macht keinen Sinn beim Induktionsanfang für [mm] X_1 [/mm] von der IV zu sprechen (das passiert unten). Es ist klar, dass [mm] p(X_1)=\{\emptyset, \{x_1\}\} [/mm] zwei Elemente enthält. Das ist der IA.
Wie kommst du überhaupt darauf, das [mm] p(X_2) [/mm] zwei Elemente hat?
>
> > Tipp für den Induktionsschritt:
> > Nimm das neu hinzugekommene Element [mm]x_{n+1}[/mm] als
> > "Fixpunkt".
> > Betrachte getrennt die Anzahl der Teilmengen von
> [mm]X_{n+1},[/mm]
> > die
> > a) [mm]x_{n+1}[/mm] enthalten
> > b) [mm]x_{n+1}[/mm] nicht enthalten.
> > Wie viele sind das jeweils?
>
> a) Das müssten n! Elemente sein.
Nein, es gibt auch hier [mm] 2^n [/mm] Elemente. Nimm dir jede Teilmenge aus b) und füge einmal das Element [mm] x_{n+1} [/mm] dazu und es entsteht eine Teilmenge, die zu a) gehört.
> b) Das müssten nach IV [mm]2^{n}[/mm] Elemente sein. ![[ok]](/images/smileys/ok.gif "[ok]")
>
> Muss ich jetzt [mm]n!+2^{n}[/mm] rechnen? Das kann nicht stimmen.
> Ich glaube die n! stimmt nicht, aber wie krieg ich das denn
> jetzt raus? Ich komm grad nicht mehr weiter.
>
> lg
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:36 Fr 11.03.2011 | | Autor: | Mandy_90 |
> > Ok, ich versteh aber nicht ganz, wieso ich die Menge
> > [mm]X_{n+1}[/mm] nicht als Vereiningung schreiben darf ?
> Kannst du gerne machen.
> Aber es macht keinen Sinn beim Induktionsanfang für [mm]X_1[/mm]
> von der IV zu sprechen (das passiert unten). Es ist klar,
> dass [mm]p(X_1)=\{\emptyset, \{x_1\}\}[/mm] zwei Elemente enthält.
> Das ist der IA.
Ja,aber bei mir war [mm] X_{1}=\{x_{1},...,x_{n}\} [/mm] und [mm] X_{2}=\{x_{n+1}\}.(Habs [/mm] mir von der Notation her etwas ungeschickt definiert).Deswegen hat auch [mm] p(X_{2}) [/mm] 2 Elemente, einmal [mm] x_{n+1} [/mm] und einmal [mm] \emptyset.
[/mm]
> Wie kommst du überhaupt darauf, das [mm]p(X_2)[/mm] zwei Elemente
> hat?
> > a) Das müssten n! Elemente sein.
> Nein, es gibt auch hier [mm]2^n[/mm] Elemente. Nimm dir jede
> Teilmenge aus b) und füge einmal das Element [mm]x_{n+1}[/mm] dazu
> und es entsteht eine Teilmenge, die zu a) gehört.
> > b) Das müssten nach IV [mm]2^{n}[/mm] Elemente sein.
Ah ok.Habs verstanden. Vielen Dank
lg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:42 Fr 11.03.2011 | | Autor: | kamaleonti |
Hallo,
> > > Ok, ich versteh aber nicht ganz, wieso ich die Menge
> > > [mm]X_{n+1}[/mm] nicht als Vereiningung schreiben darf ?
> > Kannst du gerne machen.
> > Aber es macht keinen Sinn beim Induktionsanfang für [mm]X_1[/mm]
> > von der IV zu sprechen (das passiert unten). Es ist klar,
> > dass [mm]p(X_1)=\{\emptyset, \{x_1\}\}[/mm] zwei Elemente enthält.
> > Das ist der IA.
>
> Ja,aber bei mir war [mm]X_{1}=\{x_{1},...,x_{n}\}[/mm] und
> [mm]X_{2}=\{x_{n+1}\}.(Habs[/mm] mir von der Notation her etwas
> ungeschickt definiert).Deswegen hat auch [mm]p(X_{2})[/mm] 2
> Elemente, einmal [mm]x_{n+1}[/mm] und einmal [mm]\emptyset.[/mm]
Ok. Nochmal zum Vermeiden von Verwirrung: Bei unserem Beweis am Ende bezeichnet [mm] X_n [/mm] allgemein eine n-elementige Menge. 
>
> > Wie kommst du überhaupt darauf, das [mm]p(X_2)[/mm] zwei Elemente hat?
>
> > > a) Das müssten n! Elemente sein.
> > Nein, es gibt auch hier [mm]2^n[/mm] Elemente. Nimm dir jede
> > Teilmenge aus b) und füge einmal das Element [mm]x_{n+1}[/mm] dazu
> > und es entsteht eine Teilmenge, die zu a) gehört.
> > > b) Das müssten nach IV [mm]2^{n}[/mm] Elemente sein.
>
> Ah ok.Habs verstanden. Vielen Dank
> lg
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:03 Fr 11.03.2011 | | Autor: | SEcki |
> Jetzt muss eigentlich rauskommen,dass p(X) [mm]2^{n+1}[/mm]
> Elemente hat. Dafür müsste ich [mm]2^{n}*2=2^{n+1}[/mm] rechnen.
> Ich versteh aber nicht wieso. Ich hätte jetzt [mm]2^{n}+2[/mm]
> gerechnet, aber das ist nicht [mm]2^{n+1}.[/mm]
Aber wieso denn "+"?
Es gilt viel mehr: Seien A und B Mengen, dann gilt dass [mm]P(A)\times P(B)\to P(A\cup B), (a,b)\mapsto a\cup b[/mm] eine Bijektion ist (für disjunkte Mengen A, B). Weiterhin gilt [mm]|A\times B|=|A|*|B|[/mm].
SEcki
|
|
|
|
