Injektive Selbstabbildung auch bijektiv

02.05.2015, 16:44

Joefish

Injektive Selbstabbildung auch bijektiv

Ich wuerde gerne ueber Induktion zeigen, dass jede inj. Selbstabbildung auch eine Bijektion ist.
Mein bisheriger Versuch:

$\begin{eqnarray*} f:\emptyset \to \emptyset \end{eqnarray*}$ ist bijektiv, da trivialerweise auf jedes Element aus der Zielmenge $\begin{eqnarray*} \emptyset \end{eqnarray*}$ von der Definitionsmenge $\begin{eqnarray*} \emptyset \end{eqnarray*}$ abgebildet wird.

IA: $\begin{eqnarray*} A = \{1 \},\ 1 \in \mathbb{N}^{\times} \end{eqnarray*}$
$\begin{eqnarray*} f:A \to A \end{eqnarray*}$ ist bijektiv, da $\begin{eqnarray*} 1 \mapsto 1 \end{eqnarray*}$ und somit die Bedingung der Bijektivitaet erfuellt.

IV: $\begin{eqnarray*} A = \{1,\dots ,n\} \end{eqnarray*}$
Sei $\begin{eqnarray*} f:A \to A \end{eqnarray*}$ eine Injektion und somit auch bijektiv fuer ein $\begin{eqnarray*} n \in \mathbb{N}^{\times} \end{eqnarray*}$

IS: $\begin{eqnarray*} A = \{1,\dots ,n+1\} \end{eqnarray*}$
Sei $\begin{eqnarray*} f:A \to A \end{eqnarray*}$ injektiv.
$\begin{eqnarray*} g:\{1,\dots ,n\} \to \{1,\dots ,n\},\ x \mapsto f\left(x\right) \end{eqnarray*}$ , also auch g injektiv und nach IV bijektiv.
Angenommen $\begin{eqnarray*} g\!\mid \!A \end{eqnarray*}$ mit $\begin{eqnarray*} g\left(n+1\right) \end{eqnarray*}$ beliebig sei bijektiv. Dann waere fuer ein $\begin{eqnarray*} a \in A,\ g(a)=g(n+1) \end{eqnarray*}$ was der Injektivitaet wiederspricht.
Angenommen $\begin{eqnarray*} g:\{1,\dots ,n\} \to \{1,\dots ,n+1\} \end{eqnarray*}$ sei bijektiv.
Da Bijektivitaet bedeutet, dass fuer jedes $\begin{eqnarray*} y \in \{1,\dots ,n+1\} \end{eqnarray*}$ genau ein $\begin{eqnarray*} x \in \{1,\dots ,n\} \end{eqnarray*}$ existiert, sodass $\begin{eqnarray*} g(x)=y \end{eqnarray*}$ ,
muesste $\begin{eqnarray*} g:\{1,\dots ,n+1\} \to \{1,\dots ,n\} \end{eqnarray*}$ auch eine Bijektion sein, was dem zuvor gezeigtem Fall $\begin{eqnarray*} g\!\mid \! A \end{eqnarray*}$ widerspricht.

Also muessen die Maechtigkeiten der Definitions- sowie Zielmenge uebereinstimmen, sodass eine Injektion bijektiv ist,
was bei einer injektiven Selbstabbildung gegeben ist.
Somit ist $\begin{eqnarray*} f:A \to A \end{eqnarray*}$ bijektiv.

Ich bin mir unsicher, ob ich im Induktionsschritt ueberhaupt von n auf n+1 schliesse und nicht nur den Fall Def.Menge != Zielmenge betrachte.
Waere nett, wenn mir jemand Feedback dazu geben koennte.

02.05.2015, 16:49

Captain Kirk

Auf diesen Beitrag antworten »

Hallo,

ist für euch $\begin{eqnarray*} id: \mathbb R \to \mathbb R , \quad x \to x \end{eqnarray*}$ keine injektive Selbstabbildung?

02.05.2015, 17:04

Math1986

Auf diesen Beitrag antworten »

RE: injektive Selbstabbildung auch bijektiv

Zitat:

Original von Joefish
IS: $\begin{eqnarray*} A = \{1,\dots ,n+1\} \end{eqnarray*}$
Sei $\begin{eqnarray*} f:A \to A \end{eqnarray*}$ injektiv.
$\begin{eqnarray*} g:\{1,\dots ,n\} \to \{1,\dots ,n\},\ x \mapsto f\left(x\right) \end{eqnarray*}$ , also auch g injektiv und nach IV bijektiv.

Den Schritt verstehe ich nicht. Was genau soll $\begin{eqnarray*} g \end{eqnarray*}$ sein?

Nebenbei ist hier Induktion auch prinzipiell ungeeignet, falls die Mengen auch unendlich mächtig seien dürfen.

02.05.2015, 17:33

Joefish

Auf diesen Beitrag antworten »

@Kirk: Doch, sogar eine bijektive..
@Math1986: Ich definiere eine Abbildung g mit den Zuordnungen von f.

Ich lese zurzeit die Ana-Einfuerhung von Amann, da unsere eher etwas 'intuitiverer Natur' gewesen ist.
Bei dem Beweis,dass die natuerlichen Zahlen unendlich sind, wird auch angenommen (bzw. auf eine Aufgabe verwiesen mit Hinweis auf Induktion), dass injektive Selbstabbildungen bijektiv sind.
Da ein Widerspruchsbeweis dort gefuehrt wird, macht die Einschraenkung auf endliche Mengen keine Probleme.
Intuitiv ist mir das klar, jedoch habe ich immer wieder das Problem meine Schluesse richtig zu artikulieren.
Bis zu diesem Punkt sind Definition von Mengen,Funktionen, Relationen sowie die natuerlichen Zahlen ueber die Peano-Axiome bekannt.

Wie wuerdet ihr denn das zeigen?

02.05.2015, 17:38

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Joefish
@Math1986: Ich definiere eine Abbildung g mit den Zuordnungen von f.

Dann sollte dir aber auch klar sein, dass für $\begin{align*} f\left(n+1\right)\neq n+1 \end{align*}$ diese Abbildung $\begin{align*} g \end{align*}$ eben nicht nach $\begin{align*} \left\{1,\ldots,n\right\} \end{align*}$ geht.

Von einer "Einschränkung auf endliche Mengen" war in dem Startbeitrag auch keine Rede.

02.05.2015, 17:39

Captain Kirk

Auf diesen Beitrag antworten »

@fish:
Dann ist die Aussage falsch.
Und vollständige Induktion als Beweisprinzip prinzipiell untauglich, denn wie willst du die auf überabzählbare Definitionsmengen ausweiten?
Gegenbeispiel ist der arcustangens.

Zitat:

Bei dem Beweis,dass die natuerlichen Zahlen unendlich sind, wird auch angenommen (bzw. auf eine Aufgabe verwiesen mit Hinweis auf Induktion), dass injektive Selbstabbildungen bijektiv sind.

Dann musst du mal genau schauen was da angenommen wird.
Evtl. braucht man die Aussage nur für endliche Mengen.

02.05.2015, 17:42

RavenOnJ

Auf diesen Beitrag antworten »

RE: injektive Selbstabbildung auch bijektiv
Was ist denn A für eine Menge? Die Abbildung $\begin{align*} f:\mathbb N\to \mathbb N, n\mapsto 2n \end{align*}$ ist injektiv, aber bestimmt nicht surjektiv.

06.05.2015, 02:35

Joefish

Auf diesen Beitrag antworten »

Vollstaendigkeitshalber zitiere ich den Beweis, welcher meine urspruengliche Frage motiviert hat:
Beweise, dass die Menge $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ unendlich ist.

Zitat:

Wir nehmen an, $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ sei endlich. Dann gibt es ein $\begin{eqnarray*} m \in N^{\times} \end{eqnarray*}$ und eine Bijektion $\begin{eqnarray*} \phi \end{eqnarray*}$ von $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ auf $\begin{eqnarray*} \{1,\dots ,m\} \end{eqnarray*}$ .
Somit ist $\begin{eqnarray*} \psi := \phi \! \mid \! \{1,\dots ,m\} \end{eqnarray*}$ eine Injektion von $\begin{eqnarray*} \{1,\dots ,m\} \end{eqnarray*}$ in sich.
Also ist $\begin{eqnarray*} \psi \end{eqnarray*}$ gemaess Aufgabe 1 eine Bijektion von $\begin{eqnarray*} \{1,\dots ,m\} \end{eqnarray*}$ auf sich. Folglich gibt es ein $\begin{eqnarray*} n \in \{1,\dots ,m\} \end{eqnarray*}$ mit $\begin{eqnarray*} \phi (n) = \psi (n) = \phi (m+1) \end{eqnarray*}$ , was der Injektivitaet von $\begin{eqnarray*} \phi \end{eqnarray*}$ widerspricht.
Also ist $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ unendlich. $\begin{eqnarray*} \blacksquare \end{eqnarray*}$

Wenn man lange vor etwas sitzt, dann nimmt man manchmal Sachen fuer gegeben, die andere nicht wissen koennen..
Oder zumindest geht es mir so. Sorry.
Meine urspruengliche Frage sollte sich auf injektive Selbstabbildungen endlicher Mengen beziehen.

Zitat:

Original von Math1986

Zitat:

Original von Joefish
@Math1986: Ich definiere eine Abbildung g mit den Zuordnungen von f.

Stimmt.. Also waere dann $\begin{eqnarray*} g\! : \left\{1,\dots ,n\right\} \to \left\{1,\dots ,n\right\}, \begin{cases}<br /> g(f^{-1}(n+1)) = f(n+1), & \text{falls }f(n+1) \neq n+1\\<br /> x \mapsto f(x), & x \in \left\{1,\dots ,n\right\}\backslash f^{-1}(n+1)<br /> \end{cases} \end{eqnarray*}$
Da $\begin{eqnarray*} f \end{eqnarray*}$ injektiv, hat das Urbild $\begin{eqnarray*} f^{-1} \end{eqnarray*}$ hoechstens ein Element.

Da die meisten sich vehement gegen Induktion wehren, wie wuerdet ihr die Sache angehen?

06.05.2015, 03:00

RavenOnJ

Auf diesen Beitrag antworten »

Ich versteh nicht, warum das bei endlichen Mengen so kompliziert sein muss. Wenn g eine Selbstabbildung sein soll, die auch noch injektiv ist, dann wird jedem Element der Bildmenge über das Urbild genau ein Element zugeordnet und mit $\begin{align*} g(x)=y \end{align*}$ gilt $\begin{align*} g^{-1}(y)=\{x\} \end{align*}$ . Das Urbild eines Elements muss wegen der Injektivität jeweils einelementig sein. Denn würde es ein Element y' der Menge geben, dessen Urbild aus der leeren Menge besteht, dann würde y' nicht zum Bild von g gehören, was nicht geht, da bei endlichen Mengen die Mächtigkeit der Zielmenge größergleich dem Urbild ist (wegen der Injektivität), bei Selbstabbildung sogar gleich. Die Bildmenge muss also gleich der Zielmenge sein. Damit ist die Abbildung auch surjektiv.

06.05.2015, 18:27

Joefish

Auf diesen Beitrag antworten »

Zitat:

Original von RavenOnJ
[...] da bei endlichen Mengen die Mächtigkeit der Zielmenge größergleich dem Urbild ist (wegen der Injektivität), bei Selbstabbildung sogar gleich. Die Bildmenge muss also gleich der Zielmenge sein. Damit ist die Abbildung auch surjektiv.

Waere das nicht das zu Zeigende anzunehmen?
Mir ist klar dass es so ist, aber es scheint mir formal unvollstaendig.
Sei $\begin{eqnarray*} |D_f| > |Z_f| \end{eqnarray*}$ und $\begin{eqnarray*} f \end{eqnarray*}$ injektiv, dann existieren $\begin{eqnarray*} x,y \in D_f, x \neq y : f(x) = f(y) \end{eqnarray*}$ und verstossen somit gegen die Injektivitaet.
Jedoch, wie leite ich das formal aus $\begin{eqnarray*} |D_f| > |Z_f| \end{eqnarray*}$ ab? Und eine Bedingung ueber eine abzaehlbare Menge zu testen, da erscheint mir Induktion ein geeignetes Mittel zu sein.

Intuitiv sind die Grundlagen eigentlich kein Problem (glaub ich), jedoch je mehr Fragen ich darueber stelle, desto unsicherer werde ich und je ungenuegender erscheinen mir die Antworten.

06.05.2015, 18:52

RavenOnJ

Auf diesen Beitrag antworten »

Ehrlich gesagt, verstehe ich dein Problem nicht. Jetzt schreibst du auf einmal wieder "abzählbar" anstatt "endlich". Bleiben wir doch mal bei "endlich", denn für "abzählbar" habe ich dir ja schon ein Gegenbeispiel gegeben für eine injektive, aber nicht surjektive Abbildung.

Was meinst du mit "formal unvollständig"? Wenn eine Abbildung $\begin{align*} f \end{align*}$ mit endlichem Definitionsbereich $\begin{align*} D_f \end{align*}$ injektiv ist, dann existiert doch für den Bildbereich $\begin{align*} \operatorname{img}( f) \end{align*}$ die Umkehrabbildung $\begin{align*} f^{-1}:\operatorname{img} (f)\to D_f \end{align*}$ . Die Urbildfunktion von $\begin{align*} f \end{align*}$ (eingeschränkt auf den Bildbereich von $\begin{align*} f \end{align*}$ ) ist also selber eine Abbildung. Da es sich um eine Umkehrabbildung handelt, wird jedem Element $\begin{align*} y\in \operatorname{img}(f) \end{align*}$ genau ein Element $\begin{align*} x\in D_f \end{align*}$ zugeordnet, $\begin{align*} f^{-1}(y)=x \end{align*}$ . Denn wäre das nicht so, d.h. zwei Elemente aus $\begin{align*} \operatorname{img}( f) \end{align*}$ würden demselben Element in $\begin{align*} D_f \end{align*}$ zugeordnet, dann wäre $\begin{align*} f \end{align*}$ keine Abbildung. Damit muss gelten

$\begin{align*} Z_f\supset \operatorname{img} f\Rightarrow \vert Z_f\vert \ge \vert \operatorname{img} (f)\vert = \vert D_f\vert \end{align*}$

Die einzigen zwei Voraussetzungen für diese Deduktion ist 1.) die Injektivität von $\begin{align*} f \end{align*}$ und 2.) der Definitionsbereich $\begin{align*} D_f \end{align*}$ ist endlich.

06.05.2015, 20:05

Joefish

Auf diesen Beitrag antworten »

Wow... das war wundervoll erklaert.
Und ja, ich meinte endlich statt abzaehlbar. Ich sollte die Definitionen besser im Kopf behalten.
Mit 'formal unvollstaendig' meinte ich wohl eher, dass ich so manchen Zusammenhang in Aussagen nicht sehe bzw deren Guelitgkeit wieder und wieder zeigen moechte, obwohl dass nicht sein muss..

Danke fuer die Hilfe smile

06.05.2015, 20:41

RavenOnJ

Auf diesen Beitrag antworten »

Zitat:

Original von Joefish
Und ja, ich meinte endlich statt abzaehlbar. Ich sollte die Definitionen besser im Kopf behalten.

Hier sollte man vielleicht noch anmerken, dass "abzählbar" nicht unbedingt "unendlich" implizieren muss. Zur besseren Unterscheidung kann man von "abzählbar unendlich" im Gegensatz zu "endlich" reden, damit ganz klar ist, was gemeint ist.

Neue Frage »

Antworten »

Injektive Selbstabbildung auch bijektiv

Verwandte Themen