Abbildung zw 2 endl. gleichm. < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:24 Mi 17.10.2007 | | Autor: | elefanti |
| Aufgabe | Sei f: X->Y eine Abbildung zwischen zwei endlichen, gleichmächtigen Mengen X und Y. Dann sind äquivalent:
f ist injektiv, f ist surjektiv und f ist bijektiv. |
Hallo ihr,
ich habe zu der Aufgabe den Beweis gegeben, verstehe ihn aber überhaupt nicht.
Sei f injektiv. Es ist zu zeigen:
[mm] \forall y\in [/mm] Y: [mm] |f^{-1}({y})|>=1.
[/mm]
Wieso ist das zu zeigen? Wie kommt man auf die Mächtigkeit und warum nutzt man die Umkehrfunktion?
Es gilt:
[mm] |X|=\summe_{x\in X}^{}1=\summe_{\y\in Y}^{}|f^{-1}({y})| [/mm] und [mm] |Y|=\summe_{y\in Y}^{}1.
[/mm]
Nach Voraussetzung gilt |X|=|Y|, somit folgt
[mm] \summe_{y\in Y}^{}( |f^{-1}({y})|-1)=0.
[/mm]
Da f injektiv ist, gilt für alle y [mm] \in [/mm] Y: [mm] |f^{-1}({y})|-1<=0. [/mm] Dann muss aber gelten [mm] |f^{-1}({y})|-1=0.
[/mm]
Den Rest verstehe ich vielleicht, wenn mir der Anfang klar ist 
Liebe Grüße
Elefanti
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:35 Mi 17.10.2007 | | Autor: | andreas |
hi
> Sei f injektiv. Es ist zu zeigen:
> [mm]\forall y\in[/mm] Y: [mm]|f^{-1}({y})|>=1.[/mm]
> Wieso ist das zu zeigen? Wie kommt man auf die Mächtigkeit
> und warum nutzt man die Umkehrfunktion?
also es handelt sich dabei nicht um die umkehrfunktion (die wäre ja nur dann definiert, wenn man schon wüßte, dass $f$ bijektiv ist, das ist hier aber a priori noch nicht klar), sondern um die urbild abbildung, die einer menge $M [mm] \subseteq [/mm] Y$ die menge zuordnet, die auf diese menge abgebildet wird, also [mm] $f^{-1}(M) [/mm] := [mm] \{ x \in X: f(x) \in M \}$. [/mm] ist die menge $M = [mm] \{y\}$ [/mm] einelementig, so lässt man die mengenklammern häufig weg, also [mm] $f^{-1}(y) [/mm] := [mm] f^{-1}(\{y\})$.
[/mm]
du willst hier ja wohl erstmal zeigen, dass $f$ surjektiv ist, also das jedes element $y [mm] \in [/mm] Y$ getroffen wird, aber das ist ja offensichtlich äquivalent dazu, dass [mm] $f^{-1}(y)$ [/mm] mindestens ein element enthält (welches dann per definition auf $y$ abgebildet wird).
ich hoffe mal das ist nun etwas klarer geworden.
grüße
andreas
|
|
|
|
