Bijektion zw. Potenzmengen < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:28 Sa 31.10.2009 | | Autor: | etoxxl |
| Aufgabe | Seien n,m natürliche Zahlen mit der Eigenschaft m [mm] \le [/mm] n. Die Anzahl
[mm] \vektor{n \\ m} [/mm] := | [mm] \mathcal{P}m(\{ 1,...,n \}) [/mm] |
Zeigen Sie, dass
[mm] \vektor{n \\ m} [/mm] = [mm] \vektor{n \\ n-m}
[/mm]
gilt indem Sie eine Bijektion zwischen [mm] \mathcal{P}m(\{ 1,...,n \}) [/mm] und [mm] \mathcal{P}n-m(\{ 1,...,n \}) [/mm] angeben. |
Ich habe eine Lösung gefunden, verstehe aber einen Schritt nicht.
Die Lösung:
Die Abbildungen, die jeder Teilmenge A einer n-elementigen Menge M ihr Komplement M-A im M zuordnet, ist eine Bijektion von der Potenmenge vom M auf die Potenzmenge von M. Dabei werden die k-elementigen Teilmengen von M genau auf die (n-k)- elementigen Teilmengen von M abgebildet.
Also gibt es von beiden Sorten Teilmengen gleich viele, und es folgt: [mm] \vektor{n \\ m} [/mm] = [mm] \vektor{n \\ n-m}
[/mm]
Mit der Aussage:
"Dabei werden die k-elementigen Teilmengen von M genau auf die (n-k)- elementigen Teilmengen von M abgebildet."
setzt man ja voraus, dass es genau so viele k-elementige Teilmengen von M gibt wie (n-k)-elementigen Teilmengen von M, obwohl man das ja eben beweisen will.
Und mit der Aussage:
"Also gibt es von beiden Sorten Teilmengen gleich viele"
wird dann aus der unbegründeten Annahme der Beweis.
Ist diese Lösung falsch, bzw wie kann man die Aufgabe besser lösen?
#Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:31 Sa 31.10.2009 | | Autor: | pelzig |
> Ist diese Lösung falsch, bzw wie kann man die Aufgabe besser lösen?
Indem man es etwas formaler aufschreibt und die Behauptung rigoros beweist. Wenn man zeigen will, dass zwei Mengen gleich viele Elemente haben muss man eine Bijektion zwischen ihnen finden. Nun hast du die Abbildung [mm] $$\Phi:\mathcal{P}_m(\{1,2,...,n\})\ni A\mapsto A^c\in\mathcal{P}_{n-m}(\{1,...,n\}).$$ [/mm] Nun musst du zeigen, dass [mm] $\Phi$ [/mm] wohldefiniert ist (d.h. hier: das Komplement einer m-elementigen Teilmenge ist (n-m)-elementig) und dass [mm] $\Phi$ [/mm] bijektiv ist, d.h. injektiv und surjektiv.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:51 Sa 31.10.2009 | | Autor: | etoxxl |
Ich überlege die ganze Zeit, wie ich das allgemeingültig für alle n und k zeigen kann, aber selbst in einem Beispiel für die Menge {1,2,3,4,5} und k=2
sehe ich keine Bijektion:
Ich bilde jetzt die k=2 -elementigen Mengen auf die n-k = 5-2 = 3 - elementigen Mengen ab:
1: (1,2) -> (1,2,3)
2: (1,3) -> (1,3,4)
3: (1,4) -> (1,4,5)
4: (1,5) -> (1,2,5)
5: (2,3) -> (2,3,4)
6: (2,4) -> (2,4,5)
7: (2,5) -> (2,3,5)
8: (3,4) -> (3,4,5)
9: (3,5) -> (1,3,5)
10:(4,5) -> (1,2,4)
Aber ich könnte die Reihenfolge ganz verändern und bei einer Bijektion muss
z.B für die Teilmenge (1,2,4) eindeutig klar sein, welche Menge die Uhrmenge ist.
Könnte mir jemand explizit zeigen, wie man zeigt, dass
$ [mm] \Phi:\mathcal{P}_m(\{1,2,...,n\})\ni A\mapsto A^c\in\mathcal{P}_{n-m}(\{1,...,n\}). [/mm] $
wohldefiniert ist und dass $ [mm] $\Phi$ [/mm] $ bijektiv ist?
|
|
|
| |
|
> Ich überlege die ganze Zeit, wie ich das allgemeingültig
> für alle n und k zeigen kann, aber selbst in einem
> Beispiel für die Menge {1,2,3,4,5} und k=2
> sehe ich keine Bijektion:
>
> Ich bilde jetzt die k=2 -elementigen Mengen auf die n-k =
> 5-2 = 3 - elementigen Mengen ab:
>
> 1: (1,2) -> (1,2,3)
> 2: (1,3) -> (1,3,4)
> 3: (1,4) -> (1,4,5)
> 4: (1,5) -> (1,2,5)
> 5: (2,3) -> (2,3,4)
> 6: (2,4) -> (2,4,5)
> 7: (2,5) -> (2,3,5)
> 8: (3,4) -> (3,4,5)
> 9: (3,5) -> (1,3,5)
> 10:(4,5) -> (1,2,4)
![[haee]](/images/smileys/haee.gif "[haee]") ![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]")
Weshalb machst du es nicht so, wie du es vorher
beschrieben hast ?
Jeder Menge soll ihre Komplementärmenge zu-
geordnet werden, also z.B.
1: (1,2) -> (3,4,5)
7: (2,5) -> (1,3,4)
>
> Aber ich könnte die Reihenfolge ganz verändern und bei
> einer Bijektion muss
> z.B für die Teilmenge (1,2,4) eindeutig klar sein, welche
> Menge die Uhrmenge ist.
Die Menge aller anderen Elemente, also (3,5) !
> Könnte mir jemand explizit zeigen, wie man zeigt, dass
> [mm]\Phi:\mathcal{P}_m(\{1,2,...,n\})\ni A\mapsto A^c\in\mathcal{P}_{n-m}(\{1,...,n\}).[/mm]
>
> wohldefiniert ist und dass[mm][/mm][mm] \Phi[/mm][mm][/mm] bijektiv ist?
Es sei [mm] N:=\{1,2,...,n\} [/mm] und [mm] A\in\mathcal{P}_m(N)
[/mm]
Dann ist das Komplement [mm] A^c=\{x\in N:\ x\notin A\} [/mm] eine
eindeutig definierte Teilmenge von N mit genau
n-m Elementen, also ein Element von [mm] \mathcal{P}_{n-m}(N) [/mm] .
Um die Injektivität zu zeigen, muss man nachweisen:
Wenn [mm] A^c=B^c, [/mm] dann ist A=B.
Für die Surjektivität ist zu zeigen, dass jedes
[mm] T\in \mathcal{P}_{n-m}(N) [/mm] Komplement einer Teilmenge [mm] U\in\mathcal{P}_m(N) [/mm] ist,
also [mm] T=U^c [/mm] mit einem [mm] U\in\mathcal{P}_m(N). [/mm]
Diese Beweise zu notieren sollte nicht schwer sein.
LG Al-Chw.
|
|
|
|
