Bijektion beweisen < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:38 Fr 08.11.2013 | | Autor: | Alex1993 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
Ich habe mir für dieses Wochenende vorgenommen Mathe zu üben und habe mir daher einige Übungsblätter (leider ohne Lösung) ausdrucken lassen. Seit Donnerstag habe ich versucht diese zu bearbeiten. Bei einigen Aufgaben ist mir dies allerdings nicht gelungen. Vielleicht könnt ihr mir hier weiterhelfen?:
Aufgabe:
Es existiert eine Menge X mit k Elementen und eine Menge Y mit l Elementen. Dazu gebe es 2 injektive Abbildungen f:X-->Y und g:Y-->X. Zeigen sie (ohne auf Cantor oder Bernstein zu verweisen ) , dass es eine Bijektion zwischen X und Y gibt...
Also eine Bijektion heißt ja gleichzeitig das 2 Mengen gleichmächtig sind. Das bedeuten, dass man annimmt, dass X und Y gleichmächtig sind. Doch wie beweise ich dies mithilfe der 2 injektiven Abbildungen. Es gilt doch dann auch zu beweisen, dass k=l ist oder?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:56 Fr 08.11.2013 | | Autor: | Marcel |
Hallo,
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt
> Ich habe mir für dieses Wochenende vorgenommen Mathe zu
> üben und habe mir daher einige Übungsblätter (leider
> ohne Lösung) ausdrucken lassen. Seit Donnerstag habe ich
> versucht diese zu bearbeiten. Bei einigen Aufgaben ist mir
> dies allerdings nicht gelungen. Vielleicht könnt ihr mir
> hier weiterhelfen?:
> Aufgabe:
> Es existiert eine Menge X mit k Elementen und eine Menge Y
> mit l Elementen. Dazu gebe es 2 injektive Abbildungen
> f:X-->Y und g:Y-->X. Zeigen sie (ohne auf Cantor oder
> Bernstein zu verweisen ) , dass es eine Bijektion zwischen
> X und Y gibt...
>
> Also eine Bijektion heißt ja gleichzeitig das 2 Mengen
> gleichmächtig sind. Das bedeuten, dass man annimmt, dass X
> und Y gleichmächtig sind. Doch wie beweise ich dies
> mithilfe der 2 injektiven Abbildungen. Es gilt doch dann
> auch zu beweisen, dass k=l ist oder?
ja, das sollte insbesondere ein Ergebnis des Beweises sein. Ich weiß aber
auch nicht, warum ihr den Satz nicht verwenden dürft. Da bleibt einem ja
fast nichts anderes über, als den Beweis dés Satzes zu imitieren, oder
selbst eine solche Bijektion anzugeben. (Wir werden hier wohl letzteres
im Endeffekt machen!)
Ich meine, der Gedanke ist einfach:
Wenn es eine Injektion $A [mm] \to [/mm] B$ gibt, muss [mm] $B\,$ [/mm] "mehr Elemente als [mm] $A\,$" [/mm] haben.
Grobgesagt: Man kann mit der Injektion [mm] "$A\,$ [/mm] in [mm] $B\,$ [/mm] wiederfinden."
Damit klarer wird, was ich meine:
Wenn Du [mm] $A=\{1,2,3\}$ [/mm] und [mm] $B=\{0,Apfel,Birne,\text{Käse},Tomate\}$ [/mm] hast, dann kannst
Du $f [mm] \colon [/mm] A [mm] \to [/mm] B$ mit [mm] $f(1)=0\,,$ [/mm] $f(2)=Birne$ und $f(3)=Tomate$ angeben, diese Fkt. $f$ ist
injektiv. Du findest [mm] $A\,$ [/mm] in [mm] $B\,$ [/mm] wieder - die Elemente heißen dann nur anders,
nicht mehr [mm] $1,2,3\,,$ [/mm] sondern $0, Birne, [mm] Tomate\,.$
[/mm]
(Kurz: Wenn man die Elemente in A umbenennt, findet man sie in B
wieder - und zwar ohne Verlust!)
Umgekehrt ist klar: Wenn es eine Injektion $B [mm] \to [/mm] A$ gibt, dann "finde ich auch
[mm] $B\,$ [/mm] in [mm] $A\,$ [/mm] wieder".
Was Du jetzt machen kannst - denn es geht ja um endliche Mengen:
Seien $A,B$ wie in der Aufgabe, also beides endliche Mengen. Sei [mm] $k:=|A|\,$ [/mm] und
[mm] $\ell:=|B|\,.$ [/mm] Zudem gebe es eine Injektion $A [mm] \to [/mm] B$ und auch eine Injektion
$B [mm] \to A\,.$
[/mm]
Jetzt zeige zuerst: Es muss [mm] $k=\ell$ [/mm] sein. Das machst Du in 2 Schritten:
1. Schritt: Beweise, dass aus der Existenz einer Injektion $A [mm] \to [/mm] B$ folgt, dass $k [mm] \le \ell$
[/mm]
gelten muss.
(Nicht mit Schröder-Bernstein, sondern so: Angenommen, es wäre doch
$k > [mm] \ell\,.$ [/mm] Dann... Widerspruch!)
2. Schritt: Folgere wie im 1. Schritt (oder verweise auf den 1. Schritt), dass
aus der Existenz einer Injektion $B [mm] \to [/mm] A$ dann folgt, dass [mm] $\ell \le [/mm] k$ gelten muss.
Zusammen liefert Dir das [mm] $k=\ell.$
[/mm]
Jetzt versuche, Dir damit eine Bijektion $A [mm] \to [/mm] B$ zu basteln!
Tipp: Manchmal kann es hilfreich sein, sich eine Bijektion
$X [mm] \to \{1,...,|X|\}$
[/mm]
für endliche Mengen [mm] $X\,$ [/mm] zu überlegen - sowas kannst Du dann oben
"dazwischenschalten".
P.S. Sorry, ich habe anstatt [mm] $X\,$ [/mm] leider [mm] $A\,$ [/mm] und anstatt [mm] $Y\,$ [/mm] leider [mm] $B\,$ [/mm] geschrieben,
ich denke aber, dass Du das auch selbst korrigiert/angepasst bekommst. 
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:29 Fr 08.11.2013 | | Autor: | Alex1993 |
ok danke
zu Schritt 1:
Die Funktion ist injektiv, das bedeutet das es für jedes -k- ein f(k) also ein l gibt..
Injektivität setzt voraus das [mm] k_1 [/mm] = [mm] k_2 [/mm] und [mm] f(k_1)=f(k_2) [/mm]
Insgesamt kann man sagen das gilt k [mm] \mapsto [/mm] l
das heßt jedes k lässt sich durch ein l abbilden. Das setzt ja vorraus das gilt:
k [mm] \le [/mm] l
Schritt 2:
hier gilt genau das gleiche nur k und l werden vertauscht...
reicht das um die beiden Schritte zu zeigen? Und wie könnte man dies ein bisschen mathematischer aufschreiben? (wenn du weißt was ich meine)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:51 Fr 08.11.2013 | | Autor: | Marcel |
Hallo,
> ok danke
> zu Schritt 1:
> Die Funktion ist injektiv, das bedeutet das es für jedes
> -k- ein f(k) also ein l gibt..
was?
> Injektivität setzt voraus das [mm]k_1[/mm] = [mm]k_2[/mm] und [mm]f(k_1)=f(k_2)[/mm]
Ohje... diese Begriffe müssen klar sein, sonst verstehst Du die ganze
Aufgabe nicht.
Es gibt folgende zwei Standarddefinitionen für Injektivität, die natürlich
äquivalent sein sollten (was sie auch sind):
Sei $f [mm] \colon [/mm] A [mm] \to [/mm] B$ eine Funktion.
[mm] $f\,$ [/mm] heißt injektiv, falls gilt:
1. Definitionsmöglichkeit: Für alle [mm] $a_1,a_2 \in [/mm] A,$ die [mm] $a_1 \not=a_2$ [/mm] erfüllen, gilt [mm] $f(a_1) \not=f(a_2)\,.$
[/mm]
2. Definitionsmöglichkeit: Für alle [mm] $a_1,a_2 \in [/mm] A,$ die [mm] $f(a_1)=f(a_2)$ [/mm] erfüllen, gilt [mm] $a_1=a_2\,.$
[/mm]
Diese Definitionen sind äquivalent, weil halt für Aussagen [mm] $R,S\,$ [/mm] gilt
[mm] $R\,$ $\Longrightarrow$ $S\,$
[/mm]
ist gleichwertig mit
[mm] $(\neg [/mm] S)$ [mm] $\Longrightarrow$ $(\neg R)\,.$
[/mm]
Und oben haben wir halt deswegen
[mm] $a_1\not =a_2$ $\Longrightarrow$ $f(a_1) \not=f(a_2)$
[/mm]
[mm] $\iff$
[/mm]
[mm] $f(a_1)=f(a_2)$ $\Longrightarrow$ $a_1=a_2\,.$
[/mm]
Damit mal klarer wird, was diese Definition eigentlich bedeutet:
Seien $A,B [mm] \subseteq \IR$ [/mm] und sei $f [mm] \colon [/mm] A [mm] \to B\,.$ [/mm] Dann kannst Du ja den Graphen
von [mm] $f\,,$ [/mm] der definiert ist als
[mm] $\text{Graph}_f=G_f:=\{(x,f(x)):\;\; x \in A\}$
[/mm]
visualisieren/skizzieren, und zwar, wie gewohnt, im kartesischen [mm] $\IR^2.$ [/mm] Jetzt
kann man sich die Menge [mm] $B\,$ [/mm] auf der [mm] $y\,$-Achse [/mm] "markieren". Dann bedeutet
Injektivität nichts anderes als:
Wenn ich irgendeine Gerade hernehme, die parallel zur [mm] $x\,$-Achse [/mm] verläuft
und [mm] "$B\,$ [/mm] auf der y-Achse trifft", dann darf diese Gerade höchstens einen Schnittpunkt
mit [mm] $G_f$ [/mm] haben.
Beachte aber: Beim Graphen von [mm] $f\,$ [/mm] wird nicht immer die ganze [mm] $x\,$-Achse
[/mm]
durchlaufen, sondern Du solltest Dir halt die Menge [mm] $A\,$ [/mm] auch auf der [mm] $x\,$-Achse [/mm] "markieren",
denn das ist der Definitionsbereich!
So ist bspw.:
[mm] $\bullet$ $f_1 \colon [/mm] [0, 10] [mm] \to [/mm] [-1,2]$ mit [mm] $f_1(x):=\sin(x)$ [/mm] nicht injektiv!
[mm] $\bullet$ $f_2 \colon [/mm] [0, [mm] \pi/2] \to [/mm] [-1,2]$ mit [mm] $f_2(x):=\sin(x)$ [/mm] injektiv!
[mm] $\bullet$ $f_3 \colon [-\pi/2, [/mm] 0) [mm] \to [/mm] [-1,1]$ mit [mm] $f_3(x):=\sin(x)$ [/mm] injektiv!
[mm] $\bullet$ $f_4 \colon [-\pi, -\pi/2) \cup [0,\pi/4) \to \IR$ [/mm] mit [mm] $f_4(x):=\sin(x)$ [/mm] nicht injektiv!
(Wie kann man [mm] $f_4$ [/mm] leicht abändern, so dass sie injektiv wird? Am
Einfachsten durch abändern von Klammern...)
Erkennst Du das auch anhand der Graphen? (Insbesondere solltest Du
auch sehen, dass man bei der Injektivität mit "ein Schnittpunkt oder kein
Schnittpunkt" auch den Fall, dass kein Schnittpunkt existiert, auftreten
kann.
Nochmal zu Deiner Aufgabe:
Sei also [mm] $k:=|X|\,$ [/mm] und [mm] $\ell:=|Y|$ [/mm] wie in Deiner Aufgabe. Sei $f [mm] \colon [/mm] X [mm] \to [/mm] Y$ injektiv.
Du sollst nun $k [mm] \le \ell$ [/mm] zeigen.
Nehmen wir dazu an, es wäre $k > [mm] \ell\,.$ [/mm] Versuche mal folgendes irgendwie
aufzuschreiben:
Wir wählen ein [mm] $x_1 \in X\,.$ [/mm] Dann betrachten wir
[mm] $X_1:=X \setminus \{x_1\}$
[/mm]
und
[mm] $Y_1:=Y \setminus \{f(x_1)\}\,.$
[/mm]
Jetzt wähle [mm] $x_2 \in X_1\,.$ [/mm] Nun betrachte
[mm] $X_2:=X_1 \setminus \{x_2\}=X \setminus \{x_1,x_2\}$
[/mm]
und
[mm] $Y_2:=Y_1 \setminus \{f(x_1),f(x_2)\}=Y \setminus \{f(x_1),f(x_2)\}$
[/mm]
etc. pp.
Wir stoppen den Algorithmus nach dem [mm] $k_0$-ten [/mm] Schritt, wenn dann [mm] $X_{k_0}$ [/mm] oder [mm] $Y_{k_0}$
[/mm]
die leere Menge wird.
Dann ist [mm] $k_0=\ell.$ [/mm] (Warum? Hier muss ja irgendwie die Injektivität und die
Annahme $k > [mm] \ell$ [/mm] verwendet werden!)
Was bedeutet dass dann aber für
[mm] $f(x_{\ell+1})$?
[/mm]
Was hat das für die Annahme, dass [mm] $f\,$ [/mm] injektiv sei, für eine Konsequenz?
P.S. Eigentlich ist das, was ich hier mache, eher "heuristisch" bzw. "intuitiv"
und nicht wirklich ein ganz sauberer Beweis. Um einen wirklich sauberen
Beweis führen zu können, solltest Du mal nachliefern, wie ihr
1. definiert habt, wann eine Menge [mm] $X\,$ [/mm] endlich heißt!
und aber vor allem:
2. Wie ist Eure Definition für $|X|=$Anzahl der Elemente von [mm] $X\,,$ [/mm] wenn [mm] $X\,$ [/mm] endlich ist?
Geübte Mathematiker können dann, meistens, aus der heuristischen
Idee mithilfe der ergänzten Definitionen einen sauber(rer)en Beweis
basteln!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:08 Fr 08.11.2013 | | Autor: | Alex1993 |
Ergänzung:
Wir haben notiert:
1.Eine Menge A ist endlich wir ein n aus [mm] \IN [/mm] haben mit /A/ = {1,.....,n}
2. da bin ich leider selbst überfragt
also:
für [mm] f(x_l+1) [/mm] bedeutet das doch, das es kein zugehöriges Urbild aus x hat, da wir ja annehmen das k [mm] \ge [/mm] l stimmt das? und nun?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:23 Fr 08.11.2013 | | Autor: | Marcel |
Hallo,
> Ergänzung:
> Wir haben notiert:
> 1.Eine Menge A ist endlich wir ein n aus [mm]\IN[/mm] haben mit /A/
> = {1,.....,n}
> 2. da bin ich leider selbst überfragt
gerade 2. ist das Wichtigste - denn da gibt es mehrere Möglichkeiten:
[mm] $A\,$ [/mm] heißt endlich, wenn es ein $n [mm] \in \IN$ [/mm] und eine Bijektion
$A [mm] \to \{1,...,n\}$
[/mm]
gibt. (Sehr natürlich: Ich nummeriere die Elemente von [mm] $A\,$ [/mm] mit den Zahlen
[mm] $1\,$ [/mm] bis [mm] $n\,$ [/mm] durch - dabei erfasse ich jedes Element von [mm] $A\,$ [/mm] genau ein Mal.)
Dann heißt $|A|:=n$ die Anzahl der Elemente von A.
Oder:
[mm] $A\,$ [/mm] heißt endlich, wenn es eine Injektion
$A [mm] \to \{1,...,m\}$
[/mm]
gibt mit einem $m [mm] \in \IN.$ [/mm] Dann beweist man:
Es gibt ein minimales solches [mm] $m\,,$ [/mm] wir nennen es hier wieder [mm] $n\,.$
[/mm]
Dann definiert man [mm] $|A|:=n\,.$
[/mm]
Und dann gibt es auch noch eine Definition mit Surjektion...
Aber egal: Ihr hättet sinnvoller jedenfalls erstmal den Begriff der endlichen
Menge ohne [mm] $|A|\,$ [/mm] definiert, und danach erst, was [mm] $|A|\,$ [/mm] bedeuten soll.
So, muss jetzt leider weg!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:27 Fr 08.11.2013 | | Autor: | Alex1993 |
Also was wir noch notiert haben:
wenn es eine injektive Abbildung von A nach B gibt, dann gibt es auch eine bijektive Abbildung von A in eine Teilmenge nach B.. aber ich denke das hilft an dieser Stelle reichlich wenig..
ohje... und wie soll ich jetzt diese Aufgabe lösen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:04 Fr 08.11.2013 | | Autor: | Alex1993 |
weiß keiner wie man diese Aufgabe löst? Es ist leider wirklich wichtig
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:55 Fr 08.11.2013 | | Autor: | leduart |
Hallo
wissen tun das hier sicher einige, wir erwarten aber, dass du nach den Hilfen jetzt mal selbst wenigstens anfängst und dann sagst, wo du scheiterst.
Gruss leduart
|
|
|
| |
|
> Aufgabe:
> Es existiert eine Menge X mit k Elementen und eine Menge Y
> mit l Elementen. Dazu gebe es 2 injektive Abbildungen
> f:X-->Y und g:Y-->X. Zeigen sie (ohne auf Cantor oder
> Bernstein zu verweisen ) , dass es eine Bijektion zwischen
> X und Y gibt...
Hallo,
ich denke mal, Du sollst hier nicht einfach schreiben:
" Seien f:X-->Y und g:Y-->X injektiv.
Nach dem Satz von Schröder-Bernstein gibt es eine Bijektion qed."
Wie bereits besprochen, zeige zunächst:
f:X-->Y ==> [mm] k\le [/mm] l
Beweis:
Angenommen, es wäre k>l.
Dann werden mindestens zwei Elemente aus X auf dasselbe Element in Y abgebildet.
Es gibt also Elemente [mm] x_1, x_2 [/mm] in X und ein Element [mm] y\in [/mm] Y mit
[mm] f(x_1)=y [/mm] und [mm] f(x_2)=y.
[/mm]
Jetzt mach weiter...
LG Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:56 Sa 09.11.2013 | | Autor: | Alex1993 |
okay. das bedeutet doch das [mm] f(l_1)= [/mm] k und [mm] f(l_2)=k [/mm] oder? ich verstehe schon was du meinst an dieser Stelle. Allerdings ist mir auch nach stündlichem überlegen und durchblättern meiner Mathesachen unklar wie ich jetzt weiter mache um zu beweisen das k<l . kannst du mir nochmal weiterhelfen?
|
|
|
| |
|
> okay. das bedeutet doch das [mm]f(l_1)=[/mm] k und [mm]f(l_2)=k[/mm] oder?
Hallo,
???
Nein, es bedeutet genau das, was ist geschrieben habe.
[mm] (l_1 [/mm] und [mm] l_2 [/mm] doch auch nirgends definiert. k ist die Mächtigkeit einer Menge. Wie kommst Du darauf, daß die Zahl k in der Menge B ist - in A ist sie auch nicht zwingend -, und warum sollten darauf die ominösen [mm] l_1 [/mm] abgebildet werden?
Etwas weniger Fantasie bitte. Statt Fantasie und Ornamenten brauchen wir nüchternes logisches Denken und die Kenntnis der vorkommenden Definitionen.)
Also nochmal:
Wir haben zwei Mengen X und X mit |X|=k und |Y|=l, sowie ein injektive Abbildung
f:X-->Y,
und wir wollen zeigen, daß in diesem Fall [mm] k\le [/mm] l gilt.
Beweis durch Widerspruch:
Angenommen, es wäre k>l.
Wir zeigen nun, daß diese Annahme zu einem Widerspruch führt.
Dann werden mindestens zwei Elemente aus X auf dasselbe Element in Y abgebildet.
Es gibt also zwei verschiedene
Elemente [mm] x_1, x_2 [/mm] in X und ein Element [mm] y\in [/mm] Y mit
[mm] f(x_1)=y [/mm] und [mm] f(x_2)=y.
[/mm]
Also ist [mm] f(x_1)=f(x_2).
[/mm]
Aufgrund der Injektivität von f folgt ???,
im Widerspruch dazu, daß die beiden Elemente verschieden sind.
Die Annahme, daß k>l, führt zum Widerspruch.
Also muß [mm] k\le [/mm] l gelten.
Analog kannst und mußt Du zeigen, daß [mm] l\le [/mm] k gilt.
Insgesamt folgt daraus dann: k=l.
LG Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:51 Sa 09.11.2013 | | Autor: | Alex1993 |
ja ok. das verstehe ich. Das ist ein Widerspruch da die Injektivität besagt das wenn [mm] f(x_1)= f(x_2) [/mm] auch [mm] x_1=x_2 [/mm] gilt...das ist aber ein Widerspruch zu der Annahme das k [mm] \ge [/mm] l, denn [mm] x_1 [/mm] und [mm] x_2 [/mm] sind hier verschiedene Elemente... richtig?
wenn ich dann bewiesen habe das k=l ist, kann ich doch so auch einfach auf die Bijektive Abbildung hinweisen, richtig?
|
|
|
| |
|
> ja ok. das verstehe ich. Das ist ein Widerspruch da die
> Injektivität besagt das wenn [mm]f(x_1)= f(x_2)[/mm] auch [mm]x_1=x_2[/mm]
> gilt...das ist aber ein Widerspruch zu der Annahme das k
> [mm]\ge[/mm] l, denn [mm]x_1[/mm] und [mm]x_2[/mm] sind hier verschiedene Elemente...
> richtig?
Hallo,
[mm] x_1=x_2 [/mm] ist ein Widerspruch zu [mm] x_1\not=x_2.
[/mm]
Also ist die gemachte Annahme k>l falsch.
Also ist [mm] k\le [/mm] l.
>
> wenn ich dann bewiesen habe das k=l ist, kann ich doch so
> auch einfach auf die Bijektive Abbildung hinweisen,
> richtig?
Wahrscheinlich ja. Es kommt halt immer drauf an, was Dir an Sätzchen und Definitionen zur Verfügung steht.
LG Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:29 Sa 09.11.2013 | | Autor: | Alex1993 |
Vielen Dank!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:15 Sa 09.11.2013 | | Autor: | Marcel |
Hallo Alex,
> ja ok. das verstehe ich. Das ist ein Widerspruch da die
> Injektivität besagt das wenn [mm]f(x_1)= f(x_2)[/mm] auch [mm]x_1=x_2[/mm]
> gilt...das ist aber ein Widerspruch zu der Annahme das k
> [mm]\ge[/mm] l, denn [mm]x_1[/mm] und [mm]x_2[/mm] sind hier verschiedene Elemente...
> richtig?
gehen wir mal davon aus, dass das so akzeptiert wird, dass der Beweis
von
[mm] $\exists [/mm] f$ injektiv, $f [mm] \colon [/mm] X [mm] \to [/mm] Y$ [mm] $\Rightarrow$ [/mm] $k [mm] \le \ell,$ [/mm] wobei [mm] $k:=|X|\,$ [/mm] und [mm] $\ell:=|Y|\,$ [/mm] für endliche Mengen [mm] $X,Y\,$
[/mm]
also okay ist (denn eigentlich sind da, soweit ich das sehe, durchaus auch
"Schnellfolgerungen" drin - ich habe da nicht umsonst eine Art "Algorithmus"
hingeschrieben, aus dem man das folgern würde, was Angela halt "schnell"
hinschreibt: Es gibt [mm] $x_1 \not=x_2$ [/mm] beide in [mm] $X\,$ [/mm] mit [mm] $f(x_1)=f(x_2)$ [/mm] im Widerspruch
zur Injektivität von [mm] $f\,$ [/mm] - aber genau diese "Schnellfolgerung" kann man nur
mathematisch penibler behandeln, wenn ihr auch alle Definitionen, und diese
auch "vernünftig" zur Verfügung gestellt bekommen habt. Daher kann man
da niemanden einen Vorwurf machen - strenggenommen haben aber weder
Angela noch ich hier bisher "alles ganz sauber" gehandhabt, was aber, wie
gesagt, einfach daran liegt, dass zu wenig Informationen dafür gegeben
worden sind...)
Soweit ich das nun sehe, würde ich aber dann aber die Existenz einer
Bijektion $X [mm] \to [/mm] Y$ noch genauer hinschreiben:
Wir wissen nämlich nun, dass es
sowohl eine Bijektion $u [mm] \colon [/mm] X [mm] \to \{1,...,k\}$
[/mm]
als auch
eine Bijektion $v [mm] \colon [/mm] Y [mm] \to \{1,...,k\}$
[/mm]
gibt (wegen [mm] $k=\ell\,$). [/mm] Sei also
[mm] $v^{-1} \colon \{1,...,k\} \to [/mm] Y$
die Umkehrabbildung von [mm] $v\,.$
[/mm]
Dann ist
[mm] $v^{-1} \circ [/mm] u$
eine Bijektion $X [mm] \to [/mm] Y$ (und es wäre [mm] $u^{-1} \circ v=(v^{-1} \circ u)^{-1}$ [/mm] die
zugehörige Umkehrabbildung $Y [mm] \to X\,,$ [/mm] die natürlich auch bijektiv ist...)
P.S.: Wie gesagt, so wirklich sauber kann man diese Aufgabe hier eigentlich
erst wirklich lösen/bearbeiten, wenn mal eine vernünftige Definition des
Symbols [mm] $|X|\,$ [/mm] zur Verfügung gestellt wird.
Nehmen wir mal an, ihr hättet gesagt:
Eine Menge [mm] $X\,$ [/mm] heißt endlich, wenn [mm] $X=\varnothing$ [/mm] oder wenn es ein $n [mm] \in \IN$
[/mm]
so gibt, dass eine injektive Abbildung
$u [mm] \colon [/mm] X [mm] \to \{1,...,n\}$
[/mm]
existiert. Ein solches minimales [mm] $n_0 \in \IN$ [/mm] heißt dann die Anzahl der Elemente
der Menge [mm] $X\,$ [/mm] und wir definieren dann [mm] $|X|:=n_0\,.$
[/mm]
Das bringt Dir bei der Aufgabe schon etwas:
Zuerst zeigt man, dass dann, für eine (nichtleere) endliche Menge eine injektive
Abbildung
$X [mm] \to \{1,...,|X|\}\,,$
[/mm]
schon bijektiv ist.
Daher ist für eine Menge [mm] $Y\,$ [/mm] mit analogen Eigenschaften dann eine
injektive Abbildung
$Y [mm] \to \{1,...,|Y|\}$
[/mm]
auch bijektiv.
Damit kann man sich dann auch (ohne algorithmische Überlegungen) klarmachen,
dass, wenn es eine injektive Abbildung
$X [mm] \to [/mm] Y$
gibt, wohl $|X| [mm] \le |Y|\,$ [/mm] sein muss.
So ganz genau habe ich mir das nun auch nicht überlegt, aber so [mm] $\pi$ [/mm] Mal Daumen:
Wenn $u [mm] \colon [/mm] X [mm] \to [/mm] Y$ injektiv ist, so definiere ich mir
[mm] $\tilde{u} \colon [/mm] X [mm] \to [/mm] u(X) [mm] \subseteq [/mm] Y$
mit [mm] $\tilde{u}(x):=u(x)$ [/mm] für alle $x [mm] \in X\,.$ [/mm] Dann ist [mm] $\tilde{u}$ [/mm] ja schon bijektiv.
Weiter gibt es aber auch eine Bijektion
$v [mm] \colon [/mm] Y [mm] \to \{1,...,|Y|\}\,.$
[/mm]
Damit kann man wirklich ganz gut (weiter-)arbeiten.
Aber:
Im Endeffekt müsste man aber Eurem Dozenten mal den dezenten Hinweis
geben, dass es schwer ist, die Aufgabe zu beweisen, wenn nicht genügend
viele Grundlagen zur Verfügung gestellt werden.
Gruß,
Marcel
|
|
|
|
