Eine Bijektion aus 2*Injektion beweisen

25.09.2010, 13:15

Cosmo Lavish

Auf diesen Beitrag antworten »

Eine Bijektion aus 2*Injektion beweisen

Die Aufgabe lautet:
Seien A und B beliebige Mengen. $\begin{eqnarray*} f: A \rightarrow B \end{eqnarray*}$ sei injektiv. $\begin{eqnarray*} g: B \rightarrow A \end{eqnarray*}$ sei injektiv.
Zeige: Es gibt eine Bijektion von $\begin{eqnarray*} f: A \rightarrow B \end{eqnarray*}$

Mein Lösungsansatz wäre:

Ich gehe hiervon aus: "Zwei endliche Mengen $\begin{eqnarray*} A , B \end{eqnarray*}$ "gleich mächtig" heißen, wenn es eine bijektive Abbildung $\begin{eqnarray*} f: A \rightarrow B \end{eqnarray*}$ gibt bzw. wenn jedem $\begin{eqnarray*} a \in A \end{eqnarray*}$ genau ein $\begin{eqnarray*} b \in B \end{eqnarray*}$ zugeordnet werden kann."

...und folgere daraus, dass eine Bijektion äquivalent mit der "Gleichmächtigkeit" von zwei Mengen ist.
(...hier ist das Problem, da ich nicht weiß, ob aus der Bijektion die "Gleichmächtigkeit" nur folgt oder ob beide äquivalent sind...)

$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ Ich muss nur noch beweisen, dass $\begin{eqnarray*} \left |A \right | = \left |B \right | \end{eqnarray*}$

Mein Beweis:
Annahme:

1. $\begin{eqnarray*} f: B \rightarrow A \end{eqnarray*}$ ist injektiv.
d.h. für jedes $\begin{eqnarray*} b \in B \end{eqnarray*}$ gibt es höchstens ein $\begin{eqnarray*} a \in A \end{eqnarray*}$ , es folgt: $\begin{eqnarray*} A \subseteq B \end{eqnarray*}$

2. $\begin{eqnarray*} g: A \rightarrow A \end{eqnarray*}$ ist injektiv.
d.h. für jedes $\begin{eqnarray*} a \in A \end{eqnarray*}$ gibt es höchstens ein $\begin{eqnarray*} b \in B \end{eqnarray*}$ , es folgt: $\begin{eqnarray*} B \subseteq A \end{eqnarray*}$

$\begin{eqnarray*} A \subseteq B \wedge B \subseteq A \Leftrightarrow A \subset B \Leftrightarrow \left |A \right | = \left |B \right | \Leftrightarrow f: A \rightarrow B \end{eqnarray*}$ ist bijektiv

Ist der Beweis richtig? Wenn nein, wo habe ich Fehler gemacht?

Schonmal vielen Dank für die Hilfe!

25.09.2010, 13:20

Airblader

Auf diesen Beitrag antworten »

Wieso sollten A und B Teilmengen voneinander sein? Nimm doch mal A = {1,2} und B = {3,4}. Die sind gleichmächtig und du kannst sie bijektiv aufeinander abbilden, aber die sind keineswegs Teilmengen voneinander.

Im Übrigen hat deine Idee auch schon im Kern einen Knackpunkt: Was ist mit unendlichen Mengen?

air

25.09.2010, 13:27

tmo

Auf diesen Beitrag antworten »

Du verwechselst hier die Teilmengenrelation mit der Mächtigkeitsrelation. Die haben nichts miteinander zu tun. Der Beweis dieses Satzes (Äquivalenzsatz von Schröder-Bernstein) befindet sich z.b. hier auf Seite 13.

An der Stelle "Man überlegt sich nun" solltest du halt mal überlegen smile

smile

25.09.2010, 13:28

Cosmo Lavish

Auf diesen Beitrag antworten »

Hmm... hast recht... also kann ich nicht Über die Mächtigkeit gehen...

Hast du vlt eine Idee, was ich als Ansatz nehmen könnte? Und was für eine Art von Beweisführung hier sinnvoll wäre?
Ich mach das nämlich erst seit 4 Tagen...

25.09.2010, 13:29

Cosmo Lavish

Auf diesen Beitrag antworten »

Danke für das PDF-File... ich schaus mir mal an...

25.09.2010, 13:33

Airblader

Auf diesen Beitrag antworten »

Darf ich mal fragen, ob du im Mathe-Vorkurs von Hr. Röhrl oder Hr. Adamek an der Uni Stuttgart bist? Big Laugh

Big Laugh

air

Anzeige

25.09.2010, 13:47

Cosmo Lavish

Auf diesen Beitrag antworten »

Röhrl

Big Laugh

Bist du auch an der Uni Stuttgart?

25.09.2010, 13:55

Airblader

Auf diesen Beitrag antworten »

Ja, aber ich komme jetzt ins dritte Semester. Ich war Montag und Mittwoch aber spaßeshalber auch in der Röhrl-Vorlesung. Augenzwinkern

Augenzwinkern

Was studierst du denn ab kommendem Wintersemester?

air

25.09.2010, 18:44

Cosmo Lavish

Auf diesen Beitrag antworten »

Ich nehm mal an das selbe wie du...^^
Vlt sehn wir uns ja dann mal in der Fachschaft.

Hmm... habe mir mal den Beweis angeschaut... das geht also doch über die Mächtigkeit. Also war mein Beweisansatz wohl doch nicht ganz falsch.

Wenn ich unten im Beweis so argumentiere, also die "echte Teilmenge" einfach weglasse:
$\begin{eqnarray*} A \subseteq B \wedge B \subseteq A \Leftrightarrow \left | A \right | = \left | B \right | \Leftrightarrow f: A \rightarrow B \end{eqnarray*}$ ist injektiv.
...dann wäre der Beweis doch wenigstens für die endlichen Mengen richtig, oder?

Was unendliche Mengen angeht, fällt mir gerade nichts ein, was ich als Ansatz nehmen könnte, da ich in der Schule gelernt habe, dass $\begin{eqnarray*} \infty \end{eqnarray*}$ nicht immer gleich $\begin{eqnarray*} \infty \end{eqnarray*}$ ist, sondern auch verschieden unendlich sein kann...

Dazu hätte ich jetzt zwei Fragen:

Wäre es richtig zu behaupten, dass wenn die Abbilder $\begin{eqnarray*} g \end{eqnarray*}$ und $\begin{eqnarray*} f \end{eqnarray*}$ beide injektiv sind, dass dann eine unendliche Menge wie eine endliche zu Behandeln ist?

Und wenn nicht, soll ich dann versuchen zu beweisen, dass $\begin{eqnarray*} f \end{eqnarray*}$ in diesem Fall auch surjektiv sein muss, da dadurch eine Bijektion bewiesen wäre?

Welcher dieser beiden Ansätze ist richtig?

25.09.2010, 19:05

Airblader

Auf diesen Beitrag antworten »

Oh, du studierst sogar Mathe? Das is ja cool. smile

smile

Deine "Korrektur" stimmt immer noch nicht.
Nochmal: Es hat nichts mit Teilmengen zu tun! Was du gerade mit Teilmenge meinst ist eher eine Ungleichung an die Mächtigkeiten. Du meinst nicht $\begin{eqnarray*} A \subseteq B \end{eqnarray*}$ , sondern $\begin{eqnarray*} |A| \leq |B| \end{eqnarray*}$ .

Zitat:

Wäre es richtig zu behaupten, dass wenn die Abbilder $\begin{eqnarray*} f \end{eqnarray*}$ und $\begin{eqnarray*} g \end{eqnarray*}$ beide injektiv sind, dass dann eine unendliche Menge wie eine endliche zu Behandeln ist?

In der Mathematik behaupten wir mal gar nichts ohne Begründung und Beweis. Und Unendlichkeiten einfach auf Endlichkeiten reduzieren ist eine gefährliche Sache. Augenzwinkern

Augenzwinkern

Zitat:

Und wenn nicht, soll ich dann versuchen zu beweisen, dass $\begin{eqnarray*} f \end{eqnarray*}$ in diesem Fall auch surjektiv sein muss, da dadurch eine Bijektion bewiesen wäre?

Niemand hat behauptet, dass f dann bijektiv sein muss. Die Behauptung ist, dass es irgendeine bijektive Abbildung zwischen A und B gibt. Augenzwinkern

Augenzwinkern

Und diese Bijektion konstruiert man sich dann. Zugegebenermaßen ist das nicht gerade eine Sache für einen Vorkurs, weshalb ich stark vermute, dass ihr euch auf endliche Mengen beschränken sollt, selbst wenn es nicht so in der Aufgabe steht.
Eine Konstruktionsskizze für den Beweis findest du, wenn du interessiert bist, hier: http://de.wikipedia.org/wiki/Cantor-Bern...orem#Beweisidee

Zugegeben, darüber muss man aber etwas nachdenken. Kann man aber verstehen. Ich erinnere mich noch sehr gut daran, als ich es machen musste. Herrje, war ich stolz, als ich es verstanden habe. Big Laugh

Big Laugh

air

25.09.2010, 19:29

Cosmo Lavish

Auf diesen Beitrag antworten »

Ja isses wirklich. Aber auch kompliziert...

Zitat:

Was du gerade mit Teilmenge meinst ist eher eine Ungleichung an die Mächtigkeiten. Du meinst nicht $\begin{eqnarray*} A \subseteq B \end{eqnarray*}$ , sondern $\begin{eqnarray*} |A| \leq |B| \end{eqnarray*}$ .

Oh... stimmt... hatte einfach noch den "\subseteq" Befehl im Kopf... das ist heute mein erstes mal mit Latech... Augenzwinkern

Augenzwinkern

Dann hab ich wenigstens die Hälfte vom Beweis gemacht...

Das auf Wikipedia ist wirklich ziemlich kompliziert... ich werd es mal auf morgen verschieben... jetzt geh ich erstmal in "The Expendables"...

Zitat:

Zugegebenermaßen ist das nicht gerade eine Sache für einen Vorkurs, weshalb ich stark vermute, dass ihr euch auf endliche Mengen beschränken sollt, selbst wenn es nicht so in der Aufgabe steht.

Es ist eine Bonusaufgabe... gehört so gesehen also nicht zum Vorkurs...

Und nochmal vielen Dank für deine Hilfe!

"Abbildungen und Funktionen I+II" ist echt intressant gewesen! Auch wenn ichs mir vlt früher hätte anschauen sollen...

25.09.2010, 19:34

Airblader

Auf diesen Beitrag antworten »

Wir hatten den Beweis von Schröder-Bernstein auch recht am Anfang als "Schockaufgabe", bzw. eben als Fleißaufgabe um zu sehen, wer sich trotz der Komplexität eines Studienanfängers damit auseinandersetzt.
Lohnt sich jedenfalls definitiv. Am Ende ist es dann plötzlich gar nicht mehr so kompliziert und man hat doch schon was gelernt!

Als "Hälfte" würde ich den endlichen Fall nicht bezeichnen. Streng genommen ist der recht langweilig. Augenzwinkern

Augenzwinkern

Und es heißt "Latex", nicht "Latech". Jetzt aber genug der Korrekturen. Big Laugh

Big Laugh

Erstmal viel Spaß im Kino Freude

Freude

air

25.09.2010, 19:40

Cosmo Lavish

Auf diesen Beitrag antworten »

Tut mir Leid, aber jetzt muss ich dich leider korrigieren...

Es heißt Latech bzw Tech, zumindest wird es so ausgesprochen. Denn eigentlich wird es LateX bzw. TeX geschrieben, wobei das "X" kein x sondern ein griechisches "Chi" ist. Und das wird "ch" ausgesprochen. Das weiß ich nach 5 Jahren Altgriechischuntericht und nem Graecum... smile

smile

Laut Wikipedia: LaTeX [ÈlaÐt[ç] (oder [ÈlaÐt[Ç])

...ok... Ich habe den Fall 1: "Die beiden beliebigen Mengen seien endlich" bewiesen...^^

25.09.2010, 19:43

Airblader

Auf diesen Beitrag antworten »

Ich weiß wie es gesprochen wird. Aber geschrieben wird es nunmal $\begin{eqnarray*} \text{\LaTeX} \end{eqnarray*}$ Augenzwinkern

Augenzwinkern

air

28.09.2010, 22:30

Cosmo Lavish

Auf diesen Beitrag antworten »

Hey

ich hab meine Lösung gestern mal vorgestellt, zusammen mit einer anderen, die die selbe Idee hatte...

Die Lösung an sich ist zwar richtig, aber nicht vollständig. Wir sollen jetzt noch die andere "Hälfte" beweisen. Als Tipp haben wir bekommen, dass wir uns nicht so auf $\begin{eqnarray*} \left |A \right | = \left |B \right | \end{eqnarray*}$ beschränken sollen, sondern über Relationen gehen sollen... (Dieses Thema finde ich an sich schon sehr verwirrend...) und dass wir (war ja klar^^) abstrakter denken müssen...
Heute haben wir uns dann (inzwischen zu dritt) zusammengesetzt, aber nicht wirklich etwas herausgefunden.
Am Schluss haben wir den Ansatz, dass wir es über Mächtigkeit und Abzählbarkeit machen müssen...

Ich hab die Wikipediaartikel über die beiden Themen mal ganz grob überflogen und ein / zwei Scripte durchgeschaut... Was ich rausgefunden habe ist:

-Wenn ich beweisen soll, dass $\begin{eqnarray*} f: A \rightarrow B \end{eqnarray*}$ bijektiv ist, dann heißt das nicht, dass es nicht andere Abbildungen $\begin{eqnarray*} A \rightarrow B \end{eqnarray*}$ gibt, bei denen das anders ist...

-Eine Relation R zwischen $\begin{eqnarray*} A \end{eqnarray*}$ und $\begin{eqnarray*} B \end{eqnarray*}$ ist $\begin{eqnarray*} R \subseteq A \times B \end{eqnarray*}$ also kann ein a mehreren b zugeordnet sein und andersrum...

-Ist A gleichmächtig zu B und f eine Bijektion zwischen A und B, dann ist auch die Umkehrfunktion von f eine Bijektion, also ist auch B gleichmächtig zu A. Endliche Mengen sind genau dann gleichmächtig, wenn sie gleich viele Elemente haben. Unendliche Mengen sind Mengen, die zu sich gleichmächtige echte Teilmengen besitzen. (laut Wikipedia)
...Teilmengen von unendlichen Mengen scheinen bei diesem Beweis eine wichtige Rolle zu spielen. Genau verstanden habe ich das aber noch nicht...

-Ich hab da so ein Gefühl, dass man das dann nur für abzählbare Mengen beweisen kann...
$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ ich muss die Abzählbarkeit beweisen, bzw dass für abzählbare unendliche Mengen die Bijektion gilt...

Wo liege ich richtig? Hab ich bis dahin irgendwelche Fehler und vor allem was davon soll ich mir genauer anschauen um den Beweis richtig führen zu können? Gibt es evtl irgendwelche Sätze, die ich dazu verwenden kann?
Die Aufgabe hat sich so langsam zu einer von denen entwickelt, die ich einfach verstehen will...^^

Zitat:

Aber geschrieben wird es nunmal $\begin{eqnarray*} \text{\LaTeX} \end{eqnarray*}$ Augenzwinkern

air

klar... hast natürlich recht!
Btw. ich habe Ubuntu auf meinem Netbook (wenn nötig auch WinXP, aber ungern) und habe mir Kile installiert, ein Latexprogramm... damit komme ich allerdings noch nicht wirklich klar, da Latex viel mehr kann als ich warscheinlich gerade brauche... Dann hab ich mich mal bei Google schlau gemacht und nach Tutorials gesucht... aber leider keine gefunden... hast du evtl Ahnung, wo es dazu ne gute Einführung gibt?

Danke für die tolle Hilfe bis jetzt!

28.09.2010, 23:22

Airblader

Auf diesen Beitrag antworten »

Zunächst: Nein, der Satz gilt für beliebige unendliche Mengen, auch für überabzählbare wie z.B. $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ .

Ansonsten ist mir nicht ganz klar, auf welchen Beweis du nun rauswillst. Auf den im verlinkten wikipedia-Artikel? Ich finde den recht gut, da er zwar etwa komplex für den Einsteiger ist und Mühe verlangt, aber eigentlich scöhn strukturiert ist und gut verstanden werden kann.
Es gibt aber ausformulierte Versionen davon im Internet. Die würde ich mir anschauen. Niemand velrangt hier, dass du das selbst beweist, was wäre Wahnsinn. Aber verstehen solltest du ihn.

Hier mal ein paar Links zu ausführlichen Erklärungen:
matheplanet - ausführlicher Beweis #1
matheplanet - ausführlicher Beweis #2
mathepedia

Die gehen immer einen Tick unterschiedlich vor, aber die Idee ist stets die selbe. Im Übrigen kannst du hier sehen, wie ich mich damals damit rumgeschlagen habe. Augenzwinkern

Augenzwinkern

(Edit: Herrje, war das eine bescheuerte Frage von mir damals ... Big Laugh

Big Laugh

) Ich habe den matheplanet-Link #2 (s.o.) verwendet und empfehle dir diesen auch. Er ist sehr schön verständlich! (Ein unbekannter Begriff ist ja schnell nachgeschlagen)

Zum LaTeX: Es gibt hier im Board Workshops smile

smile

air

03.10.2010, 12:15

Cosmo Lavish

Auf diesen Beitrag antworten »

Hey,

Das kommt jetzt vielleicht ein bisschen spät, aber die Ereignisse von Donnerstag und Freitag sind mir irgendwie dazwischen gekommen... Ich war in den letzten drei Tagen 16 Stunden im Park... *immernochmüde*

Auf jeden Fall vielen Dank für die Links... sie waren sehr hilfreich!
Allerdings habe ich das Gefühl, dass noch einige Lemmas zwischen mir und dem entgültigen Verständniss stehen, die ich einfach noch nicht gelernt habe... ein paar kleine Punkte sind noch unklar... ich werde mir alles aber einfach nochmal gründlich durchlesen...

Glg

11.10.2010, 02:47

akechi90

Auf diesen Beitrag antworten »

Hallo Cosmo Lavish,

Kann es sein, dass ich dein Tutor bin? Augenzwinkern

Augenzwinkern

Liebe Grüße,
Carsten

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »