Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Mengenlehre » Aufgabe zu Mächtigkeit von Mengen
Thema eröffnet 2018-11-10 16:07 von X3nion
Druckversion
Druckversion
Seite 2   [1 2]   2 Seiten
Autor
Kein bestimmter Bereich J Aufgabe zu Mächtigkeit von Mengen
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.40, vom Themenstarter, eingetragen 2018-11-11


Ahhh auch über einen Widerspruchsbeweis also!

Die Inklusion i $N_{m+1} \to N_{n}$ ist injektiv, und laut Annahme auch die Inklusion f $N_{n} \to N_{m}$.
Also wäre auch die Komposition $f \circ i, N_{m+1} \to N_{m}$ injektiv im Widerspruch zum bewiesenen Lemma.
Folglich war die Behauptung falsch und $N_{n} \to N_{m}$ ist nicht injektiv.


Um nun damit schlussendlich die Aussage zu beweisen:
Sei für $n \in \IN: N_{n} = \{m \in \IN: m \le n\}.$

Zu zeigen ist, dass wenn eine bijektive Abbildung $N_{n} \to N_{\tilde{n}}$ existiert, daraus $n = \tilde{n}$ folgt.

Angenommen $n > \tilde{n}$. Dies wäre nach dem bewiesenen Lemma ein Widerspruch zur vorausgesetzten Injektivität. Analog $n < \tilde{n}$.

=> $n = \tilde{n}$.


Würde das passen?


Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.41, eingetragen 2018-11-11


Ja. 😄



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.42, vom Themenstarter, eingetragen 2018-11-11


Woa echt vielen Dank dir für deine Unterstützung zum Beweis des 1. Teils! 😄
Allein wäre ich da echt aufgeschmissen gewesen...

Zum Nachweis der 2. Aussage:
 Für zwei beliebige endliche Mengen M,N gilt: Es ist #M = #N genau dann, wenn für jede Abbildung $f: M \to N$ gilt, dass f injektiv $\iff$ f surjektiv.


„=>“ Würde man hier wegen #M = #N davon ausgehen, dass es eine bijektive Abbildung zwischen M und N gibt?


Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.43, vom Themenstarter, eingetragen 2018-11-12


Hallo  zusammen,

wie würde man die in Beitrag 42 beschriebene Behauptung zeigen?

Für jede Hilfe wäre ich sehr dankbar!


Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.44, vom Themenstarter, eingetragen 2018-11-13


Guten Abend zusammen,

ich würde mich sehr freuen, wenn mir jemand von euch bei der Bearbeitung der Aufgabe behilflich sein könnte!


Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.45, eingetragen 2018-11-13

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
Ich hatte die letzten zwei Tage leider keine Zeit um zu antworten.

Es geht vielleicht einfacher, aber ich würde mal so anfangen:

Sei $\#M=m$ und $\#N=n$ und seien $\varphi: M\to N_m$ und $\psi: N\to N_n$ Bijektionen.
Ist $f:M\to N$ irgendeine Abbildung, dann sei $f': N_m\to N_n$ definiert als $f':=\psi\circ f \circ \varphi^{-1}$.
Es gilt: $f$ ist injektiv bzw. surjektiv genau dann, wenn $f'$ injektiv bzw. surjektiv ist.

Für die Hinrichtung in deiner Aufgabe ist $m=n$ und es bleibt also nur noch zu zeigen, dass jede injektive Abbildung $f':N_m\to N_m$ auch surjektiv ist und umgekehrt.
Die Richtung "$f'$ injektiv $\Rightarrow$ $f'$ surjektiv" haben wir im Wesentlichen schon im ersten Teil bewiesen. (Wenn $f'$ nicht surjektiv ist, dann können wir den Wertebereich einschränken, und dann eine Injektion $N_m\to N_{m-1}$ konstruieren.)
Wenn umgekehrt $f'$ surjektiv ist, dann hat $f'$ ein Rechtsinverses $g': N_m\to N_m$ mit $f'\circ g' = \id_{N_m}$, das injektiv ist. Also ...

Für die Rückrichtung kannst annehmen, dass $m\not= n$ und dann ein Gegenbeispiel angeben.

\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.46, vom Themenstarter, eingetragen 2018-11-13


Hallo Nuramon und vielen Dank, dass du dich mit guten Ratschlägen gemeldet hast! :-)

Müsste es nicht lauten

$f' := \psi \circ f \circ \phi^{-1}$?

Ich würde nun zuerst die Richtung f' ist injektiv $\Rightarrow$ f' ist surjektiv betrachten.
Wo haben wir dies bereits bewiesen, bzw. wie ließe sich die Injektion $N_{m} \to N_{m-1}$ konstruieren? Und wieso können wir gerade das m-te Element aus dem Wertebereich entnehmen und erhalten $N_{m-1}$?


Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.47, eingetragen 2018-11-13

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
2018-11-13 23:22 - X3nion in Beitrag No. 46 schreibt:
Müsste es nicht lauten

$f' := \psi \circ f \circ \phi^{-1}$?
Stimmt. Ich habe es oben geändert.


Ich würde nun zuerst die Richtung f' ist injektiv $\Rightarrow$ f' ist surjektiv betrachten.
Wo haben wir dies bereits bewiesen, bzw. wie ließe sich die Injektion $N_{m} \to N_{m-1}$ konstruieren? Und wieso können wir gerade das m-te Element aus dem Wertebereich entnehmen und erhalten $N_{m-1}$?
Ich wollte darauf hinaus, dass wir schon wissen, dass es keine Injektion $N_m\to N_{m-1}$ gibt. Wenn $f':N_m\to N_m$ injektiv, aber nicht surjektiv ist, dann können wir $f'$ mit einer Bijektion $h:N_m\to N_m$ verknüpfen, so dass $m$ nicht im Bild von $h\circ f'$ liegt und erhalten so einen Widerspruch.

Es geht sogar noch ein bisschen einfacher: Wenn $f':N_m\to N_m$ injektiv, aber nicht surjektiv ist, dann können wir $f'$ erweitern zu einer injektiven Abbildung $f'':N_{m+1}\to N_m$.

\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.48, vom Themenstarter, eingetragen 2018-11-13




Ich wollte darauf hinaus, dass wir schon wissen, dass es keine Injektion $N_m\to N_{m-1}$ gibt. Wenn $f':N_m\to N_m$ injektiv, aber nicht surjektiv ist, dann können wir $f'$ mit einer Bijektion $h:N_m\to N_m$ verknüpfen, so dass $m$ nicht im Bild von $h\circ f'$ liegt und erhalten so einen Widerspruch.

Okay warte, aber dann habe ich ja eine Abbildung $h \circ f': N_{m} \to N_{m}$, aber wo hätten wir dann die "Widerspruchsabbildung" $N_{m} \to N_{m-1}?$ Könntest du das vielleicht an einem Beispiel verdeutlichen?


Es geht sogar noch ein bisschen einfacher: Wenn $f':N_m\to N_m$ injektiv, aber nicht surjektiv ist, dann können wir $f'$ erweitern zu einer injektiven Abbildung $f'':N_{m+1}\to N_m$.

In diesem Fall setzt man einfach $f''(m+1)$ als den Wert, welcher sonst im Bild unter f' nicht getroffen wird?


Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.49, eingetragen 2018-11-13

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
2018-11-13 23:48 - X3nion in Beitrag No. 48 schreibt:


Ich wollte darauf hinaus, dass wir schon wissen, dass es keine Injektion $N_m\to N_{m-1}$ gibt. Wenn $f':N_m\to N_m$ injektiv, aber nicht surjektiv ist, dann können wir $f'$ mit einer Bijektion $h:N_m\to N_m$ verknüpfen, so dass $m$ nicht im Bild von $h\circ f'$ liegt und erhalten so einen Widerspruch.

Okay warte, aber dann habe ich ja eine Abbildung $h \circ f': N_{m} \to N_{m}$, aber wo hätten wir dann die "Widerspruchsabbildung" $N_{m} \to N_{m-1}?$ Könntest du das vielleicht an einem Beispiel verdeutlichen?
Leider nicht, da es ja keine solchen Abbildungen gibt.  😛
Aber alles was noch zu tun ist, ist die Abbildung $N_m\to N_{m-1}, x\to h(f'(x))$ zu betrachten.



Es geht sogar noch ein bisschen einfacher: Wenn $f':N_m\to N_m$ injektiv, aber nicht surjektiv ist, dann können wir $f'$ erweitern zu einer injektiven Abbildung $f'':N_{m+1}\to N_m$.

In diesem Fall setzt man einfach $f''(m+1)$ als den Wert, welcher sonst im Bild nicht getroffen wird?
Genau.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.50, vom Themenstarter, eingetragen 2018-11-14




Leider nicht, da es ja keine solchen Abbildungen gibt.  😛
Aber alles was noch zu tun ist, ist die Abbildung $N_m\to N_{m-1}, x\to h(f'(x))$ zu betrachten.


Haha ja klar, ich Blödmann 😁
Aber ja jetzt wo du es sagst, leuchtet es mir ein.




Wenn umgekehrt $f'$ surjektiv ist, dann hat $f'$ ein Rechtsinverses $g': N_m\to N_m$ mit $f'\circ g' = id_{N_m}$, das injektiv ist. Also ...


Wieso ist das Rechtsinverse dann injektiv, also woraus folgt das?

Und folgt dann daraus, dass $f' \circ g$ bijektiv ist und deshalb auch $f'$, oder ist dies der falsche Schluss?


Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.51, eingetragen 2018-11-14

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
Rechtsinverse sind immer injektiv: Es gilt ganz allgemein für beliebige Abbildungen $f:X\to Y, g: Y\to X$, dass wenn $g\circ f = \id_X$, dann ist $f$ injektiv und $g$ surjektiv.

Und aus der schon bewiesenen Implikation folgt, dass das Rechtsinverse $g'$ hier auch surjektiv, also bijektiv ist. Daraus folgt dann aber auch, dass $f'$ schon bijektiv ist.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.52, vom Themenstarter, eingetragen 2018-11-14


Okay aber die Aussage müsste man streng genommen noch beweisen, da dies a priori nicht klar ist?


Und welchen Widerspruch meinst du?


Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.53, eingetragen 2018-11-14


Ja, das muss man beweisen. Der Beweis ist aber nicht schwierig.

Ich habe meinen vorigen Post noch editiert während du deinen geschrieben hast. Ist es so klarer? (Die nicht ausgeführten Argumente sollst du dir natürlich selbst ergänzen.)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.54, vom Themenstarter, eingetragen 2018-11-14


Okay also wir hatten auf dem Übungsblatt zu beweisen, dass wenn $g \circ f$ injektiv, so auch f und dass wenn $g \circ f$ surjektiv, so auch g surjektiv ist.

Fragen:

1) Können wir nun also annehmen, dass wenn $g \circ f = id_{X}$, dass dann $g \circ f$ bijektiv ist?
Weil dann würde dies Aussage direkt folgen.


2) Um nun zur eigentlichen Aufgabe zurückzukehren:
Aus $f' \circ g' = id_{N_{m}}$ folgt wegen g' injektiv, dass g' auch surjektiv ist nach der ersten Implikation. Weiter folgt ja, dass f' surjektiv ist. Wieso folgt daraus aber, dass f' schon bijektiv sein muss, also insbesondere die Injektivität von f?


Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.55, eingetragen 2018-11-14


1) Ich denke die Frage kannst du selbst beantworten.

2) Eine Abbildung ist bijektiv, genau dann, wenn sie ein Inverses hat (d.h. wenn es eine Abbildung gibt, die sowohl rechts- als auch linksinvers zu der gegebenen Abbildung ist.). Außerdem gibt es zu einer bijektiven Abbildung genau ein Links- bzw. genau ein Rechtsinverses (nämlich gerade das Inverse).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.56, vom Themenstarter, eingetragen 2018-11-14


Okay also es ist ja so, dass die Identität trivialerweise bijektiv ist, und deshalb auch $g \circ f$.


Ahh und ist ist es nun so, dass weil wir wissen, dass $f' \circ g' = id_{N_{m}}$ und $g' \circ f' = id_{N_{m}}$, dass deshalb f' ein Rechts- und Linksinverses besitzt und daher bijektiv ist?


Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.57, eingetragen 2018-11-14

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
2018-11-14 17:41 - X3nion in Beitrag No. 56 schreibt:
Ahh und ist ist es nun so, dass weil wir wissen, dass $f' \circ g' = id_{N_{m}}$ und $g' \circ f' = id_{N_{m}}$, dass deshalb f' ein Rechts- und Linksinverses besitzt und daher bijektiv ist?
Woher wissen wir, dass $g' \circ f' = id_{N_{m}}$ gilt?

Ich hatte es mir so gedacht: $g'$ ist bijektiv und wegen $f' \circ g' = id_{N_{m}}$ ist $f'=g'^{-1}$ das Inverse zu $g'$ und somit bijektiv.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.58, vom Themenstarter, eingetragen 2018-11-15


Ach ja klar, das macht echt Sinn!

Wie könnte ich nun die Rückimplikation zeigen?
Du meintest, ich könnte $m \neq n$ annehmen und dann ein Gegenbeispiel angeben.

f ist ja nun bijektiv genau dann, wenn f‘: $N_{m} \to N_{n}$ bijektiv ist.
Gelte nun m > n.
Wie könnte ich nun ein Gegenbeispiel konstruieren?

Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.59, eingetragen 2018-11-15

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
Du musst ein $f':N_m\to N_n$ finden, für dass die Äquivalenz "$f'$ ist injektiv genau dann, wenn $f'$ surjektiv ist" falsch ist. Ich bin sicher, dir fallen ein paar injektive aber nicht surjektive bzw. surjektive aber nicht injektive Abbildungen ein.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.60, vom Themenstarter, eingetragen 2018-11-15


Ja klar, die Abbildung f‘: $\{1,2\} \to \{1\}, f’(1) = f’(2) = 1$ ist surjektiv, aber nicht injektiv.
Ich hätte dann für m = 2 und n = 1 eine Abbildung f‘: $N_{2} \to N_{1}$ angegeben, sodass die Äquivalenz nicht gilt.
Aber ich muss ja eine Abbildung für beliebige m,n $\in \IN$ mit m > n, also $N_{m} \to N_{n}$ angeben, wie mache ich das dann?


Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.61, eingetragen 2018-11-15

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
Warum beschränkst du dich eigentlich auf den Fall $m>n$? Es ist schon sinnvoll die Fälle $m>n$ und $m<n$ zu unterscheiden, aber du musst diesmal beide betrachten (oder irgendwie begründen, dass einer ausreicht.).

Ich weiß leider nicht wie ich dir weiterhelfen kann ein geeignetes $f'$ zu finden, außer mit "Schreib einfach eine Abbildung auf". :P

Vielleicht hilft es, wenn du dir vorstellst, dass du $m$ Geschenke hast, die du an $n$ Personen verteilen willst. Eine Möglichkeit das zu tun wäre es jeder Person nacheinander erstmal ein Geschenk zu geben, und falls dann noch welche übrig sind wieder von vorn anzufangen. Aber es gibt noch viel einfacher aufzuschreibende Methoden.

\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.62, vom Themenstarter, eingetragen 2018-12-09


Hallo Nuramon,

der stressige Unialltag verwehrte mir bislang eine gedankliche Fortsetzung im Hinblick auf diese Aufgabe - dies hatte ich dir auch in einer privaten Nachricht geschrieben. Mal schauen, vielleicht komme ich in den Weihnachtsferien dazu 😄


Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.63, vom Themenstarter, eingetragen 2020-03-18


Ein herzliches Hallo an euch, liebe Community!

Ich möchte mich nun einem Beitrag widmen, der nun schon über ein Jahr her ist, und ihn wieder aufgreifen. Der stressige Unialltag hat es unmöglich gemacht, mich intensiver mit der Aufgabe zu beschäftigen, auch wenn ich sie sehr interessant fand und immer noch sehr interessant finde - ansonsten hätte ich mich nicht so intensiv damit befasst.
Herzlichen Dank an dir, Nuramon, für deine damalige intensive Unterstützung und Geduld!

Nun möchte ich die Aufgabe nochmals aufgreifen und ich würde euch bitten, durchzublättern, ob der Beweis vorerst nur zu 1) so in Ordnung wäre. 😄
Nebenbei habe ich noch eine Frage in blau hinterlegt.

- - - - - - - - - -

Voraussetzung

(a) Es seien M eine Menge und n eine natürliche Zahl. Wir sagen genau dann, dass M n Elemente hat, wenn es eine bijektive Abbildung M auf die Menge $m \in \IN: m \le n$ gibt. In dem Fall schreiben wir kurz

#M = n.

(b) Eine Menge heißt endlich genau dann, wenn es ein $n \in \IN \cup \{0\}$ gibt, sodass sie n Elemente hat.

Zu zeigen ist:

1) Die Definition ist sinnvoll: Falls M eine Menge und $n, \tilde{n} \in \IN$ sind und #M = n sowie #M = $\tilde{n}$, so ist $n = \tilde{n}$

2) Für zwei beliebige endliche Mengen M,N gilt: Es ist #M = #N genau dann, wenn für jede Abbildung $f: M \to N$ gilt, dass f injektiv $\iff$ f surjektiv.


Beweis zu 1)

Sei für $n \ge 0$ zunächst $N_{n}:= \{m \in \IN: m \le n\}$.

Zeige zunächst folgendes
Lemma:
Für $m \ge 0$ gibt es keine Injektion $N_{m+1} \to N_{m}$.

Induktionsanfang m=0: Es gibt keine Abbildung $N_{1} \to N_{0} = \emptyset$, da die leere Menge kein Element besitzt. Somit kann es auch keine Injektion geben.

Induktionsannahme: Es gilt für ein beliebiges aber festes $m \in \mathbb{N}$, dass es keine Injektion $N_{m+1} \to N_{m}$ gibt.

Induktionsschritt m -> m+1, zu zeigen: Es gibt keine Injektion $N_{m+2} \to N_{m+1}$.

Beweis durch Widerspruch: Nehme an, es gäbe eine Injektion $f: N_{m+2} \to N_{m+1}$, welche aufgrund ihrer Existenz insbesondere wohldefiniert ist.

Betrachte nun die Abbildung $f': N_{m+1}=N_{m+2}\setminus\{m+2\}\to N_{m+1}\setminus\{f(m+2)\}$, $x\mapsto f(x)$
Es gilt also nach Definition $f(x) = f'(x)$ $\forall x \in N_{m+1}$.
Diese Abbildung ist injektiv. Denn seien $x,y \in N_{m+1}$ beliebig mit $f'(x) = f'(y)$. Daraus folgt $f(x) = f'(x) = f'(y) = f(y)$, also $f(x) = f(y)$ und, mit der Injektivät von f, dass x=y.

Die Abbildung f' ist aufgrund der Injektivität von f ebenso wohldefiniert.
Frage: Wie könnte man die Wohldefiniertheit beweisen?

Definiere nun die Bijektion g: $N_{m+1} \backslash \{f(m+2)\} \to N_{m}$

$g(x) =
\begin{cases}
x & \text{für } 1 \le x < f(m+2) \\
x-1 & \text{für } m+1 \ge x > f(m+2)
\end{cases}$.

Damit ist die Abbildung $g \circ f: N_{m+1} \to N_{m}$ injektiv, da die Verkettung von injektiven Abbildungen wieder injektiv ist, was einen Widerspruch zur Induktionsannahme darstellt.
Folglich ist das Lemma bewiesen.


Korollar: Sei nun $n > m $. Angenommen, die Funktion $h: N_{n} \to N_{m}$ wäre injektiv. Wegen $n > m$ ist $n \ge m + 1$ und folglich die Inklusion i: $N_{m+1} \subset N_{n}$ injektiv.

Laut Annahme ist ferner auch die Inklusion f $N_{n} \to N_{m}$ injektiv.
Also wäre auch die Komposition $f \circ i, N_{m+1} \to N_{m}$ injektiv im Widerspruch zum bewiesenen Lemma.
Folglich war die Behauptung falsch und $N_{n} \to N_{m}$ ist nicht injektiv.



Um nun damit schlussendlich die Aussage zu beweisen:
Sei für $n \in \IN: N_{n} = \{m \in \IN: m \le n\}.$

Zu zeigen ist, dass wenn eine bijektive Abbildung $N_{n} \to N_{\tilde{n}}$ existiert, daraus $n = \tilde{n}$ folgt.

Angenommen $n > \tilde{n}$. Dies wäre nach dem Korollar ein Widerspruch zur vorausgesetzten Injektivität. Analog $n < \tilde{n}$.

=> $n = \tilde{n}$.

- - - - - - - - - -



Wäre der Beweis so in Ordnung?
Und wie würdet ihr die Wohldefiniertheit von f' beweisen?


Wie immer wäre ich euch für jede Antwort sehr dankbar!

Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.64, eingetragen 2020-03-18

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}}\)
2020-03-18 00:11 - X3nion in Beitrag No. 63 schreibt:
Frage: Wie könnte man die Wohldefiniertheit beweisen?
Kannst du aufschreiben, was für die Wohldefiniertheit zu zeigen ist? Der Beweis ergibt sich dann fast automatisch.

Ansonsten ist der Beweis in Ordnung. Du könntest noch beweisen, dass $g$ bijektiv (injektiv würde ausreichen) ist.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.65, vom Themenstarter, eingetragen 2020-03-19


Hi Nuramon,

vielen Dank dir, dass du nach so langer Zeit bereit bist, das Thema mit mir zu Ende zu führen! 🙂

Zeige nun also die Injektivität von

g: $N_{m+1} \backslash \{f(m+2)\} \to N_{m}$

$g(x): =
\begin{cases}
x & \text{für } 1 \le x < f(m+2) \\
x-1 & \text{für } m+1 \ge x > f(m+2)
\end{cases}$.


Seien dafür $x,y \in N_{m+1} \backslash \{f(m+2)\}$ beliebig mit
$g(x) = g(y)$, wobei $g(x) = g(y)$ aufgrund Definition von g nur eintreten kann, falls die folgenden 2 Fälle auftreten:

1. Fall: Es gilt sowohl $1 \le x < f(m+2)$ als auch $1 \le y < f(m+2)$

Damit folgt $g(x) = x$ und $g(y) = y$ und somit $x=y$

2. Fall: Es gilt sowohl $m+1 \ge x > f(m+2)$ als auch $m+1 \ge y > f(m+2)$. Damit folgt $g(x) = x-1$ und $g(y) = y-1$ und somit insgesamt $x-1 = y-1 \iff x=y$


Zeige nun die Surjektivität von g.  

Sei dazu $y = N_{m}$ beliebig

1. Fall: $1 \le y < f(m+2)$. Dann ist $x=y$ für ein $1 \le x < f(m+2)$. Nach Definition von g folgt daraus x = g(x) = y.

2. Fall: $f(m+2) \le y \le m$. Dann ist $y = x-1$ für ein $f(m+2) < x < m+1$, und wiederum nach Definition von g: $y = x-1 = g(x)$.




Zur Wohldefiniertheit von f': Zu zeigen ist, dass für alle $N_{m+1}$ genau ein $y \in N_{m+1}\setminus\{f(m+2)\}$ existiert mit $f'(x) = y$.

Laut Voraussetzung ist die Abbildung f: $N_{m+2} \to N_{m+1}$ wohldefiniert und injektiv.

Aufgrund der Injektivität von f existiert kein $x' \in N_{m+1}$ mit $f(x') = f(m+2)$.

Falls f' nicht wohldefiniert ist, so gäbe es mindestens ein $x \in N_{m+1}$, für welches kein oder mehr als zwei $y \in N_{m+1} \setminus \{f(m+2)\}$ existieren mit $f'(x) = y$.

Wähle solch ein x.
Betrachte den Fall, dass es kein $y \in N_{m+1} \setminus \{f(m+2)\}$ gibt mit $f'(x) = y$.
Das würde bedeuten, dass $f(x) = f(m+2)$, im Widerspruch zur vorausgesetzten Injektivität von f.
Betrachte den Fall, dass es mindestens zwei $y \in N_{m+1} \setminus \{f(m+2)\}$ gibt mit $f'(x) = y$. Dies ist ein Widerspruch zur Wohldefiniertheit von f.




Würde das so passen? Oder geht die Wohldefiniertheit einfacher? 😄

Viele Grüße,
X3nion







Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.66, eingetragen 2020-03-19

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}}\)
2020-03-19 00:47 - X3nion in Beitrag No. 65 schreibt:
Seien dafür $x,y \in N_{m+1} \backslash \{f(m+2)\}$ beliebig mit
$g(x) = g(y)$, wobei $g(x) = g(y)$ aufgrund Definition von g nur eintreten kann, falls die folgenden 2 Fälle auftreten:

1. Fall: Es gilt sowohl $1 \le x < f(m+2)$ als auch $1 \le y < f(m+2)$

Damit folgt $g(x) = x$ und $g(y) = y$ und somit $x=y$

2. Fall: Es gilt sowohl $m+1 \ge x > f(m+2)$ als auch $m+1 \ge y > f(m+2)$. Damit folgt $g(x) = x-1$ und $g(y) = y-1$ und somit insgesamt $x-1 = y-1 \iff x=y$

Den Fall $1\leq x < f(m+2)$ und $m+1\geq y > f(m+2)$ (bzw. andersherum) solltest du auch noch betrachten.


Zeige nun die Surjektivität von g.  

Sei dazu $y = N_{m}$ beliebig
Du meinst $y\in N_m$. Bis auf diesen Tippfehler ist der Surjektivitätsbeweis in Ordnung.

Dein Beweis für die Wohldefiniertheit von $f'$ passt auch. Meiner Meinung nach hätte es dort aber auch schon gereicht zu zeigen, dass für $x \in N_{m+1}$ gilt $f(x)\in N_{m+1}\setminus\{f(m+2)\}$.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.67, vom Themenstarter, eingetragen 2020-03-19




Den Fall $1\leq x < f(m+2)$ und $m+1\geq y > f(m+2)$ (bzw. andersherum) solltest du auch noch betrachten.

Hmm aber der Fall kann ja gar nicht auftreten, da ja in diesem Falle bereits $g(x) = g(y)$ aufgrund der Definition von g ja gar nicht eintreten kann? x kann ja maximal den Wert $x = f(m+2) - 1$ annehmen und y minimal den Wert $y = f(m+2) + 1$.
Damit wäre g(x) = f(m+2) - 1 und g(y) = f(m+2) + 1 - 1 = f(m+2), also g(x) = g(y) $\iff$ -1 = 0.

Bzw. nehmen wir einmal $g(x) = g(y)$ respektive $x = y-1$ an. Daraus können wir doch nicht x=y folgern?



Du meinst $y\in N_m$. Bis auf diesen Tippfehler ist der Surjektivitätsbeweis in Ordnung.

Dein Beweis für die Wohldefiniertheit von $f'$ passt auch. Meiner Meinung nach hätte es dort aber auch schon gereicht zu zeigen, dass für $x \in N_{m+1}$ gilt $f(x)\in N_{m+1}\setminus\{f(m+2)\}$.

Ahh okay, ja das stimmt!

Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.68, eingetragen 2020-03-19

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}}\)
2020-03-19 14:15 - X3nion in Beitrag No. 67 schreibt:
Hmm aber der Fall kann ja gar nicht auftreten, da ja in diesem Falle bereits $g(x) = g(y)$ aufgrund der Definition von g ja gar nicht eintreten kann?
Ja, der Fall führt wenn man ihn sich genauer ansieht zu einem Widerspruch. Von vornherein weiß man das aber noch nicht, also kannst du ihn nicht einfach ausschließen.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.69, vom Themenstarter, eingetragen 2020-03-19


Ja, der Fall führt wenn man ihn sich genauer ansieht zu einem Widerspruch. Von vornherein weiß man das aber noch nicht, also kannst du ihn nicht einfach ausschließen.

Ja da hast du Recht!

Seien nun also $x,y \in N_{m+1}$ beliebig, ohne Einschränkung $1\leq x < f(m+2)$ und $m+1\geq y > f(m+2)$, mit $g(x) = g(y) \iff x = y-1$. Es gilt $y > f(m+2)$, also $y-1 \ge f(m+2)$, allerdings auch $x < f(m+2)$ und somit $y-1 \ge f(m+2) > x$, ein Widerspruch zu $x = y-1$.
Damit kann der Fall $g(x) = g(y)$ gar nicht auftreten.

Soweit okay?

Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.70, eingetragen 2020-03-19


Ja.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.71, vom Themenstarter, eingetragen 2020-03-19


Okay alles klar 😄

Dann war da noch die Teilaufgabe 2, die wir noch intensiv behandelt hatten.


2) Für zwei beliebige endliche Mengen M,N gilt: Es ist #M = #N genau dann, wenn für jede Abbildung $f: M \to N$ gilt, dass f injektiv $\iff$ f surjektiv.

Beweis:

Sei $\#M=m$ und $\#N=n$ und seien $\varphi: M\to N_m$ und $\psi: N\to N_n$ Bijektionen.
Ist $f:M\to N$ irgendeine Abbildung, dann sei $f': N_m\to N_n$ definiert als $f':=\psi\circ f \circ \varphi^{-1}$.
Nun gilt: $f$ ist injektiv bzw. surjektiv genau dann, wenn $f'$ injektiv bzw. surjektiv ist.
Müsste man das noch explizit beweisen, oder ist das an und für sich klar?


Hinrichtung:
Nehme an, dass $m=n$ ist.

"=>" Sei $f': N_{m} \to N_{m}$ eine injektive Abbildung. Angenommen, f' wäre nicht surjektiv. Dann existiert ein $y \in N_{m}$, für das kein $x \in N_{m}$ existiert mit $f(x) = y$.
Wähle solch ein y.
Definiere nun die Abbildung $f'' : N_{m+1} \to N_{m}$
$f'(x):= \begin{cases}
f(x) & \text{ für } x \in N_{m} \\
y & \text{ für } x = m+1
\end{cases}$

Nach Definition ist $f''$ injektiv. Nach vorausgegangenem Lemma kann es aber keine solche Injektion geben. Insbesondere muss dadurch $f'$ bereits surjektiv gewesen sein, woraus die Surjektivität von f folgt.

"<="

- - - - - - - - - -

Zeige zunächst folgendes
Lemma 1: Sei $f: A \to B$ eine Abbildung.
Dann: f ist surjektiv $\iff f$ hat eine Rechtsinverse g. Dabei heißt $g: B \to A$ ist Rechtsinverse zu f, falls $f \circ g = id_{B}$.

Sei zunächst einmal f surjektiv, also besitzt jedes $y \in B$ mindestens ein Urbild unter f. Nach dem Auswahlaxiom existiert eine Funktion $g: B \to A$, welche jedem $y \in B$ genau ein Urbild zuweist. Damit haben wir $f \circ g = id_{B}$.
Gelte umgekehrt $f \circ g = id_{B}$. Sei nun $b \in B$ beliebig. Definiere $a:=g(b)$. Damit ist $f(a) = f(g(b)) = id_{B}(b) = b$.

Zeige nun das
Lemma 2:
Seien $f:X\to Y, g: Y\to X$ Abbildungen. Gilt $g\circ f = id_X$, so ist $f$ injektiv und g surjektiv.

Zur Injektivität: seien $x,y \in X$ beliebig mit $f(x) = f(y)$. Dann gilt $g(f(x)) = g(f(y))$ und damit $x=y$, denn $g(f(x)) = id_{X}(x)$ und $g(f(y)) = id_{X}(y)$.

Zur Surjektivität: Sei $x \in X$ beliebig. Setze $y:= f(x) \in Y$. Damit ist $g(y) = g(f(x)) = id_{X}(x) = x$.

- - - - - - - - -


Nehme nun an, dass $f'$ surjektiv ist. Nach Lemma 1 hat $f'$ ein Rechtsinverses $g': N_m\to N_m$ mit $f'\circ g' = id_{N_m}$. Nach Lemma 2 ist $g'$ injektiv, und nach der Hinrichtung auch surjektiv, also bijektiv.

Wegen $f' \circ g' = id_{N_{m}}$, ist $f'=g'^{-1}$ das Inverse zu $g'$ und somit bijektiv.


Rückrichtung:

Angenommen $m \neq n$.

m > n : Definiere die Abbildung $f: M \to N$,
$f(x):= \begin{cases}
x & \text{ für } 1 \le x \le n \\
n & \text{ für } n < x \le m
\end{cases}$

f ist surjektiv, denn sein $y \in N$ beliebig. Dann gilt $y = x$ für ein $x$ mit $1 \le x \le n$. Also $x = f(x) = y$.
f ist nicht injektiv, weil zum Beispiel  $f(n) = f(n+1)$.

n > m . Definiere die Abbildung $f: M \to N$,
$f(x):= x$ für $1 \le x \le m$

Diese Abbildung ist nicht surjektiv, da zum Beispiel $m+1$ unter f kein Urbild besitzt. Jedoch ist f offensichtlich injektiv.





Würde das so passen? Würdest du das mit blau gekennzeichnete noch beweisen?

Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.72, eingetragen 2020-03-20

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}}\)
2020-03-19 23:58 - X3nion in Beitrag No. 71 schreibt:
Ist $f:M\to N$ irgendeine Abbildung, dann sei $f': N_m\to N_n$ definiert als $f':=\psi\circ f \circ \varphi^{-1}$.
Nun gilt: $f$ ist injektiv bzw. surjektiv genau dann, wenn $f'$ injektiv bzw. surjektiv ist.
Müsste man das noch explizit beweisen, oder ist das an und für sich klar?
Natürlich muss es bewiesen werden. Wenn dir der Beweis aber klar ist, dann liegt es in deinem eigenen Ermessen, ob es dir die Mühe wert ist ihn aufzuschreiben.

Die Hinrichtung passt. An einer Stelle hast du $f'$ statt $f''$ geschrieben.

Rückrichtung:
Bei der Rückrichtung hast du anscheinend angenommen, dass $M=N_m$ und $N=N_n$. Die Annahme kann man machen (vorausgesetzt dir ist klar warum), aber du solltest zumindest erwähnen, dass du dies tust.
Ansonsten passt alles.

\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.73, vom Themenstarter, eingetragen 2020-03-23


Hi Nuramon,

okay dann mache ich das mal zur Übung 😄


Beweise also: f ist injektiv bzw. surjektiv genau dann, wenn f′ injektiv bzw. surjektiv ist.

Beweis zur Injektivität:
"=>" Sei $f$ injektiv. Seien $x,y \in N_{m}$ beliebig mit $f'(x) = f'(y)$, also $\psi(f(\phi^{-1}(x))) = \psi(f(\phi^{-1}(y)))$.
Die Injektivität von $\psi$ liefert $f(\phi^{-1}(x)) = f(\phi^{-1}(y))$.
Injektivität von $f$ liefert $\phi^{-1}(x) = \phi^{-1}(y)$.
Injektivität von $\phi^{-1}$ liefert $x = y$.

"<=" Sei $f'$ injektiv. Angenommen, f wäre nicht injektiv. Dann existieren $x,y \in M$ mit $f(x) = f(y)$, aber $x \neq y$.
Wähle solche $x,y$. Aufgrund der Bijektivität von $\phi^{-1}$ existiert genau ein $a \in N_{m}$ mit $\phi^{-1}(a) = x$ und genau ein $b \in N_{m}$ mit $\phi^{-1}(b) = y$. Insbesondere ist $a \neq b$.
Es folgt nun $\psi(f(x)) = \psi(f(y)) \iff \psi(f(\phi^{-1}(a))) = \psi(f(\phi^{-1}(b))) \iff f'(a) = f'(b)$. Die Injektivität von f' liefert nun $a = b$, Widerspruch! Also muss doch $f$ injektiv sein.

Beweis zur Surjektivität:
"=>" Sei f surjektiv. Sei nun $d \in N_{n}$ beliebig.
Aufgrund der Surjektivität von $\psi$ existiert ein $c \in N$ mit $\psi(c) = d$.
Aufgrund der Surjektivität von $f$ existiert ein $b \in M$ mit $f(b) = c$.
Aufgrund der Surjektivität von $\phi^{-1}$ existiert ein $a \in N_{m}$ mit $\phi^{-1}(a) = b$.

Insgesamt existiert also ein $a \in N_{m}$ mit $\psi(f(\phi^{-1}(a))) = f'(a)$.
Also ist $f'$ surjektiv.

"<=" Sei f' surjektiv. Angenommen $f$ ist nicht surjektiv. Dann existiert ein $c \in N$, sodass kein $b \in M$ existiert mit $f(b) = c$. Das bedeutet aber, für alle $b \in M$ gilt $f(b) \neq c$.

Wähle solch ein $c \in N$.
Es folgt, dass genau ein $d \in N_{n}$ existiert mit $\psi(c) = d$.
Mit der Surjektivität von $f'$ existiert nun ein $a \in N_{m}$ mit $f'(a) = \psi(f(\phi^{-1}(a))) = d$.
Es folgt nun $\phi^{-1}(a) = \tilde{b}$ für genau ein $\tilde{b} \in M$.

Also haben wir $\psi(f(\phi^{-1}(a))) = d \iff \psi(f(\tilde{b})) = \psi(c)$. Die Injektivität von $\psi$ liefert $f(\tilde{b}) = c$.
Das steht aber im Widerspruch dazu, dass kein $b \in M$ existiert mit $f(b) = c$.
Also muss $f$ doch surjektiv gewesen sein.

- - - - - - - - - - -

Passt das so?

- - - - - - - - - - - -

Zur Rückrichtung:

Wir haben jeweils Bijektionen $\phi^{-1}: N_{m} \to M$ und $\psi: N \to N_{n}$, bzw. die Bijektion $\phi: M \to N_{k}$. Da $N_{m}$ und M gleich viele Elemente enthalten, gilt $M = N_{m}$. Analog gilt $N = N_{n}$

Nun ist $f$ genau dann injektiv / surjektiv, wenn f' injektiv / surjektiv ist. Damit genügt es, die Rückimplikation für eine beliebige Abbildung $f': N_{m} \to N_{n}$ zu zeigen.



Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2043
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.74, eingetragen 2020-03-23

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}}\)
2020-03-23 01:23 - X3nion in Beitrag No. 73 schreibt:
Beweise also: f ist injektiv bzw. surjektiv genau dann, wenn f′ injektiv bzw. surjektiv ist.
[...]

Passt das so?
Ja.


Zur Rückrichtung:

Wir haben jeweils Bijektionen $\phi^{-1}: N_{m} \to M$ und $\psi: N \to N_{n}$, bzw. die Bijektion $\phi: M \to N_{k}$. Da $N_{m}$ und M gleich viele Elemente enthalten, gilt $M = N_{m}$. Analog gilt $N = N_{n}$
Die rot markierten Sätze sind falsch. Lass die einfach weg, dann sollte alles passen.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 605
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.75, vom Themenstarter, eingetragen 2020-03-26


Hey Nuramon,

vielen vielen Dank für deine so tatkräftige Unterstützung und deinen langen Atem!
Du hast mir sehr geholfen 😄

Viele Grüße und bleib gesund,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion hat die Antworten auf ihre/seine Frage gesehen.
X3nion hat selbst das Ok-Häkchen gesetzt.
Seite 2Gehe zur Seite: 1 | 2  
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]