Beweis bijektive Abbildung

22.10.2017, 16:03

Nyamh

Beweis bijektive Abbildung

Bei folgender Aufgabe bin ich mir nicht ganz sicher ob ich den richtigen Ansatz verfolge oder nicht.
Seien $\begin{eqnarray*} n,m \in \mathbb{N} \end{eqnarray*}$ zwei natürliche Zahlen, Zeigen Sie, dass es genau dann eine bijektive Abbildung $\begin{eqnarray*} f: \{1,2,3,4,...,n\} \to \{1,2,3,4...,m\} \end{eqnarray*}$ gibt, wenn n= m ist.

Ich dachte erst an einen Widerspruchsbeweis, also als Annahme das n ungleich m gilt, aber damit komme ich ja nicht zu genau dann wenn. Dann hab ich mir das mal mit den Definitionen aufgeschrieben:

$\begin{eqnarray*} (f(x_{1})=f(x{_2}) \Rightarrow x_{1} = x_{2}) \wedge (\forall y \in Y \exists x \in X : f(x)=y ) \Leftrightarrow n = m \end{eqnarray*}$

Und an dem Punkt weiß ich nicht so wirklich weiter, irgendwie komm ich von der Idee nicht los zu sagen wenn n ungleich m dann wird halt nicht auf alle m abgebildet oder so, aber bin mir eben nicht sicher. Kann mir jemand auf die Sprünge helfen?

22.10.2017, 18:04

Elvis

Auf diesen Beitrag antworten »

$\begin{eqnarray*} "\Leftarrow" \end{eqnarray*}$ ist ganz leicht, da gibt man einfach eine bijektive Abbildung an.
$\begin{eqnarray*} "\Rightarrow" \end{eqnarray*}$ betrachte $\begin{eqnarray*} M=\{1,...,n\} \end{eqnarray*}$ und $\begin{eqnarray*} f(M) \end{eqnarray*}$

Eventuell ist deine Idee (Beweis durch Widerspruch) doch besser als meine Idee für die $\begin{eqnarray*} "\Rightarrow" \end{eqnarray*}$ - Richtung. Tipp: $\begin{eqnarray*} n\ne m\Rightarrow n<m\vee n>m \end{eqnarray*}$

22.10.2017, 18:50

Nyamh

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
$\begin{eqnarray*} "\Leftarrow" \end{eqnarray*}$ ist ganz leicht, da gibt man einfach eine bijektive Abbildung an.
$\begin{eqnarray*} "\Rightarrow" \end{eqnarray*}$ betrachte $\begin{eqnarray*} M=\{1,...,n\} \end{eqnarray*}$ und $\begin{eqnarray*} f(M) \end{eqnarray*}$

Eventuell ist deine Idee (Beweis durch Widerspruch) doch besser als meine Idee für die $\begin{eqnarray*} "\Rightarrow" \end{eqnarray*}$ - Richtung. Tipp: $\begin{eqnarray*} n\ne m\Rightarrow n<m\vee n>m \end{eqnarray*}$

D.h. für $\begin{eqnarray*} "\Leftarrow" \end{eqnarray*}$ nehme ich einfach $\begin{eqnarray*} f: x \to x \end{eqnarray*}$ für irgendein x1 und habe die Richtung damit gezeigt?

und bei $\begin{eqnarray*} "\Rightarrow" \end{eqnarray*}$ Nehme ich Bspw. $\begin{eqnarray*} f: x \to x+1 \end{eqnarray*}$ und zeige damit, dass wenn m ungleich n ist die Abbildung nicht bijektiv ist?

22.10.2017, 18:58

Elvis

Auf diesen Beitrag antworten »

Die erste Richtung stimmt. Man schreibt dafür $\begin{eqnarray*} f(x)=x \end{eqnarray*}$ oder $\begin{eqnarray*} f:\{1,...,n\}\to \{1,...,n\},x\mapsto f(x)=x \end{eqnarray*}$ , und dieses $\begin{eqnarray*} f \end{eqnarray*}$ ist offensichtlich bijektiv.

Die andere Richtung ist logisch falsch. Du musst beweisen, dass für n ungleich m alle Funktionen von $\begin{eqnarray*} \{1,...,n\} \end{eqnarray*}$ nach $\begin{eqnarray*} \{1,...,m\} \end{eqnarray*}$ nicht bijektiv sind, also nicht injektiv oder nicht surjektiv. Beachte meinen Tipp n<m oder n>m .

22.10.2017, 19:30

Nyamh

Auf diesen Beitrag antworten »

Also Intuitiv würde ich ja sagen wenn bspw. f(x)= 2*x dann werden eben nur alle geraden Zahlen getroffen, das zeigt es für ein Beispiel , aber nicht für alle Funktionen. Wenn ich es für alle zeigen will dann muss ich allgemein zeigen was passiert wenn n < m und was passiert wenn n>m, richtig?

Mir ist vollkommen klar das bei n<m nicht alle Zahlen im Bild getroffen werden und dass dies bei n>m auch so sein müsste. ich weiß nur nicht wie ich das sagen soll?!

Bei meinem Beispiel oben wäre ja n < m, für n > m will mir nicht so recht ein Beispiel einfallen um mir das zu vergegenständlichen.

22.10.2017, 19:38

Elvis

Auf diesen Beitrag antworten »

Zitat:

Original von Nyamh
Mir ist vollkommen klar das bei n<m nicht alle Zahlen im Bild getroffen werden und dass dies bei n>m auch so sein müsste. ich weiß nur nicht wie ich das sagen soll?!

Leider nur halb richtig.
n<m, dann trifft jede Funktion f nicht alle Zahlen von 1 bis m, also ist f nicht surjektiv. (Uff. Das hätten wir geschafft.)

n>m, dann ... ??? (bleibt ja nicht mehr viel zu beweisen übrig). Beachte (wieder einmal), dass f jedem Element etwas zuordnen muss.

22.10.2017, 20:16

Nyamh

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
n>m, dann ... ??? (bleibt ja nicht mehr viel zu beweisen übrig). Beachte (wieder einmal), dass f jedem Element etwas zuordnen muss.

Ok das heißt wenn n>m dann ist die Bedingung einer Abbildung nicht erfüllt, da wenn n>m nicht alle n abgebildet werden, irgendwie hab ich da noch ein knick und habe mir überlegt was eigentlich in den natürlichen zahlem mit f(x) = 1/2x passiert oder geht 1/2x garnicht weil in den Natürlichen zahlen, oder würde das einfach dann heißen f(1)= 0 f(2) = 1 f(3) = 1? damit wäre ja dann injektivität nicht gegeben?

23.10.2017, 08:09

Elvis

Auf diesen Beitrag antworten »

Leider kein gutes Argument dabei. Heute Nachmittag mehr ...

Jede Funktion von $\begin{eqnarray*} \{1,...,n\} \end{eqnarray*}$ nach $\begin{eqnarray*} \{1,...,m\} \end{eqnarray*}$ ist eine Funktion, also wird jedem Element der Definitionsmenge genau ein Element der Zielmenge zugeordnet. (Jedes Pferd ist ein Pferd.) Deshalb ist dein erstes Argument nicht schlüssig.

Spezielle Funktionen zu betrachten ist hier nicht sinnvoll, weil eine Aussage über alle Funktionen von $\begin{eqnarray*} \{1,...,n\} \end{eqnarray*}$ nach $\begin{eqnarray*} \{1,...,m\} \end{eqnarray*}$ gemacht werden soll.

Dein Beispiel $\begin{eqnarray*} f(x)=\frac 1 2 x \end{eqnarray*}$ ist ein bedauerlicher Rückfall in Denk- und Schreibweisen der Schulmathematik. Du musst lernen und dich damit vertraut machen, wie Funktionen in der modernen Mathematik definiert und verstanden werden. (Beachte das oben fett gesetzte.) Es gibt zwar einige Funktionen, die man bei gegebenem Definitionsbereich und Zielbereich durch Formeln der Art $\begin{eqnarray*} f(x)=... \end{eqnarray*}$ angeben kann, im allgemeinen ist das aber nicht so, und deshalb behindert eine solche Schreibweise das Denken eher als dass sie das Denken fördert.

Und jetzt wieder konstruktiv: Du brauchst nur noch ein winzig kleines Argument dafür, dass jede Funktion $\begin{eqnarray*} f:\{1,...,n\}\to \{1,...,m\} \end{eqnarray*}$ nicht injektiv ist falls $\begin{eqnarray*} m<n \end{eqnarray*}$ . (Beachte das oben fett gesetzte.) Versuche einmal, n Paar Socken in m Schubläden zu legen ... was passiert, wenn weniger Schubläden als Sockenpaare da sind ? Das allgemeine Phänomen nennt man das "Schubfachprinzip".

23.10.2017, 19:29

Nyamh

Auf diesen Beitrag antworten »

Hallo Elvis, es ist mir fast peinlich, dass zuzugeben: Ich hatte durchgehend ein fundamental falsches Verständnis von n=m! Bei n=m geht es ja darum dass gleich viele Elemente in den Mengen sind, ich bin jedoch die ganze Zeit davon ausgegangen dass die Abbildung 1 -> 1, 2-> 2 sein muss, was natürlich völliger Quark ist. da es ja n! mögliche bijektive Abbildungen von n -> m gibt. Und somit ist es ja total einfach zu sagen, dass wenn n < m, die Funktion nicht surjektiv sein kann, da nicht auf alle m abgebildet werden kann und wenn n>m die Funktion nicht injektiv sein kann, da es min. ein m gibt auf das mehrere n abbilden.

Ich hoffe ich hab das jetzt richtig verstanden?

23.10.2017, 19:39

Elvis

Auf diesen Beitrag antworten »

total genial. so ist es und nicht anders. sei stolz auf dich. du hast es begriffen und in einem unmißverständlichen Satz ausgesprochen. Tanzen

Damit hast du ein Grundprinzip der Mengenlehre bewiesen, nämlich den "Klassifikationssatz endlicher Mengen".

Definition: Zwei Mengen $\begin{eqnarray*} A \end{eqnarray*}$ und $\begin{eqnarray*} B \end{eqnarray*}$ heißen gleichmächtig, wenn es eine Bijektion $\begin{eqnarray*} f:A\to B \end{eqnarray*}$ gibt.
Theorem (Klassifikationssatz endlicher Mengen) : Zwei endliche Mengen sind genau dann gleichmächtig, wenn sie gleich viele Elemente enthalten.

23.10.2017, 19:47

Nyamh

Auf diesen Beitrag antworten »

Juhuu, und nochmals vielen Dank, ich entwickle gerade mit Hilfe dieses Forums und deiner tollen Hilfestellung großen Spaß an der Mathematik!

Neue Frage »

Antworten »

Beweis bijektive Abbildung

Verwandte Themen