Bijektivität zeigen < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Für zwei Mengen X ,Y sei Abb (X ,Y) die Menge aller Abbildungen von X nach Y.
Außerdem sei
[mm]\mathcal{P}(X) := \{A | A \subset X\}[/mm]
die Potenzmenge von X.
Beweisen Sie, dass die Zuordnung
[mm] \begin{matrix}
Abb(X,\{0,1\}) &\to& \mathcal{P}(X)\\
\phi &\mapsto& \phi^{-1}(\{1\})
\end{matrix}
[/mm]
eine bijektive Abbildung ist.
|
Kann mir hierfür jemand eine möglichst allgemeine Vorgehensweise aufzeigen? Den Stoff über Abbildungen habe ich bereits (wenn auch ein wenig lückenhaft) nachgelernt und ich komme aus dem Stehgreif z.B. darauf, dass zu zeigen wäre, dass
[mm](1)\ x_{1}\ \not=\ x_{2} \Rightarrow f(x_{1}) \not= f(x_{2})[/mm]
und
[mm](2)\ \forall\ y \in\ \mathcal{P}(X)\ \exists\ x \in X\ :\ f(x) = y[/mm]
Bitte seid so lieb und sagt mir jeden noch so kleinen Fehler in dieser Schreibweise. Ich bin mir absolut sicher, dass es derer haufenweise gibt. ^^
|
|
| |
|
> Für zwei Mengen X ,Y sei Abb (X ,Y) die Menge aller
> Abbildungen von X nach Y.
>
> Außerdem sei
> [mm]\mathcal{P}(X) := \{A | A \subset X\}[/mm]
> die Potenzmenge
> von X.
>
> Beweisen Sie, dass die Zuordnung
> [mm]\begin{matrix}
Abb(X,\{0,1\}) &\to& \mathcal{P}(X)\\
\phi &\mapsto& \phi^{-1}(\{1\})
\end{matrix}[/mm]
>
> eine bijektive Abbildung ist.
>
> Kann mir hierfür jemand eine möglichst allgemeine
> Vorgehensweise aufzeigen? Den Stoff über Abbildungen habe
> ich bereits (wenn auch ein wenig lückenhaft) nachgelernt
> und ich komme aus dem Stehgreif z.B. darauf, dass zu zeigen
> wäre, dass
>
> [mm](1)\ x_{1}\ \not=\ x_{2} \Rightarrow f(x_{1}) \not= f(x_{2})[/mm]
>
> und
> [mm](2)\ \forall\ y \in\ \mathcal{P}(X)\ \exists\ x \in X\ :\ f(x) = y[/mm]
Hallo,
das ist noch nicht richtig.
Du hast dort eine Abbildung, welche in der Aufgabenstellung noch keinen Namen bekommen hatte. Ich nenne sie jetzt f.
Diese Abbildung ordnet jeder in [mm] Abb(X,\{0,1\}) [/mm] enthaltenen Abbildung [mm] \Phi [/mm] die Menge der Elemente zu , welche durch [mm] \Phi [/mm] auf die 1 abgebildet werden.
Also:
f: [mm] Abb(X,\{0,1\}) &\to& \mathcal{P}(X) [/mm] mit
[mm] f(\phi):=\phi^{-1}(\{1\}) [/mm] für alle [mm] \phi \in Abb(X,\{0,1\}).
[/mm]
Mach Dir das in Ruhe klar, und formuliere dann das zu Zeigende neu.
Gruß v. Angela
|
|
|
| |
|
> Hallo,
>
> das ist noch nicht richtig.
>
> Du hast dort eine Abbildung, welche in der Aufgabenstellung
> noch keinen Namen bekommen hatte. Ich nenne sie jetzt f.
>
> Diese Abbildung ordnet jeder in [mm]Abb(X,\{0,1\})[/mm] enthaltenen
> Abbildung [mm]\Phi[/mm] die Menge der Elemente zu , welche durch
> [mm]\Phi[/mm] auf die 1 abgebildet werden.
>
> Also:
>
> f: [mm]Abb(X,\{0,1\}) &\to& \mathcal{P}(X)[/mm] mit
>
> [mm]f(\phi):=\phi^{-1}(\{1\})[/mm] für alle [mm]\phi \in Abb(X,\{0,1\}).[/mm]
>
> Mach Dir das in Ruhe klar, und formuliere dann das zu
> Zeigende neu.
>
> Gruß v. Angela
Also in meinen eigenen Worten ausgedrückt würde ich jetzt sagen:
Wir haben für unsere Abbildung f eine Definitionsmenge Abb(X, [mm] \{0,1\}) [/mm] und eine Zielmenge [mm] \mathcal{P}(X). [/mm]
Die Definitionsmenge enthält nun Abbildungen [mm] $\phi_{1}, \phi_{2}, \ldots [/mm] , [mm] \phi_{n}$. [/mm] In der Zielmenge haben wir sozusagen Mengen aus den Mengen aller Zahlen, da X ja nicht in einem bestimmten Bereich definiert ist. (Das ist unerheblich, vermute ich, aber der Vollständigkeit halber erwähne ich es. ^^)
Dann definieren wir unsere Abbildung f so, dass wir sagen [mm] f(\phi) [/mm] "zeigt" auf das Urbild der Menge [mm] \{1\}. [/mm] Da [mm] \phi [/mm] wiederum eine Abbildung ist haben wir eine Komposition, richtig?
Wäre also folgendes zu zeigen, damit die Bijektivität gegeben ist?
$ (1)\ [mm] \phi_{1}\ \not=\ \phi_{2} \Rightarrow f(\phi_{1}) \not= f(\phi_{2}) [/mm] $
$ (2)\ [mm] \phi^{-1}(\{1\}) \in Abb(X,\{0,1\}) [/mm] $
Wenn nein, wird's zumindest "wärmer"? *g*
(EDIT)
Ich habe mir jetzt zusammen mit einem Kommilitonen einige Gedanken dazu gemacht und wir glauben, dass wir zumindest die Injektivität zeigen können.
[mm]f(\phi_{1}) = \phi^{-1}(\{1\}) = f(\phi_{2})[/mm]
[mm]\Rightarrow \phi_{1} = \phi_{2}[/mm]
[mm]\Rightarrow\ f\ ist\ injektiv[/mm]
Könnt ihr das bestätigen?
Bezgl. Surjektivität sind wir jedoch noch immer ratlos. Wir bitten dringend um Hilfe. ^^
Danke im Voraus
~LG W
|
|
|
| |
|
> Also in meinen eigenen Worten ausgedrückt würde ich jetzt
> sagen:
> Wir haben für unsere Abbildung f eine Definitionsmenge
> Abb(X, [mm] \{0,1\})
[/mm]
Hallo,
richtig.
> und eine Zielmenge [mm] \mathcal{P}(X).
[/mm]
Genau.
>
> Die Definitionsmenge enthält nun Abbildungen [mm] \phi_{1}, \phi_{2},..., \phi_{n}.
[/mm]
Naja, daß es nur endlich viele oder abzählbar viele Abbildungen sind, ist nicht gesagt. Wenn z.B. [mm] X=\IR [/mm] wäre, hätte man sehr, sehr viele Abbildungen.
Sagen wir einfach: die Definitionsmenge enthält Abbildungen.
> In der Zielmenge haben wir sozusagen Mengen aus den Mengen
> aller Zahlen, da X ja nicht in einem bestimmten Bereich
> definiert ist. (Das ist unerheblich, vermute ich, aber der
> Vollständigkeit halber erwähne ich es. ^^)
Das müssen ja noch nichtmal Zahlen sein. X könnte ja auch aus Farben, Buchstaben oder Tieren bestehen.
Jedenfalls sind die Elemente der Zielmenge Mengen aus den Objekten, die in X sind.
>
> Dann definieren wir unsere Abbildung f so, dass wir sagen
> [mm] f(\phi) [/mm] "zeigt" auf das Urbild der [mm] Menge\{1\}.
[/mm]
Ja, genau.
> Da [mm] \phi
[/mm]
> wiederum eine Abbildung ist haben wir eine Komposition,
> richtig?
Eigentlich nicht.
f ist eine Abbildung, die auf Abbildungen angewendet wird.
Aber [mm] f(\phi) [/mm] ist keine Komposition von Abbildungen. Es kommt doch eine menge heraus und nicht eine Abbildung.
Mit [mm] f\circ \Phi [/mm] hat das nichts zu tun. Es passen ja die Zielmenge von [mm] \Phi [/mm] und die Definitionsmenge von f überhaupt nicht zusammen.
>
> Wäre also folgendes zu zeigen, damit die Bijektivität
> gegeben ist?
> (1)\ [mm] \phi_{1}\ \not=\ \phi_{2} [/mm] ==> [mm] f(\phi_{1}) \not= f(\phi_{2})
[/mm]
Genau.
> (2)\ [mm] \phi^{-1}(\{1\}) \in Abb(X,\{0,1\})
[/mm]
Für die Surjektivität ist folgendes zu zeigen:
Für jede beliebige Teilmenge T von X (also für jedes Element aus [mm] \mathcal{P}(X)) [/mm] findet man eine Abbildung [mm] \Phi\in [/mm] Abb(x, [mm] \{0,1\}) [/mm] mit [mm] f(\phi)=T, [/mm] dh. [mm] \phi^{-1}(\{1\})=T.
[/mm]
Falls Ihr nicht gleich wißt, was zu tun ist, empfehle ich wärmstens das, was ich in solchen Fällen immer tue.
Macht erstmal ein konkretes Beispiel, z.B. so:
Sei [mm] X:=\{ a,b,c,d\}
[/mm]
Abb(X , [mm] \{0,1\}) [/mm] enthält alle Abbildungen, deren Definitionsbereich X und deren Zielmenge [mm] \{0,1\} [/mm] ist.
Ein Beispiel ein Element dieser Menge wäre
[mm] \Phi: \{ a,b,c,d\}\to\{0,1\}
[/mm]
[mm] \phi(a):=1
[/mm]
[mm] \Phi(b):=1
[/mm]
[mm] \phi(c):= [/mm] 0
[mm] \phi(d):=1
[/mm]
Jetzt berechnen wir [mm] f(\phi).
[/mm]
[mm] f(\phi)=\phi^{-1}(\{1\})=\{a,b,d\}.
[/mm]
Jetzt könnt Ihr Euch ja mal folgendes Überlegen: für welche Abbildung aus Abb(X , [mm] \{0,1\}) [/mm] wäre das Urbild der 1 die Menge [mm] \{c,d\} [/mm] ?
Wie müßte diese Abbildung definiert sein?
>
> Wenn nein, wird's zumindest "wärmer"? *g*
>
> (EDIT)
> Ich habe mir jetzt zusammen mit einem Kommilitonen einige
> Gedanken dazu gemacht und wir glauben, dass wir zumindest
> die Injektivität zeigen können.
>
> [mm] f(\phi_{1}) [/mm] = [mm] \phi^{-1}(\{1\}) [/mm] = [mm] f(\phi_{2})
[/mm]
> [mm] \Rightarrow \phi_{1} [/mm] = [mm] \phi_{2}
[/mm]
>
[mm] >\Rightarrow\ [/mm] f\ ist\ injektiv
>
> Könnt ihr das bestätigen?
Nein, das reicht noch nicht. Aber das wird!
Sei [mm] f(\phi_{1}) [/mm] = [mm] f(\phi_{2}).
[/mm]
==> (Definition anwenden!) [mm] \phi_1^{-1}(\{1\})=\phi_2^{-1}(\{1\})
[/mm]
Was bedeutet das denn? [mm] \phi_1 [/mm] und [mm] \phi_2 [/mm] bilden dieselben Elemente auf die 1 ab.
Und worauf bilden sie die anderen Elemente ab? (Viel Auswahl gibt's nicht...)
Bedenkt nun, wann zwei Funktionen gleich sind.
Gruß v. Angela
|
|
|
| |
|
Also ich fasse nochmal schnell zusammen:
Eine beliebige Menge X:
[mm]X = \{a, b, c, d,\ldots\}[/mm]
Unsere Definitionsmenge:
[mm]Abb (X, \{0,1\}) = \{\phi_{1},\phi_{2},\phi_{3},\ldots\}[/mm],
[mm]$mit\ \phi:$[/mm]
[mm] \begin{matrix}
X &\to& \{0,1\}\\
x &\mapsto& 0 \vee 1
\end{matrix}
[/mm]
Unsere Zielmenge:
[mm]\mathcal{P}(X) = \{A | A \subseteq X\}[/mm]
Unsere Abbildung:
[mm] \begin{matrix}
f: & Abb(X,\{0,1\} &\to& \mathcal{P}(X)\\
& \phi &\mapsto& \phi^{-1}(\{1\})
\end{matrix}
[/mm]
Zu zeigen für Bijektion:
injektiv:
[mm]\phi_{1}\ \not=\ \phi_{2} \Rightarrow f(\phi_{1}) \not= f(\phi_{2})[/mm]
$ [mm] f(\phi_{1}) [/mm] $ = $ [mm] \phi^{-1}(\{1\}) [/mm] $ = $ [mm] f(\phi_{2}) [/mm] $
$ [mm] \Rightarrow \phi_{1} [/mm] $ = $ [mm] \phi_{2} [/mm] $
$ [mm] \Rightarrow\ [/mm] f\ ist\ injektiv $
>Nein, das reicht noch nicht. Aber das wird!
>
>Sei $ [mm] f(\phi_{1}) [/mm] $ = $ [mm] f(\phi_{2}). [/mm] $
>
>==> (Definition anwenden!) $ [mm] \phi_1^{-1}(\{1\})=\phi_2^{-1}(\{1\}) [/mm] $
>
>Was bedeutet das denn? $ [mm] \phi_1 [/mm] $ und $ [mm] \phi_2 [/mm] $ bilden dieselben >Elemente auf die 1 ab.
>
>Und worauf bilden sie die anderen Elemente ab? (Viel Auswahl gibt's >nicht...)
>
>Bedenkt nun, wann zwei Funktionen gleich sind.
1. Ja, was heißt das? War das eine rhetorische Frage?
2. Ich mutmaße mal auf 0.
3. Wenn (1) ihre Definitionsmengen gleich sind, (2) ihre Zielmengen gleich sind und (3) gleiche Elemente der Def-Menge auf gleiche Elemente der Zielmenge abgebildet werden.
Aber was bringt mir das? Letztendlich ist die Vorstellung davon was ich zu tun habe dadurch nur noch mehr verschwommen. Was fehlt denn an meinem Beweis?
surjektiv:
[mm]\forall\ A \in \mathcal{P}(X)\ \exists\ \phi \in Abb(X, \{0,1\})\ mit\ f(\phi) = \phi^{-1}(\{1\})[/mm]
Ich schätze mal, der Abschnitt mit den Teilmengen T [mm] \in [/mm] X, dem "konkreten Beispiel" u.s.w. bezog sich auf die Surjektion. Denn bezüglich Injektion kann ich da keinerlei Zusammenhang erkennen.
> Jetzt könnt Ihr Euch ja mal folgendes Überlegen: für welche Abbildung
> aus Abb(X , $ [mm] \{0,1\}) [/mm] $ wäre das Urbild der 1 die Menge $ [mm] \{c,d\} [/mm] $ ?
> Wie müßte diese Abbildung definiert sein?
Für keine der Abbildungen, denke ich. Denn entweder bildet [mm] \phi [/mm] auf die 1 ab oder [mm] \phi [/mm] bildet auf die 0 ab. Wie Du schon sagt, $ [mm] f(\phi) [/mm] = [mm] \phi^{-1}(\{1\}) [/mm] = [mm] \{a, b, d\} [/mm] $. Wir könnten natürlich noch [mm] $g(\phi) [/mm] = [mm] \phi^{-1}(\{0\}) [/mm] = [mm] \{d\} [/mm] $ bilden. Aber wie man auf die Menge [mm] \{c,d\} [/mm] kommen könnte ist mir vollkommen schleierhaft.
Danke vielmals für Deine wiederholten Hilfeversuche, auch wenn Du eigentlich mit jedem Beitrag mehr neue Fragen aufwarfst als ich mit den Informationen beantworten konnte. Aber das liegt ja nicht an Dir, denke ich. ^^ Danke nochmals
~LG W
|
|
|
| |
|
> Also ich fasse nochmal schnell zusammen:
>
> Eine beliebige Menge X:
> [mm]X = \{a, b, c, d,\ldots\}[/mm]
>
> Unsere Definitionsmenge:
> [mm]Abb (X, \{0,1\}) = \{\phi_{1},\phi_{2},\phi_{3},\ldots\}[/mm],
>
> [mm]$mit\ \phi:$[/mm]
> [mm]\begin{matrix}
X &\to& \{0,1\}\\
x &\mapsto& 0 \vee 1
\end{matrix}[/mm]
>
> Unsere Zielmenge:
> [mm]\mathcal{P}(X) = \{A | A \subseteq X\}[/mm]
>
> Unsere Abbildung:
> [mm]\begin{matrix}
f: & Abb(X,\{0,1\} &\to& \mathcal{P}(X)\\
& \phi &\mapsto& \phi^{-1}(\{1\})
\end{matrix}[/mm]
>
> Zu zeigen für Bijektion:
>
> injektiv:
> [mm]\phi_{1}\ \not=\ \phi_{2} \Rightarrow f(\phi_{1}) \not= f(\phi_{2})[/mm]
>
> [mm]f(\phi_{1})[/mm] = [mm]\phi^{-1}(\{1\})[/mm] = [mm]f(\phi_{2})[/mm]
> [mm]\Rightarrow \phi_{1}[/mm] = [mm]\phi_{2}[/mm]
> [mm]\Rightarrow\ f\ ist\ injektiv[/mm]
>
> >Nein, das reicht noch nicht. Aber das wird!
> >
> >Sei [mm]f(\phi_{1})[/mm] = [mm]f(\phi_{2}).[/mm]
> >
> >==> (Definition anwenden!)
> [mm]\phi_1^{-1}(\{1\})=\phi_2^{-1}(\{1\})[/mm]
> >
> >Was bedeutet das denn? [mm]\phi_1[/mm] und [mm]\phi_2[/mm] bilden dieselben
> >Elemente auf die 1 ab.
> >
> >Und worauf bilden sie die anderen Elemente ab? (Viel
> Auswahl gibt's >nicht...)
> >
> >Bedenkt nun, wann zwei Funktionen gleich sind.
>
> 1. Ja, was heißt das? War das eine rhetorische Frage?
Hallo,
das war eine der Fragen, die ich dann selbst beantwortet habe und den Fortschritt der Aufgabe nicht zu behindern.
Es war auch eine Frage um zu zeigen, welche Fragen man sich im Verlaufe eine Aufgabe stellen muß.
> 2. Ich mutmaße mal auf 0.
Genau.
> 3. Wenn (1) ihre Definitionsmengen gleich sind, (2) ihre
> Zielmengen gleich sind und (3) gleiche Elemente der
> Def-Menge auf gleiche Elemente der Zielmenge abgebildet
> werden.
Haargenau.
> Aber was bringt mir das? Letztendlich ist die Vorstellung
> davon was ich zu tun habe dadurch nur noch mehr
> verschwommen. Was fehlt denn an meinem Beweis?
Es fehlt in Deinem Beweis die Begründung dafür, warum für [mm] \phi_1 [/mm] und [mm] \phi_2 [/mm] die von Dir unter drei genannten Punkte zutreffen.
Erst dann darfst Du schreiben "==>" [mm] \phi_1=\phi_2".
[/mm]
>
> surjektiv:
> [mm]\forall\ A \in \mathcal{P}(X)\ \exists\ \phi \in Abb(X, \{0,1\})\ mit\ f(\phi) = \phi^{-1}(\{1\})[/mm]
>
> Ich schätze mal, der Abschnitt mit den Teilmengen T [mm]\in[/mm] X,
> dem "konkreten Beispiel" u.s.w. bezog sich auf die
> Surjektion. Denn bezüglich Injektion kann ich da keinerlei
> Zusammenhang erkennen.
Ja, richtig, das war ein Schusselfehler, den ich beseitigt habe.
Gut, daß Du keinen Zusammenhang zur Injektion gesehen hast.
>
> > Jetzt könnt Ihr Euch ja mal folgendes Überlegen: für welche
> Abbildung
> > aus Abb(X , [mm]\{0,1\})[/mm] wäre das Urbild der 1 die Menge
> [mm]\{c,d\}[/mm] ?
> > Wie müßte diese Abbildung definiert sein?
>
> Für keine der Abbildungen, denke ich.
Du sprichst hier von Abbildungen
Bisher hatte ich beispielhaft ja nur die eine Abbildung angegeben.
Ich hatte sie angegeben, indem ich für jedes Element gesagt hatte, worauf es durch diese Abbildung [mm] \phi [/mm] abgebildet wird, so'ne Art Wertetabelle.
Aber es gibt zwischen X und [mm] \{0,1\} [/mm] doch noch viiiiiiiiiiiiiiiel mehr Abbildungen. (Insgesamt 16 Stück, nebenbei bemerkt...)
Schreib mal noch 'ne Abbildung auf.
[mm] \psi: [/mm] X [mm] \to \{0,1\}
[/mm]
[mm] a\mapsto...
[/mm]
[mm] b\mapsto...
[/mm]
[mm] c\mapsto...
[/mm]
[mm] d\mapsto...
[/mm]
gruß v. Angela
> Denn entweder bildet
> [mm]\phi[/mm] auf die 1 ab oder [mm]\phi[/mm] bildet auf die 0 ab. Wie Du
> schon sagt, [mm]f(\phi) = \phi^{-1}(\{1\}) = \{a, b, d\} [/mm]. Wir
> könnten natürlich noch [mm]f(\phi) = \phi^{-1}(\{0\}) = \{d\}[/mm]
> bilden. Aber wie man auf die Menge [mm]\{c,d\}[/mm] kommen könnte
> ist mir vollkommen schleierhaft.
Du mußt erst die passende Funktion finden.
Die von mir vorgegebene Funktion [mm] \phi [/mm] tut's nicht. Aber eine von den 15 anderen.
Gruß v. Angela
|
|
|
|
