injektive abbildung

18.10.2008, 20:05

zickchen112

injektive abbildung

hab hier folgende aufgabe die mich um den verstand bringt:

für m,n Element der natürlichen zahlen, sei E eine Menge mit m Elementen und F eine Menge mit n Elementen. Zeige: es existiert genau dann eine injektive Abbildung f:E-->F, wenn m $\begin{eqnarray*} \leq \end{eqnarray*}$ n ist.

18.10.2008, 20:15

system-agent

Auf diesen Beitrag antworten »

Such mal bei Wikipedia nach "Schubfachprinzip".

18.10.2008, 20:54

zickchen112

Auf diesen Beitrag antworten »

also kann ich eigentlich die injektivität so beweisen, dass ich die surjektivität ausschließe, weil laut def. von surjektiv (jedem y ist mind. ein x zugeordnet) das m<n gar nicht zutrifft, weil es ja weniger m als n gibt.
und die injektivität besagt, dass jedem n (von denen es mehr als m gibt) höchstens 1 oder auch kein m zugeordnet ist.

liege ich da richtig?

18.10.2008, 21:10

system-agent

Auf diesen Beitrag antworten »

Zitat:

Original von zickchen112
also kann ich eigentlich die injektivität so beweisen, dass ich die surjektivität ausschließe

Nein. Was hat Injektivität mit Surjektivität zu tun?

Injektivität für eine Funktion $\begin{eqnarray*} f:E\to F \end{eqnarray*}$ bedeutet, dass für alle $\begin{eqnarray*} e_1,e_2\in E \end{eqnarray*}$ mit $\begin{eqnarray*} f(e_1)=f(e_2) \end{eqnarray*}$ stets auch sofort $\begin{eqnarray*} e_1=e_2 \end{eqnarray*}$ folgt.
In Worten kann man sagen, jedes Bildelement der Funktion wird nur einmal getroffen.

Übrigens hast du zwei Richtungen zu zeigen, denn die Behauptung ist:
Es gibt ein injektives $\begin{eqnarray*} f:E\to F \end{eqnarray*}$ $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} m\leq n \end{eqnarray*}$ .

18.10.2008, 21:22

zickchen112

Auf diesen Beitrag antworten »

ok...

in beide richtungen? also auch noch F-->E?

ich hab jetzt 2 fälle gemacht:

a) m=n , dann wird jedem m genau ein n zugeordnet, somit auch jedem n ein m, womit das "=" bewiesen wäre

b) m<n , jedem m wird mindestens ein n zugeordnet.

jetzt kapier ich selbst nicht mehr, was daran injektiv sein soll

18.10.2008, 21:25

system-agent

Auf diesen Beitrag antworten »

Was tust du denn da?
Du sollst die beiden Richtungen der Äquivalenz beweisen, das heisst zuerst die Aussage:
"Ist $\begin{eqnarray*} f:E\to F \end{eqnarray*}$ injektiv dann ist $\begin{eqnarray*} m\leq n \end{eqnarray*}$ "
und danach die Aussage
"Ist $\begin{eqnarray*} m\leq n \end{eqnarray*}$ dann gibt es eine injektive Funktion $\begin{eqnarray*} f:E\to F \end{eqnarray*}$ ."

18.10.2008, 21:47

zickchen112

Auf diesen Beitrag antworten »

sorry, bin der absolute neuling und hab sowas noch nie gemacht. von daher stell ich mich vielleicht auch etwas blöd an. ich hab weder ahnung wie man sowas aufschreibt, noch hab ich im großen tollen internet n vergleichbares beispiel gefunden.

also nochmal ein versuch:

zur ersten aussage:

eine abbildung/funktion ist dann injektiv wenn den Elementen aus F höchstens ein (für den Fall =) oder kein (für den fall m<n) Element aus E zugeordnet ist.

zur zweiten aussage:

wenn jedem m höchstens ein n zugeordnet werden kann, dann is es injektiv

18.10.2008, 21:54

system-agent

Auf diesen Beitrag antworten »

Versuchen wir mal die erste Aussage zu beweisen, also "Ist $\begin{eqnarray*} f:E\to F \end{eqnarray*}$ injektiv, dann ist $\begin{eqnarray*} m\leq n \end{eqnarray*}$ ".

Nehmen wir mal das Gegenteil an, also dass $\begin{eqnarray*} m>n \end{eqnarray*}$ . Das heisst im Klartext, die Menge $\begin{eqnarray*} E \end{eqnarray*}$ enthält mehr Elemente als die Menge $\begin{eqnarray*} F \end{eqnarray*}$ . Nun ist aber $\begin{eqnarray*} f \end{eqnarray*}$ injektiv, das bedeutet zu jedem Element in $\begin{eqnarray*} E \end{eqnarray*}$ gibt es ein Bildelement in $\begin{eqnarray*} F \end{eqnarray*}$ und zwar nur eines. Es folgt, dass das Bild unter $\begin{eqnarray*} f \end{eqnarray*}$ auch genau $\begin{eqnarray*} m \end{eqnarray*}$ verschiedene Elemente hat innerhalb der Menge $\begin{eqnarray*} F \end{eqnarray*}$ . Das ist aber ein Widerspruch, denn $\begin{eqnarray*} F \end{eqnarray*}$ hat lediglich $\begin{eqnarray*} n \end{eqnarray*}$ Elemente. Es muss also $\begin{eqnarray*} m\leq n \end{eqnarray*}$ gegolten haben.

Nun du mit der Umkehrung.

Wie gesagt, diese Aufgabe ist genau das Schubfachprinzip von Dirichlet und einen Artikel dazu kann man bei Wikipedia finden.

18.10.2008, 21:54

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von zickchen112
eine abbildung/funktion ist dann injektiv wenn den Elementen aus F höchstens ein (für den Fall =) oder kein (für den fall m<n) Element aus E zugeordnet ist.

"höchstens ein" schließt "kein" mit ein. Also reicht:

"eine abbildung ist injektiv wenn den Elementen aus F höchstens ein Element aus E zugeordnet ist."

18.10.2008, 22:20

zickchen112

Auf diesen Beitrag antworten »

wenn es eine bestimmte anzahl von objekten gibt und mehrere schubladen, dann landet in jeder schublade höchstens ein objekt (es können auch welche leer bleiben). in der bildmenge (F) gibt es dann höchstens ein Element aus E.

so in etwa?

18.10.2008, 22:31

WebFritzi

Auf diesen Beitrag antworten »

Wo sind jetzt die beiden Richtungen bewiesen?

19.10.2008, 11:14

zickchen112

Auf diesen Beitrag antworten »

@webfritzi:

ich bitte dich mal nachzudenken wie es bei dir nach der ersten vorlesung an der uni war, da hast auch du vielleicht noch nicht alles kapiert. von daher musst du nicht gleich alle angreifen.

so ich hab mir jetzt nochmal gedanken gemacht um die rückrichtung zu beweisen und bin auf folgendes ergebnis gekommen.

"Ist $\begin{eqnarray*} m\leq n , so ist f:E->F injektiv \end{eqnarray*}$ "

Annahme des Gegenteils: f ist nicht injektiv, d.h. jedes n hat mindestens ein m, sprich jedem n sind mehrere m zugeordnet. --> m>n

Das ist ein Widerspruch zu $\begin{eqnarray*} m\leq n \end{eqnarray*}$ , so muss f: E->F injektiv sein, da jedem n höchstens ein m zugeordnet werden kann.

ist das jetzt richtig?

19.10.2008, 13:16

system-agent

Auf diesen Beitrag antworten »

Zitat:

Original von zickchen112

Annahme des Gegenteils: f ist nicht injektiv, d.h. jedes n hat mindestens ein m, sprich jedem n sind mehrere m zugeordnet. --> m>n

Du solltest darüber nachdenken was die einzelnen Dinge bedeuten. Hier $\begin{eqnarray*} m \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ sind einfach die "Grössen" der Mengen $\begin{eqnarray*} E \end{eqnarray*}$ und $\begin{eqnarray*} F \end{eqnarray*}$ , sprich die Anzahl der Elemente dieser Mengen.
Das heisst $\begin{eqnarray*} f \end{eqnarray*}$ ordnet weder $\begin{eqnarray*} m \end{eqnarray*}$ noch $\begin{eqnarray*} n \end{eqnarray*}$ etwas zu.
Also die Voraussetzung für diese Richtung ist, dass
$\begin{eqnarray*} |E|=m\leq n=|F| \end{eqnarray*}$
Nun sollst du zeigen, dass es dann eine injektive Abbildung $\begin{eqnarray*} f:E\to F \end{eqnarray*}$ gibt. $\begin{eqnarray*} f \end{eqnarray*}$ kannst du hier auch direkt konstruieren um diese Abbildung zu bekommen.
Sei $\begin{eqnarray*} E=\{x_1,x_2,...,x_m\} \end{eqnarray*}$ und $\begin{eqnarray*} F=\{y_1,y_2,...,y_m,y_{m+1},...,y_n\} \end{eqnarray*}$ .
Wie könnte man nun eine Abbildung $\begin{eqnarray*} f \end{eqnarray*}$ definieren so, dass sie injektiv ist? [Lies nochmal die Definition von Injektivität].

19.10.2008, 13:41

zickchen112

Auf diesen Beitrag antworten »

injektiv bedeutet doch, das für alle x1,x2 aus X aus es auch das gleiche f(x1),f(x2) gibt.

ehrlich gesagt liegt mein problem schon darin was dieses dumme f zu bedeuten hat. wenn das geklärt wäre, vielleicht würde ich dann leichter damit zurecht kommen

es muss doch eineindeutig sein. jedes x muss sein zugehöriges y haben.
heißt das doch wenn x=2 sei, dann ist y f(2)

somit müsste dann ja jedes m genau ein zugehöriges n haben

19.10.2008, 13:49

system-agent

Auf diesen Beitrag antworten »

Du solltest nochmals die Grundlagen lesen:
$\begin{eqnarray*} f:E\to F \end{eqnarray*}$ bedeutet, dass man eine Abbildung von $\begin{eqnarray*} E \end{eqnarray*}$ nach $\begin{eqnarray*} F \end{eqnarray*}$ mit dem Namen $\begin{eqnarray*} f \end{eqnarray*}$ betrachtet [ansonsten wäre der Zusatz "injektiv" auch sinnlos]. Also lies nochmal genau nach was eine Abbildung/Funktion ist.

Und nochmals:
Weder $\begin{eqnarray*} m \end{eqnarray*}$ noch $\begin{eqnarray*} n \end{eqnarray*}$ sind Elemente von $\begin{eqnarray*} E \end{eqnarray*}$ oder $\begin{eqnarray*} F \end{eqnarray*}$ , sondern lediglich die Anzahl der Elemente dieser Mengen.

19.10.2008, 13:56

zickchen112

Auf diesen Beitrag antworten »

Also in meinen unterlagen steht (vielleicht liegt da der fehler, wäre nicht der erste im skript):

f ist eine Vorschrift, welche jedem x aus X ein eindeutig bestimmtes y aus Y zuweist.

hiernach müsste f: E->F heißen:

f ist die vorschrift welche jedem m aus E ein eindeutig bestimmtes n aus F zuweist.

(sprich kein F wird doppelt belegt, aber da F ja größer ist bleiben einige plätze frei)

19.10.2008, 14:29

system-agent

Auf diesen Beitrag antworten »

Zitat:

Original von zickchen112
hiernach müsste f: E->F heißen:

f ist die vorschrift welche jedem m aus E ein eindeutig bestimmtes n aus F zuweist.

Genau das heisst es eben nicht.
In der Definition steht, dass $\begin{eqnarray*} f \end{eqnarray*}$ jedem $\begin{eqnarray*} x\in X \end{eqnarray*}$ etwas zuweist. In deinem Fall wäre es also jedem $\begin{eqnarray*} e\in E \end{eqnarray*}$ . Aber $\begin{eqnarray*} m\notin E \end{eqnarray*}$ , denn $\begin{eqnarray*} m=|E| \end{eqnarray*}$ , also die Anzahl der Elemente aus $\begin{eqnarray*} E \end{eqnarray*}$ .

19.10.2008, 14:43

zickchen112

Auf diesen Beitrag antworten »

ok, vielen dank.

also wenn E </= F ist, dann hat E weniger oder gleich viele Elemente wie F, sprich m>/= n.

f weißt nun jedem e ein f zu. da die menge aller e (=m) aber kleiner/gleich der menge aller f (=n) ist müsste ja jedem f mindestens ein e zugewiesen werden.

und wie bring ich jetzt das injektiv mit rein?

19.10.2008, 15:19

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von zickchen112
@webfritzi:

ich bitte dich mal nachzudenken wie es bei dir nach der ersten vorlesung an der uni war, da hast auch du vielleicht noch nicht alles kapiert. von daher musst du nicht gleich alle angreifen.

Ich habe dich nicht angegriffen. Wenn du dich hier angegriffen gefühlt hast, dann muss ich schon sagen, dass du recht zart besaitet bist. Ich habe dir mit meinem Beitrag kurz und knapp klargemacht, dass dein Beweis keiner ist und dass du dich doch bitte an die Vorgaben halten solltest, die dir von den anderen Forenmitgliedern gegeben waren. Wie ich sehe, hat das ja auch wenigtens ein bisschen gefruchtet.
ZUdem kann ich mich leider nicht in deine Lage versetzen, denn eine solche Aufgabe habe ich auch im ersten Semester in 5 Minuten gelöst. Wenn du Injektivität nämlich wirklich verstanden hast, dann ist die zu beweisende Aussage der Aufgabe auch für dich trivial.

19.10.2008, 16:13

zickchen112

Auf diesen Beitrag antworten »

ok. liegt vielleicht daran, dass injektivität etc nie geklärt wurde bisher. hatten nur 1std vorlesung und ich versuch mir das eben selbst beizubringen.

nochmal ein versuch zum gegenbeweis. sollte dies überhaupt ein gegenbeweis sein.

ist f: E->F die funktion zwischen den beiden endlichen mengen E und F und gilt nach dem schubfachprinzip F<E, dann ist f nicht injektiv.es gibt also mindestens zwei verschiedene Elemente e und f von E mit f(e)=f(f). da dies aber nicht der fall ist, muss die abbildung f injektiv sein.

habe ich damit jetzt wieder das gleiche bewiesen? aber eigentlich ist es doch die rückrichtung oder?

19.10.2008, 19:45

system-agent

Auf diesen Beitrag antworten »

Beachte, einfach eine Funktion zu nehmen nützt nichts, denn diese ist im allgemeinen garnichts. Beispielsweise könnte in deiner Argumentation $\begin{eqnarray*} f \end{eqnarray*}$ eine konstante Funktion sein, also geht das nicht.
Wie ich oben bereits sagte willst du hier die Existenz eines injektiven $\begin{eqnarray*} f \end{eqnarray*}$ beweisen kannst du direkt eines angeben [immer unter der Annahme, dass $\begin{eqnarray*} m\leq n \end{eqnarray*}$ gilt].
Noch ein Hinweis dazu:
Seien $\begin{eqnarray*} E=\{x_1,x_2,...,x_m\} \end{eqnarray*}$ und $\begin{eqnarray*} F=\{y_1,...,y_m,y_{m+1},...,y_n\} \end{eqnarray*}$ .
Nehme $\begin{eqnarray*} f:E\to F \end{eqnarray*}$ definiert durch
$\begin{eqnarray*} x_1\mapsto y_1 \end{eqnarray*}$
$\begin{eqnarray*} x_2\mapsto y_2 \end{eqnarray*}$
...
$\begin{eqnarray*} x_n\mapsto y_n \end{eqnarray*}$

Neue Frage »

Antworten »

injektive abbildung

Verwandte Themen