Potenzmenge, Bijektionen < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:08 So 28.10.2007 | | Autor: | Mirtschi |
Hallo!
Ich muss folgende Aufgabe lösen und habe leider überhaupt keinen Plan, wie ich damit anfangen soll:
Es sei M eine Menge mit [mm] n\in\IN [/mm] vielen Elementen. Zeigen Sie:
(I) [mm] \beta(M) [/mm] hat [mm] 2^n [/mm] Elemente.
(II) Es gibt genau n! Bijektionen f: M [mm] \rightarrow [/mm] M.
Zu (I) habe ich mir überlegt, dass ich zeigen soll, dass die Abbildung von M [mm] \rightarrow \beta(M) [/mm] ist und damit gilt n [mm] \rightarrow 2^n. [/mm] Stimmt das? Und wie geht man so einen Beweis an?
Viele Grüße
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:23 So 28.10.2007 | | Autor: | max3000 |
Hallo.
Zur 1. Aufgabe:
[mm] |\beta(M)|=2^{n}
[/mm]
|.| sind die Anzahl der Elemente einer Menge (Mächtigkeit nennt man das glaub ich).
Diesen Beweis machst du mit Induktion:
Anfang: M hat 1 Element (x), also ist [mm] \beta(M)=\{\emptyset,\{x\}\}
[/mm]
Also 2 Elemente, die Gleichung ist erfüllt.
Vorraussetzung: [mm] |M|=n\Rightarrow|\beta(M)|=2^{n}
[/mm]
Das ist klar.
Induktionsschritt:
Kommt noch ein Element (y) dazu, also [mm] n\rightarrow [/mm] n+1,
dann gibt es [mm] 2^{n} [/mm] Mengen, wo y nicht vorkommt und dazu kommen jetzt noch die Kombinationen mit y.
Das solltest du jetzt selbst herausfinden, wie man dann auf [mm] 2^{n+1} [/mm] kommt. Offenbar musst du also zeigen, dass es nochmal [mm] 2^{n} [/mm] Mengen in [mm] \beta(M) [/mm] gibt, wo y mit enthalten ist.
Ich hoffe das hilft dir erstmal weiter.
Wenn du noch Hilfe brauchst frag einfach nochmal nach.
Aufgabe II dürfte eigentlich ziemlich ähnlich sein, also auch mit Induktion.
Grüße
Max
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:38 So 28.10.2007 | | Autor: | Mirtschi |
Hallo!
Ehrlich gesagt, verstehe ich deine Antwort nicht so ganz. Ich habe es doch mit einer Abbildung zu tun, oder? Das Bild der Abbildung hat [mm] 2^n [/mm] Elemente und die Urmenge n Elemente.
Wenn ich das jetzt über vollständige Induktion beweisen soll, ist mir die Induktionsvoraussetzung klar. Ich setze die Urmenge = 1 und habe somit eine Abbildung mit 2 Elementen. Das bedeutet ich habe eine Menge mit n Elementen und eine Abbildung der Menge mit [mm] 2^n [/mm] Elementen. Wenn das ganze auch für n+1 gelten soll, habe ich eine Menge mit n+1 Elementen und eine Abbildung mit [mm] 2^{n+1} [/mm] Elementen.
Ich versuche das einmal aufzuschreiben.
Mein A(n) = [mm] 2^n
[/mm]
Wenn A(n) gilt, soll auch A(n+1) gelten.
Das wäre: A(n+1) = [mm] 2^{n+1} [/mm] = [mm] 2*2^n [/mm] = 2*A(n)
Damit habe ich doch dann gezeigt, dass ich für ein zusätzliches Element in der Urbildmenge die doppelte Bildmenge bekomme, oder nicht? Das ist aber doch nicht das, was ich beweisen soll. Oder bin ich auf der falschen Fährte?
Viele Grüße
|
|
|
| |
|
> Ehrlich gesagt, verstehe ich deine Antwort nicht so ganz.
> Ich habe es doch mit einer Abbildung zu tun, oder?
Hallo,
ich fürchte, Du hast Deine Aufgabe überhaupt nicht verstanden.
Du schreibst es zwar nirgendwo, aber aufgrund der Überschrift und einer gewissen Lebenserfahrung komme ich zu dem Schluß, daß mit [mm] \beta [/mm] (M) die Potenzmenge von M gemeint ist.
Du sollst nun zeigen, daß wenn M n-elemntig ist, die Potenzmenge [mm] 2^n [/mm] Elemente hat.
Wie man das per Induktion machen kann, hat Dir max3000 erklärt.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:41 So 28.10.2007 | | Autor: | froggie |
Zu dieser Ausgabe habe ich folgenden beweis gefunden:
Beh.: Sei A eine Menge mit |A| = n. Dann gilt |P(A)| = [mm] 2^n. [/mm]
Beweis: Induktion über die Anzahl der Elemente. Für |A| = 0 gilt A = {} und |P(A)| = |{{}}| = 1 = [mm] 2^0. [/mm] Gelte Die Aussage für ein 0 < n in lN. Betrachte für den Fall n+1 eine Menge A mit |A| = n+1. Dann ist die Menge nicht leer und es gibt ein Element a in A. Sei M = P(A \ {a}) mit |M| = [mm] 2^n [/mm] nach Induktionsannahme. Dann ist nach dem Bildungsgesetz für Potenzmengen für endliche Mengen
P(A) = M [mm] \cup [/mm] { S [mm] \cup [/mm] {a} | S in M }.
Es gilt somit, da die beiden obigen Mengen in der Vereinigung disjunkt sind, |P(A)| = |M| + | { S \ {a} | S in M}| = [mm] 2^n [/mm] + [mm] 2^n [/mm] = 2^(n+1). qed
Mir ist alles klar bis auf warum | { S \ {a} | S in M}| = [mm] 2^n
[/mm]
Kann mir da jemand helfen?
|
|
|
| |
|
Hallo,
dieser Beweis ist ja genau der, für den max3000 die Anleitung geliefert hat.
> Mir ist alles klar bis auf warum | { S \ {a} | S in M}| =
> [mm]2^n[/mm]
Ich vermute mal, daß da eigentlich { S [mm] \cup [/mm] {a} | S in M} stehen sollte - für die Anzahl der Eelemnte dieser Menge ist's allerdings egal:
M ist die Potenzmenge von A \ [mm] \{a\}, [/mm] enthält also [mm] 2^n [/mm] Elemente, welche a nicht enthalten. Diese [mm] 2^n [/mm] Elemente werden nun jeweils mit [mm] \{a\} [/mm] vereinigt.
(Da a in diesem Mengen S nicht drin ist, kann man {a} ebensogut abziehen, an der Anzahl der Mengen in der Menge ändert sich nichts.)
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:19 Mo 29.10.2007 | | Autor: | froggie |
MERCI BEAUCOUP!!! Wenn da anstelle von \ ein [mm] \cup [/mm] steht verstehe ichs!!! :)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:37 Mo 29.10.2007 | | Autor: | froggie |
wie gehts man denn aufgabe 2 an?
IA: M1 hat eine Bijektion, nämlcih [mm] 1\to [/mm] 1
1!=1
Wie sieht denn der induktionsschritt ausbzw die induktionsvorraussetzung?
Irgendwelche ansatzvorschläge?
|
|
|
| |
|
> wie gehts man denn aufgabe 2 an?
>
> IA: M1 hat eine Bijektion, nämlcih [mm]1\to[/mm] 1
> 1!=1
>
> Wie sieht denn der induktionsschritt ausbzw die
> induktionsvorraussetzung?
> Irgendwelche ansatzvorschläge?
Hallo,
wichtig ist zunächst - vor dem Rechnen - daß Du die Aussage verstehst.
Weißt Du, warum es hier n! Bijektionen gibt?
Könntest Du das Deinem kleinen Bruder erklären - falls Du einen hättest?
Falls Du noch nicht soweit bist, kannst Du ja erstmal alle Bijektionen für 2-und 3- , eventuell sogar 4-elementige Mengen aufschreiben.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:38 Mo 29.10.2007 | | Autor: | froggie |
bijektiv heißt doch
hab zwar keinen kleinen bruder, aber dafür einen großen :)
....
wenn für alle y aus Y GENAU EIN x aus X mit f(x)=y existiert oder?
hieße das dann nicht
~ ein element: 1 bijektion
~ 2 elemente : 2 bijektionen
~ 3 elemente: 3 bijektionen (ich hab 3 elemente in der bildmenge und 3 in der Urbildmenge.... ist mit der anzahl der Bijektionen dann die Anzhal der möglichen Kombinationen gemeint, mit der ich die element aus bild und urbildmenge verbinden kann?
|
|
|
| |
|
> bijektiv heißt doch
> hab zwar keinen kleinen bruder, aber dafür einen großen :)
> ....
> wenn für alle y aus Y GENAU EIN x aus X mit f(x)=y
> existiert oder?
Hallo,
ja, so ist das.
>
> ist mit der anzahl
> der Bijektionen dann die Anzhal der möglichen
> Kombinationen gemeint, mit der ich die element aus bild und
> urbildmenge verbinden kann?
Wenn ich Dich richtig verstehe: ja.
Nehmen wir [mm] A_2:={a,b\} [/mm] und schauen, welche Bijektionen auf A es gibt:
Es sind nur zwei [mm] f_1 [/mm] und [mm] f_2 [/mm] mit:
[mm] f_1(a):=a f_2(a)=b
[/mm]
[mm] f_1(b):=b f_2(b)=a.
[/mm]
Überlege Dir, wie Du Dir und anderen (gr. Bruder) erklären kannst, daß es für n=3 3! Bijektionen gibt und für n=4 4!.
Gruß v. Angela
|
|
|
|
