Potenzmenge < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:03 Mo 04.08.2008 | | Autor: | Plapper |
| Aufgabe | | Ist A eine Menge mit n Elementen, so enthält die Potenzmenge [mm] \mathcal{P} [/mm] (A) [mm] 2^{n} [/mm] Elemente |
Hallo...
Ich lerne auf meine Zwischenprüfung und habe mir vorgenommen, wirklich den Großteil zu verstehen, vorallem möchte ich ganz am Anfang mit allem mitkommen, damit das später dann nicht unnötig kompliziert wird.
Also ich komme mit meinem Induktionsbeweis zur Potenzmenge nicht weiter:
Also für n=0 und n=1 ist das kein Problem
Nun kommt der Induktionsschritt: Wenn die obige Aussage für alle n gilt, dann auch für n+1
A={1,2,....,n,n+1} Dann enthält die Potenzmenge ja die folgenden Elemente: [mm] \mathcal{P} (A)=\{\emptyset, \{1\}, \{1,2\},...,\{1,...,n\},\{1,...,n+1\},\{2\},\{2,3\},...,\{2,...,n+1\}...\}
[/mm]
Und sogeht das weiter bis nur noch {n+1} da steht.
Aber wieviele Elemente sind das nun. Es müssen [mm] 2^{n+1} [/mm] sein, aber wie sehe ich das?
Danke für eure Hilfe!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Ist A eine Menge mit n Elementen, so enthält die
> Potenzmenge [mm]\mathcal{P}[/mm] (A) [mm]2^{n}[/mm] Elemente
> Hallo...
> Ich lerne auf meine Zwischenprüfung und habe mir
> vorgenommen, wirklich den Großteil zu verstehen, vorallem
> möchte ich ganz am Anfang mit allem mitkommen, damit das
> später dann nicht unnötig kompliziert wird.
> Also ich komme mit meinem Induktionsbeweis zur Potenzmenge
> nicht weiter:
> Also für n=0 und n=1 ist das kein Problem
> Nun kommt der Induktionsschritt: Wenn die obige Aussage
> für alle n gilt, dann auch für n+1
> A={1,2,....,n,n+1} Dann enthält die Potenzmenge ja die
> folgenden Elemente: [mm]\mathcal{P} (A)=\{\emptyset, \{1\}, \{1,2\},...,\{1,...,n\},\{1,...,n+1\},\{2\},\{2,3\},...,\{2,...,n+1\}...\}[/mm]
>
> Und sogeht das weiter bis nur noch {n+1} da steht.
> Aber wieviele Elemente sind das nun. Es müssen [mm]2^{n+1}[/mm]
> sein, aber wie sehe ich das?
Die Potenzmenge [mm] $\{1,\ldots, n, n+1\}$ [/mm] enthält einerseits die (nach Induktionsvoraussetzung) [mm] $2^n$ [/mm] Mengen, die schon in der Potenzmenge von [mm] $\{1,\ldots, n\}$ [/mm] enthalten sind, und dann noch die ebenfalls [mm] $2^n$ [/mm] Mengen, die sich aus der Vereinigung einer der [mm] $2^n$ [/mm] Teilmengen von [mm] $\{1,\ldots, n\}$ [/mm] mit der Menge [mm] $\{n+1\}$ [/mm] ergeben. Macht insgesamt [mm] $2^n+2^n=2\cdot 2^n=2^{n+1}$.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:53 Mo 04.08.2008 | | Autor: | Plapper |
Die Potenzmenge [mm] $\{1,\ldots, n, n+1\}$ [/mm] enthält einerseits die (nach Induktionsvoraussetzung) [mm] $2^n$ [/mm] Mengen, die schon in der Potenzmenge von [mm] $\{1,\ldots, n\}$ [/mm] enthalten sind,
Ja, das versteh ich, das ist mir klar.
und dann noch die ebenfalls [mm] $2^n$ [/mm] Mengen, die sich aus der Vereinigung einer der [mm] $2^n$ [/mm] Teilmengen von [mm] $\{1,\ldots, n\}$ [/mm] mit der Menge [mm] $\{n+1\}$ [/mm] ergeben.
Da die Vereinigung eine neue Menge ist, hat die Potenzmenge auch wieder [mm] 2^{n} [/mm] Elemente. Stimmt die Überlegung?
Macht insgesamt [mm] $2^n+2^n=2\cdot 2^n=2^{n+1}$. [/mm]
Dann ist der Schritt auch klar!
Vielen Dank!
|
|
|
| |
|
> Die Potenzmenge [mm]\{1,\ldots, n, n+1\}[/mm] enthält einerseits die
> (nach Induktionsvoraussetzung) [mm]2^n[/mm] Mengen, die schon in der
> Potenzmenge von [mm]\{1,\ldots, n\}[/mm] enthalten sind,
>
> Ja, das versteh ich, das ist mir klar.
>
> und dann noch die ebenfalls [mm]2^n[/mm] Mengen, die sich aus der
> Vereinigung einer der [mm]2^n[/mm] Teilmengen von [mm]\{1,\ldots, n\}[/mm]
> mit der Menge [mm]\{n+1\}[/mm] ergeben.
>
> Da die Vereinigung eine neue Menge ist, hat die Potenzmenge
> auch wieder [mm]2^{n}[/mm] Elemente.
Moment: es ist nicht klar von welcher Potenzmenge Du hier sprichts. Die Anzahl der Mengen, die beim Übergang von der Potenzmenge von [mm] $\{1,\ldots, n\}$ [/mm] zur Potenzmenge von [mm] $\{1,\ldots, n,n+1\}$ [/mm] neu hinzukommen, ist [mm] $2^n$: [/mm] eben weil man zu jeder Menge aus der Potenzmenge von [mm] $\{1,\ldots, n\}$ [/mm] durch Hinzufügen von $n+1$ jedenfalls eine neue Menge erhält, die nicht schon in der Potenzmenge von [mm] $\{1,\ldots, n\}$ [/mm] enthalten war.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:21 Mo 04.08.2008 | | Autor: | Plapper |
Mmh, also das ist komisch, heißt das jetzt, dass durch den Übergang zur Potenzmenge von [mm] \{1,...,n+1\} [/mm] eine neue Menge entsteht mit ihrerseits wieder [mm] 2^{n} [/mm] Elementen. Also hab ich eine Menge [mm] A'=\{1,2,....,n+1\} [/mm] und deren Potenzmenge setzt sich aus der Potenzmenge von [mm] A=\{1,....,n\} [/mm] und der Potenzmenge von A'zusammen, also hat die Potenzmenge von A' zweimal [mm] 2^{n} [/mm] Elemente: [mm] 2*2^{n}=...=2^{n+1}.
[/mm]
Stimmt das so?
|
|
|
| |
|
> Mmh, also das ist komisch, heißt das jetzt, dass durch den
> Übergang zur Potenzmenge von [mm]\{1,...,n+1\}[/mm] eine neue Menge
> entsteht mit ihrerseits wieder [mm]2^{n}[/mm] Elementen.
![[notok]](/images/smileys/notok.gif "[notok]") Eben nicht. Du sollst ja gerade beweisen, dass diese Potenzmenge [mm] $2^{n+1}$ [/mm] Elemente besitzt.
> Also hab
> ich eine Menge [mm]A'=\{1,2,....,n+1\}[/mm] und deren Potenzmenge
> setzt sich aus der Potenzmenge von [mm]A=\{1,....,n\}[/mm] und der
> Potenzmenge von A'zusammen,
Dies ist zwar richtig, einfach weil ja die Potenzmenge von $A'$ die Potenzmenge von $A' := [mm] \{1,\ldots,n,n+1\}$ [/mm] ist. So hast Du $A'$ ja soeben definiert: aber es bringt Dir nichts, denn weil die Potenzmenge von $A'$ die Potenzmenge von $A$ einfach enthält, ist deren Vereinigung natürlich die grössere Menge.
> also hat die Potenzmenge von A'
> zweimal [mm]2^{n}[/mm] Elemente: [mm]2*2^{n}=...=2^{n+1}.[/mm]
Nochmal: wir wollen die Teilmengen von $A' := [mm] \{1,\ldots,n,n+1\}$ [/mm] zählen. Dies erledigen wir in zwei Schritten. Sei [mm] $X'\subseteq [/mm] A'$, falls [mm] $n+1\notin [/mm] X'$ ist, ist $X'$ sogar eine Teilmenge von $A := [mm] \{1,\ldots,n\}$. [/mm] Falls aber [mm] $n+1\in [/mm] X'$ ist, ist [mm] $X'\backslash \{n+1\}$ [/mm] ebenfalls eine Teilmenge von $A$ (und zwar eine eindeutig bestimmte). Daher besteht also die Potenzmenge von $A'$ aus zwei disjunkten Teilmengen von Mengen: den Mengen, die Teilmengen von $A$ sind (davon gibt es nach Induktionsvoraussetzung [mm] $2^n$ [/mm] Stück), und Mengen, die Teilmengen von $A'$ sind und die durch Hinzufügen von $n+1$ aus einer eindeutig bestimmten Teilmenge von $A$ entstehen (davon gibt es nochmals [mm] $2^n$ [/mm] Stück). Also hat $A'$ insgesamt doppelt so viele Elemente wie $A$.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:59 Mo 04.08.2008 | | Autor: | Plapper |
> Nochmal: wir wollen die Teilmengen von [mm]A' := \{1,\ldots,n,n+1\}[/mm]
> zählen. Dies erledigen wir in zwei Schritten.
ok.
> Sei
> [mm]X'\subseteq A'[/mm], falls [mm]n+1\notin X'[/mm] ist, ist [mm]X'[/mm] sogar eine
> Teilmenge von [mm]A := \{1,\ldots,n\}[/mm].
Okay, das hab ich verstanden.
> Falls aber [mm]n+1\in X'[/mm]
> ist, ist [mm]X'\backslash \{n+1\}[/mm] ebenfalls eine Teilmenge von
> [mm]A[/mm] (und zwar eine eindeutig bestimmte).
Das ist mir auch klar.
> Daher besteht also
> die Potenzmenge von [mm]A'[/mm] aus zwei disjunkten Teilmengen von
> Mengen: den Mengen, die Teilmengen von [mm]A[/mm] sind (davon gibt
> es nach Induktionsvoraussetzung [mm]2^n[/mm] Stück)
das ist das X'
> , und Mengen, die
> Teilmengen von [mm]A'[/mm] sind und die durch Hinzufügen von [mm]>n+1[/mm] aus
> einer eindeutig bestimmten Teilmenge von [mm]A[/mm] entstehen
Das ist ja die Menge X' [mm] \setminus\{n+1\}, [/mm] die durch das Hinzufügen von {n+1} zu einer neuen Menge wird, die wiederrum [mm] 2^{n} [/mm] Elemente besitzt
> (davon
> gibt es nochmals [mm]2^n[/mm] Stück). Also hat [mm]A'[/mm] insgesamt doppelt
> so viele Elemente wie [mm]A[/mm].
Ich hoffe, nun hab ich es...
|
|
|
| |
|
> > Nochmal: wir wollen die Teilmengen von [mm]A' := \{1,\ldots,n,n+1\}[/mm]
> > zählen. Dies erledigen wir in zwei Schritten.
> ok.
> > Sei
> > [mm]X'\subseteq A'[/mm], falls [mm]n+1\notin X'[/mm] ist, ist [mm]X'[/mm] sogar eine
> > Teilmenge von [mm]A := \{1,\ldots,n\}[/mm].
> Okay, das hab ich
> verstanden.
> > Falls aber [mm]n+1\in X'[/mm]
> > ist, ist [mm]X'\backslash \{n+1\}[/mm] ebenfalls eine Teilmenge von
> > [mm]A[/mm] (und zwar eine eindeutig bestimmte).
> Das ist mir auch klar.
> > Daher besteht also
> > die Potenzmenge von [mm]A'[/mm] aus zwei disjunkten Teilmengen von
> > Mengen: den Mengen, die Teilmengen von [mm]A[/mm] sind (davon gibt
> > es nach Induktionsvoraussetzung [mm]2^n[/mm] Stück)
> das ist das X'
> > , und Mengen, die
> > Teilmengen von [mm]A'[/mm] sind und die durch Hinzufügen von [mm]>n+1[/mm]
> aus
> > einer eindeutig bestimmten Teilmenge von [mm]A[/mm] entstehen
> Das ist ja die Menge X' [mm]\setminus\{n+1\},[/mm] die durch das
> Hinzufügen von {n+1} zu einer neuen Menge wird, die
> wiederrum [mm]2^{n}[/mm] Elemente besitzt
Hallo,
ich bin mir nicht so sicher, ob Du's hast.
X' ist hier keine Menge von Mengen, sondern das X', über welches hier geredet wird, ist einfach irgendeine Teilmenge von A', und eine Teilmenge von A' hat zwei Möglichkeiten: entweder enthält sie n+1, oder sie enthält n+1 nicht.
Also kann man die Potenzmenge von A' in zwei disjunkte Mengen von Teilmengen von A' aufteilen: in die, die die Teilmengen ohne n+1 enthält, und in die, die die Teilngen mit n+1 enthält.
Jetzt nimmt man sich die Menge P der Teilmengen von A' vor, die n+1 nicht enthalten. Das ist ja gerade die Potenzmenge von A, welche nach Induktionsvoraussetzung [mm] 2^n [/mm] Elemente hat.
Wenn man jedes der Elemente von P mit [mm] \{n+1\} [/mm] vereinigt, so ist die entstehende Menge P' von Teilmengen von A' gerade die Menge der Teilmengen von A', die n+1 enthalten, und es ist unmittelbar einzusehen, daß P' auch [mm] 2^n [/mm] Elemente enthält. Also enthält die Potenzmenge von A' [mm] 2^n+2^n [/mm] Elemente.
Da Du Dich in einem Wirrwarr verstrickt haben zu scheinst, ein Beispiel:
[mm] A':=\{1,2,3\} [/mm] , [mm] A:=\{1,2\}
[/mm]
Die Potenzmenge von A ist [mm] P_A=\{ \emptyset, \{1\}, \{2\}, A\}.
[/mm]
Es ist [mm] P:=P_A [/mm] die Teilmenge der Potenzmenge [mm] P_{A'} [/mm] von A', welche sämtliche Teilmengen von A' enthält, die die 3 nicht enthalten.
Die Menge P' sei die Menge, die entsteht, wenn man jedes Element aus P mit [mm] \{3\} [/mm] vereinigt. Also ist
[mm] P'=\{\{3\}, \{1,3\}, \{2,3\}, A'\}.
[/mm]
P und P' enthalten beide [mm] 2^2 [/mm] Elemente, und die Vereinigung dieser beiden disjunkten Mengen ist die Potenzmenge von A', [mm] P_{A'}=\{ \emptyset, \{1\}, \{2\},\{3\}, A, \{1,3\}, \{2,3\}, A'\}.
[/mm]
Gruß v. Angela
>
|
|
|
| |
|
Es ginge auch ohne Induktionsbeweis.
Hat die ursprüngliche Menge A n Elemente, dann kann
man jede Teilmenge T von A durch eine n-stellige Binärzahl
codieren. An der k-ten Stelle dieser Binärzahl stehe eine 1,
wenn [mm] k\in [/mm] T , und eine 0, wenn [mm] k\not \in [/mm] T ist.
Die Anzahl der Teilmengen von A ist gleich der Anzahl der
n-stelligen Binärzahlen (an jeder der n Stellen entweder eine
0 oder eine 1 ). Die Anzahl solcher Binärzahlen ist natürlich
gleich [mm] 2^n.
[/mm]
LG al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Di 05.08.2008 | | Autor: | Plapper |
Hallo Angela,
jetzt hab ichs komplett, vielen Dank für die liebe Erklärung... Das mit der Vereinigung war mir immer noch bissl wirre, aber nun hab ich es!!!
Danke, lg Plapper
@Al Chwarizmi: Danke für deinen alternativen Beweis. Aber ich denke, mit der Induktion bin ich völlig zufrieden!!! Danke dir trotzdem!!!
Lg, Plapper
|
|
|
|
