injektiv-->surjektiv < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:51 Mo 08.03.2010 | | Autor: | s-jojo |
| Aufgabe | Es seien A, B endliche Mengen mit |A|=|B| und f: [mm] A\to [/mm] B eine Abbildung. Dann gilt inj.<=>surj.<=>bij.
Beweis:
"inj => surj.": f: [mm] A\to [/mm] f(A) ist surj. und auch inj., also bij. => |f(A)|=|A|=|B| => f(A)=B also f surj. |
Meine Fragen nun :D
1.) Soweit ich es richtig verstanden habe, ist es so, dass man unter den Pfeil von "|f(A)|=|A|=|B| => f(A)=B"
[mm] "f(A)\le [/mm] B schreibt, weil f(A) auch nur eine Teilmenge von B sein kann?
2.) Man folgert doch schon, dass f(A)=B ist, das heißt dass die Abbildung bijektiv ist, aber wieso will man noch die Surjektivität beweisen? Vielleicht damit man letztendlich den Ringschluss von inj., surj. und bij. erhält?
Danke schon mal im Voraus! :)
achja, ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt! :D
|
|
| |
|
Hallo,
> Es seien A, B endliche Mengen mit |A|=|B| und f: [mm]A\to[/mm] B
> eine Abbildung. Dann gilt inj.<=>surj.<=>bij.
>
> Beweis:
> "inj => surj.": f: [mm]A\to[/mm] f(A) ist surj. und auch inj., also
> bij. => |f(A)|=|A|=|B| => f(A)=B also f surj.
> Meine Fragen nun :D
>
> 1.) Soweit ich es richtig verstanden habe, ist es so, dass
> man unter den Pfeil von "|f(A)|=|A|=|B| => f(A)=B"
> [mm]"f(A)\le[/mm] B schreibt, weil f(A) auch nur eine Teilmenge
> von B sein kann?
Ja, genau.
f(A) ist prinzipiell erstmal nur Teilmenge von B.
Schreib' dann aber auch [mm] $f(A)\subset [/mm] B$, und nicht mit [mm] \le [/mm] - Zeichen.
> 2.) Man folgert doch schon, dass f(A)=B ist, das heißt
> dass die Abbildung bijektiv ist, aber wieso will man noch
> die Surjektivität beweisen? Vielleicht damit man
> letztendlich den Ringschluss von inj., surj. und bij.
> erhält?
Der abgebildete Beweis folgert erstmal nur die Surjektivität aus der Injektivität.
Aus f(A) = B folgt im Allgemeinen noch keine Bijektivität, das ist nur so, weil f ohnehin schon als injektiv angenommen wird.
Was nun noch beim Beweis fehlt, ist der Schluss von Surjektivität auf Injektivität. Dass aus Bijektivität beides folgt, ist klar.
Sur --> Inj:
Wegen f surjektiv ist f(A) = B. Damit ist auch |f(A)| = |B|. Daraus folgt f injektiv.
Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:26 Mo 15.03.2010 | | Autor: | s-jojo |
| Aufgabe | "surj- => bij.": z.z. f injektiv
- für [mm] b\in [/mm] B gilt: f(f^-1(b))={b}
- für A' [mm] \subseteq [/mm] A gilt: f(A)\ f(A') [mm] \subseteq [/mm] f(A\ A')
Dann: Falls f nicht injektiv, dann gibt es b [mm] \in [/mm] B mit |f^-1(b)| [mm] \ge [/mm] 2, also |A\ [mm] f^-1(b)|\le [/mm] n-2 (n=|A|=|B|)
f Abb. => |f(A\ [mm] f^-1(b))|\le [/mm] n-2
dann gilt
|f(A)\ {b} |=|B\ {b}|=n-1 --> Widerspruch! |
Meine Frage besteht daraus, dass ich nicht weiß, wieso man von "n-2" plötzlich auf "n-1" kommt. Ich meine man hat
|f(A\ f^-1(b))| durch |B\ {b} | ersetzt, aber wie kann man darauf schließen, dass es zu "n-1" kommt?
- Hab diese Frage auch in keinem andern Forum gestellt! ;)
freue mich über Antworten :D:D
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:23 Di 16.03.2010 | | Autor: | Blech |
Hi,
würde es Dich umbringen, den Formeleditor zu benutzen? Dein Zeugs ist verdammt schwer zu lesen. Danke.
> "surj- => bij.": z.z. f injektiv
>
> - für [mm]b\in[/mm] B gilt: f(f^-1(b))={b}
> - für A' [mm]\subseteq[/mm] A gilt: f(A)\ f(A') [mm]\subseteq[/mm] f(A\
> A')
>
> Dann: Falls f nicht injektiv, dann gibt es b [mm]\in[/mm] B mit
> |f^-1(b)| [mm]\ge[/mm] 2, also |A\ [mm]f^-1(b)|\le[/mm] n-2 (n=|A|=|B|)
>
> f Abb. => |f(A\ [mm]f^-1(b))|\le[/mm] n-2
> dann gilt
Das "dann gilt" ist eine unglückliche Formulierung.
Betrachten wir die nächste Aussage mal für sich allein, dann ist sie nämlich sehr einfach:
> |f(A)\ {b} |=|B\ {b}|=n-1 --> Widerspruch!
$f(A)=B$, wegen Surjektivität, also $|f(A)|=|B|=n$ nach Voraussetzung.
Wenn ich jetzt ein einzelnes Element [mm] ($\{b\}$) [/mm] wegnehme, dann hat das, was übrig bleibt, Mächtigkeit n-1.
Mit [mm] $A':=f^{-1}(b)$ [/mm] können wir jetzt die obige Aussage (die Dir klar ist?) verwenden:
[mm] $f(A)\backslash\{b\} [/mm] = [mm] f(A)\backslash f\left(f^{-1}(b)\right) [/mm] = [mm] f(A)\backslash [/mm] f(A') [mm] \subseteq f(A\setminus [/mm] A')= [mm] f\left(A\setminus f^{-1}(b)\right)$
[/mm]
Aber die linke Seite hat echt mehr Elemente (eben n-1 gegenüber höchstens n-2) als die rechte, also kann es keine Untermenge sein. Widerspruch.
ciao
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:01 Di 16.03.2010 | | Autor: | s-jojo |
> Hi,
>
> würde es Dich umbringen, den Formeleditor zu benutzen?
> Dein Zeugs ist verdammt schwer zu lesen. Danke.
Sorry :D aber ich bin damit noch nicht so vertraut und irgendwie klappt das manchmal nicht so, wie ich mir das vorstelle. Aber danke, dass du das trotzdem gelesen hast ;)
> - für A' [mm]\subseteq[/mm] A gilt: f(A)\ f(A') [mm]\subseteq[/mm] f( A\ A')
Ist bestimmt eine blöde Frage, aber ich versteh jetzt nicht, wieso f(A)\ f(A') [mm]\subseteq[/mm] f( A\ A') ist, was mir eigentlich früher hätte auffallen sollen.
> Aber die linke Seite hat echt mehr Elemente (eben n-1
> gegenüber höchstens n-2) als die rechte, also kann es
> keine Untermenge sein. Widerspruch.
Das hab ich jetzt verstanden :D
nochmal Dankeschön! :)
|
|
|
| |
|
Hi,
> Ist bestimmt eine blöde Frage, aber ich versteh jetzt
> nicht, wieso f(A)\ f(A') [mm]\subseteq[/mm] f( A\ A') ist, was mir
> eigentlich früher hätte auffallen sollen.
Es ist $\ A' [mm] \subseteq [/mm] A $
Dann ist $\ f(A') [mm] \subseteq [/mm] f(A) $
Sei $\ y [mm] \in f(A)\backslash [/mm] f(A') [mm] \Rightarrow [/mm] y [mm] \in [/mm] f(A) [mm] \wedge [/mm] y [mm] \not\in [/mm] f(A')$, $\ y:=f(x) [mm] \Rightarrow [/mm] x [mm] \in [/mm] A [mm] \wedge [/mm] x [mm] \not\in [/mm] A' [mm] \Rightarrow [/mm] x [mm] \in [/mm] A [mm] \backslash [/mm] A' [mm] \Rightarrow [/mm] y [mm] \in [/mm] f(A [mm] \backslash [/mm] A') $
Reicht das?
Grüße
ChopSuey
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:45 Mi 17.03.2010 | | Autor: | s-jojo |
>
> Es ist [mm]\ A' \subseteq A[/mm]
>
> Dann ist [mm]\ f(A') \subseteq f(A)[/mm]
>
> Sei [mm]\ y \in f(A)\backslash f(A') \Rightarrow y \in f(A) \wedge y \not\in f(A')[/mm],
> [mm]\ y:=f(x) \Rightarrow x \in A \wedge x \not\in A' \Rightarrow x \in A \backslash A' \Rightarrow y \in f(A \backslash A')[/mm]
Das hab ich jetzt verstanden :)
Aber wieso ist [mm] f(A)\backslash f(A')\subseteq f(A\backslash [/mm] A')? Weil wenn [mm] y\in f(A)\backslash [/mm] f(A') und [mm] y\in f(A\backslash [/mm] A'), dann sind [mm] f(A)\backslash [/mm] f(A')= f(A [mm] \backslash [/mm] A'), oder? Wieso ist das eine also eine Teilmenge?
Das ist jetzt wirklich meine letzte Frage zu diesem Thema, alles andere hab ich durch die super Erklärungen bis aufs kleinste Detail verstanden ;)
Dankeschön :)
Gruß,
s-jojo
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:12 Mi 17.03.2010 | | Autor: | tobit09 |
Hallo,
> Aber wieso ist [mm]f(A)\backslash f(A')\subseteq f(A\backslash[/mm]
> A')? Weil wenn [mm]y\in f(A)\backslash[/mm] f(A') und [mm]y\in f(A\backslash[/mm]
> A'), dann sind [mm]f(A)\backslash[/mm] f(A')= f(A [mm]\backslash[/mm] A'),
> oder? Wieso ist das eine also eine Teilmenge?
1. Würde [mm] $f(A)\backslash [/mm] f(A')= [mm] f(A\backslash [/mm] A')$ gelten, so wäre insbesondere [mm] $f(A)\backslash f(A')\subseteq f(A\backslash [/mm] A')$ richtig. Für jede Menge M gilt nämlich [mm] $M\subseteq [/mm] M$.
2. Tatsächlich gilt aber i.A. gar nicht [mm] $f(A)\backslash [/mm] f(A')= [mm] f(A\backslash [/mm] A')$: Wenn z.B. [mm] $b\in [/mm] B$ ein beliebiges Element und f die konstante Abbildung auf b ist (also $f(a)=b$ für alle [mm] $a\in [/mm] A$ gilt), $A'$ nicht die leere Menge ist und [mm] $A\not=A'$ [/mm] gilt, so folgt [mm] $f(A)\backslash f(A')=\{b\}\backslash \{b\}=\emptyset\not=\{b\}=f(A\backslash [/mm] A')$.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:51 Mi 17.03.2010 | | Autor: | s-jojo |
Hi :)
ich weiß nicht, aber ich hab irgendwie eine seeeehr lange Leitung im Moment :D
> [mm]A\not=A'[/mm] gilt, so folgt
> [mm]f(A)\backslash f(A')=\{b\}\backslash \{b\}=\emptyset\not=\{b\}=f(A\backslash A')[/mm].
Hmm... Wenn jetzt [mm] A\not=A', [/mm] wieso haben die beide dann [mm] {b\} [/mm] als Abbildung, sodass die leere Menge rauskommt?
Könntest du oder jemand anderes mir so ein Zahlenbeispiel geben? Vielleicht versteh ich das dann besser.
Ganz liebe Grüße
s-jojo :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:45 Mi 17.03.2010 | | Autor: | tobit09 |
> > [mm]A\not=A'[/mm] gilt, so folgt
> > [mm]f(A)\backslash f(A')=\{b\}\backslash \{b\}=\emptyset\not=\{b\}=f(A\backslash A')[/mm].
>
> Hmm... Wenn jetzt [mm]A\not=A',[/mm] wieso haben die beide dann [mm]{b\}[/mm]
> als Abbildung, sodass die leere Menge rauskommt?
Nehmen wir uns z.B. die Gleichung [mm] $f(A)=\{b\}$ [/mm] heraus und zeigen wir beide Inklusionen:
[mm] "\subseteq": [/mm] Sei [mm] $b'\in [/mm] f(A)$. Dann gibt es ein [mm] $a\in [/mm] A$ mit $f(a)=b'$. Wegen $f(a)=b$ folgt $b=b'$ und somit [mm] $b'\in\{b\}$.
[/mm]
[mm] "\supseteq": [/mm] Sei [mm] $b'\in\{b\}$, [/mm] also $b'=b$. Da [mm] $A'\not=\emptyset$ [/mm] existiert ein [mm] $a\in [/mm] A'$. Wegen [mm] $A'\subset [/mm] A$ gilt [mm] $a\in [/mm] A$. Wegen $f(a)=b$ gilt [mm] $b\in [/mm] f(A)$, also [mm] $b'\in [/mm] f(A)$.
> Könntest du oder jemand anderes mir so ein Zahlenbeispiel
> geben? Vielleicht versteh ich das dann besser.
Sei [mm] $f:\IR\to\IR,x\mapsto5$ [/mm] (also [mm] $A=B=\IR$ [/mm] und $b=5$; außerdem sei [mm] $A'=\IQ$). [/mm] Es gilt dann [mm] $f(\IR)\backslash f(\IQ)=\{5\}\backslash\{5\}=\emptyset\not=\{5\}=f(\IR\backslash\IQ)$.
[/mm]
|
|
|
|
