Nachlesen

Injektivität

Bei einer injektiven Funktion bzw. injektiven Abbildung (auch Injektion genannt) handelt es sich um eine Abbildung, bei der verschiedene Elemente der Definitionsmenge stets verschiedene Bilder haben. Allgemein: Bei einer injektiven Funktion handelt es sich um einen Spezialfall einer linkseindeutigen Relation, die zudem rechtseindeutig und linkstotal ist.

Inhalt

Definition
Beispiele
Nachweis der Injektivität
Eigenschaften
Mächtigkeit von Mengen
Anzahl injektiver Abbildungen

Definition

Gegeben seien zwei Mengen $A$ und $B$ sowie eine Funktion bzw. Abbildung $f: A \rightarrow B$. Die Abbildung $f$ heißt injektiv, wenn sie unterschiedlichen Elementen $a_1$ und $a_2$ der Definitionsmenge $A$ stets verschiedene Elemente $f(a_1)$ und $f(a_2)$ der Zielmenge $B$ zuordnet, falls also gilt:

\forall a_1,a_2 \in A \Bigl( a_1 \neq a_2 \Rightarrow f(a_1) \neq f(a_2) \Bigr).

Diese Bedingung kann analog auch so formuliert werden, dass jedem Element $b$ der Zielmenge $B$ höchstens ein Element $a$ der Definitionsmenge $A$ zugeordnet ist, für das $f(a)=b$ gilt, falls also gilt:

\forall a_1,a_2 \in A \Bigl( f(a_1) = f(a_2) \Rightarrow a_1 = a_2 \Bigr).

Da verschiedene Elemente der Definitionsmenge bei einer injektiven Abbildung stets verschiedene Bilder besitzen, kann die Zielmenge nicht weniger mächtig als die Definitionsmenge sein. Umgekehrt ist es für injektive Abbildungen jedoch nicht erforderlich, dass jedes Element der Zielmenge tatsächlich ein Urbild besitzt. In diesem Fall ist die Bildmenge $f(A) = \bigl\{ f(a) | a \in A \bigr\} \subseteq B$ eine echte Teilmenge der Zielmenge. Die Zielmenge kann folglich auch mächtiger als die Definitionsmenge sein. Für injektive Abbildungen gilt somit:

|B| \geq |A|.

Beispiele

Bei den folgenden Beispielen handelt es sich um injektive Abbildungen:

Die Abbildung $f_1: \N \rightarrow \N$, $n \mapsto 5n$ ist injektiv.
Die Abbildung $f_2: \Z \rightarrow \Z$, $n \mapsto 2n-1$ ist injektiv.
Die Abbildung $f_3: \N \rightarrow \N$, $n \mapsto {(n+1)}^2$ ist injektiv.

Bei den folgenden Beispielen handelt es sich um nicht injektive Abbildungen:

Die Abbildung $f_1: \N \rightarrow \N$, $n \mapsto 42$ ist nicht injektiv.
Die Abbildung $f_2: \Z \rightarrow \Z$, $n \mapsto {(n+1)}^2$ ist nicht injektiv.
Die Abbildung $f_3: \Z \times \N \rightarrow \Q$, $(m,n) \mapsto \frac{m}{n}$ ist nicht injektiv.
Jede Abbildung $f_4: A \rightarrow B$ mit $A = \bigl\{ a_1,a_2 \bigr\}$ und $B = \bigl\{ b \bigr\}$ ist nicht injektiv, da $|A| \gt |B|$ gilt.

Nachweis der Injektivität

Zum Nachweis der Injektivität einer Abbildung $f: A \rightarrow B$ muss gezeigt werden, dass verschiedene Elemente $a_1$ und $a_2$ der Definitionsmenge $A$ stets auf verschiedene Elemente $f(a_1)$ und $f(a_2)$ der Zielmenge $B$ abgebildet werden. Während dies für endliche Mengen $A$ durch direktes Nachrechnen gezeigt werden kann, ist dies bei unendlichen Mengen nicht möglich. In diesem Fall ist es sinnvoll, zwei beliebige Elemente $a_1,a_2 \in A$ zu betrachten und zunächst anzunehmen, dass diese dasselbe Bild besitzen. Die resultierende Gleichung $f(a_1) = f(a_2)$ kann anschließend nach $a_1$ bzw. $a_2$ aufgelöst werden und es gilt:

Existiert ausschließlich die immer vorhandene triviale Lösung $a_1 = a_2$, handelt es sich bei $a_1$ und $a_2$ also um dasselbe Element, so ist die Abbildung $f$ injektiv.
Existiert neben der trivialen Lösung mindestens eine weitere Lösung der Gleichung $f(a_1) = f(a_2)$ mit $a_1 \neq a_2$, so ist die Abbildung $f$ nicht injektiv.

Die Nicht-Injektivität einer Abbildung $f: A \rightarrow B$ kann alternativ auch durch die Angabe eines Gegenbeispiels gezeigt werden, indem zwei verschiedene Elemente $a_1,a_2 \in A$ mit $a_1 \neq a_2$ angegeben werden, für die $f(a_1) = f(a_2)$ gilt.

Beispiel 1

Gegeben sei die Abbildung $f_1: \Z \rightarrow \Z$ mit $n \mapsto 2n-1$. Um die Injektivität der Abbildung zu prüfen, werden zunächst zwei Elemente $m$ und $n$ der Definitionsmenge $\Z$ gewählt und angenommen, dass diese dasselbe Bild haben; dann gilt:

\begin{align*} f_1(m) &= f_1(n) \\[0.5em] 2m-1 &= 2n-1. \end{align*}

Anschließendes Auflösen der Gleichung liefert:

\begin{align*} 2m-1 &= 2n-1 \\[0.5em] 2m &= 2n \\[0.5em] m &= n. \end{align*}

Da sich als einzige Lösung der Gleichung die triviale Lösung $m=n$ ergibt, ist die Abbildung $f_1$ injektiv.

Beispiel 2

Gegeben sei die Abbildung $f_2: \Z \rightarrow \Z$ mit $n \mapsto {(n+1)}^2$. Um die Injektivität der Abbildung zu überprüfen, werden zunächst zwei Elemente $m$ und $n$ der Definitionsmenge $\Z$ gewählt und angenommen, dass diese dasselbe Bild haben; dann gilt:

\begin{align*} f_2(m) &= f_2(n) \\[0.5em] {(m+1)}^2 &= {(n+1)}^2. \end{align*}

Ziehen der Wurzel auf beiden Seiten der Gleichung liefert:

\begin{align*} {(m+1)}^2 &= {(n+1)}^2 \\[0.5em] m+1 &= \pm (n+1). \end{align*}

Die beiden Fälle können nun separat gelöst werden:

Für den ersten Fall $m+1=n+1$ ergibt sich: $\begin{align*} m+1 &= n+1 \\[0.5em] m &= n. \end{align*}$
Für den zweiten Fall $m+1=-(n+1)$ ergibt sich entsprechend: $\begin{align*} m+1 &= -(n+1) \\[0.5em] m+1 &= -n-1 \\[0.5em] m &= -n - 2. \end{align*}$

Während es sich bei der Lösung des ersten Falls um die trivial Lösung handelt, ergibt der zweite Fall die nichttriviale Lösung, dass $f_2(m)=f_2(n)$ ebenfalls für $m=-n-2$ gilt, woraus unmittelbar folgt, dass die Abbildung $f_2$ nicht injektiv ist.

Alternativ hätte die Nicht-Injektivität auch mithilfe eines Gegenbeispiels gezeigt werden können – es gilt beispielsweise $f_2(0) = f_2(-2) = 1$. (Hinweis: Die Werte $m=0$ und $n=-2$ erfüllen exemplarisch den Zusammenhang $m = -n-2$, der sich als Lösung des zweiten Falls ergeben hat.)

Beispiel 3

Gegeben sei die Abbildung $f_3: \Z \rightarrow \Z \times \Z$ mit $n \mapsto \bigl(n^2,\ {(n+2)}^2\bigr)$. Um die Injektivität der Abbildung zu überprüfen, werden zunächst zwei Elemente $m$ und $n$ der Definitionsmenge $\Z$ gewählt und angenommen, dass diese dasselbe Bild haben; dann gilt:

\begin{align*} f_3(m) &= f_3(n) \\[0.5em] \bigl( m^2,\ {(m+2)}^2 \bigr) &= \bigl( n^2,\ {(n+2)}^2 \bigr). \end{align*}

Zwei Paare (allgemein: Tupel) stimmen überein, wenn sie komponentenweise übereinstimmen. Hieraus ergibt sich das folgende Gleichungssystem:

\begin{align*} m^2 &= n^2 \\[0.5em] {(m+2)}^2 &= {(n+2)}^2. \end{align*}

Ausrechnen der Quadrate der zweiten Gleichung mithilfe der ersten binomischen Formel und Abziehen der ersten Gleichung liefert:

\begin{align*} {(m+2)}^2 - m^2 &= {(n+2)}^2 - n^2 \\[0.5em] m^2 + 4m + 4 - m^2 &= n^2 + 4n + 4 - n^2 \\[0.5em] 4m + 4 &= 4n + 4 \\[0.5em] 4m &= 4n \\[0.5em] m &= n. \end{align*}

Da sich als einzige Lösung des Gleichungssystems die triviale Lösung $m=n$ ergibt, ist die Abbildung $f_3$ injektiv.

Beispiel 4

Gegeben sei die Abbildung $f_4: \Z \times \Z \rightarrow \Z \times \Z$ mit $\bigl(m,n\bigr) \mapsto \bigl(m+7,\ (m^2+1) \cdot n \bigr)$. Um die Injektivität der Abbildung zu überprüfen, werden zunächst zwei Elemente $\bigl(m,n\bigr)$ und $\bigl(x,y\bigr)$ der Definitionsmenge $\Z \times \Z$ gewählt und angenommen, dass diese dasselbe Bild haben; dann gilt:

\begin{align*} f_4(m,n) &= f_4(x,y) \\[0.5em] \bigl( m+7,\ (m^2+1) \cdot n \bigr) &= \bigl( x+7,\ (x^2+1) \cdot y \bigr). \end{align*}

Zwei Paare (allgemein: Tupel) stimmen überein, wenn sie komponentenweise übereinstimmen. Hieraus ergibt sich das folgende Gleichungssystem:

\begin{align*} m+7 &= x+7 \\[0.5em] \bigl( m^2 + 1 \bigr) \cdot n &= \bigl( x^2 + 1 \bigr) \cdot y. \end{align*}

Aus der ersten Gleichung ergibt sich unmittelbar:

\begin{align*} m+7 &= x+7 \\[0.5em] m &= x. \end{align*}

Einsetzen von $m=x$ in die zweite Gleichung und anschließende Division durch $m^2+1$ (dies ist erlaubt, da wegen $m^2 \geq 0$ stets $m^2+1 \neq 0$ gilt) liefert:

\begin{align*} \bigl( m^2 + 1 \bigr) \cdot n &= \bigl( x^2 + 1 \bigr) \cdot y \\[0.5em] \bigl( m^2 + 1 \bigr) \cdot n &= \bigl( m^2 + 1 \bigr) \cdot y \\[0.5em] n &= y. \end{align*}

Da sich als einzige Lösung des Gleichungssystems die triviale Lösung $\bigl( m,n \bigr) = \bigl( x,y \bigr)$ ergibt, ist die Abbildung $f_4$ injektiv.

Beispiel 5

Gegeben sei die Abbildung $f_5: \Z \times \Z \rightarrow \Z$ mit $\bigl(m, n\bigr) \mapsto 2m+n$.

Die Nicht-Injektivität kann mithilfe eines Gegenbeispiels gezeigt werden – es gilt beispielsweise $f_5(0,3) = f_5(1, 1) = 3$.

Eigenschaften

Für injektive Abbildungen gelten unter anderem die folgenden Eigenschaften:

Die Injektivität einer Abbildung $f: A \rightarrow B$ hängt ausschließlich vom Funktionsgraphen $\bigl\{ (a,f(a)) \mid a \in A \bigr\}$ ab.
Eine Abbildung $f: A \rightarrow B$ ist genau dann injektiv, wenn für alle Teilmengen $A_1,A_2 \subseteq A$ stets die folgende Eigenschaft gilt: $f(A_1 \cap A_2) = f(A_1) \cap f(A_2).$ In Worten: Das Bild der Schnittmenge von $A_1$ und $A_2$ entspricht der Schnittmenge der Bilder.
Eine Abbildung $f: A \rightarrow B$ ist genau dann injektiv, wenn für alle Teilmengen $S \subseteq A$ die folgende Eigenschaft gilt: $f^{-1} \bigl( f(S) \bigr) = S.$ Mit $f^{-1}$ ist hierbei die Urbildfunktion bezeichnet.
Für injektive Abbildungen $f: A \rightarrow B$ und $g: B \rightarrow C$ ist auch die Komposition $g \circ f$ eine injektive Abbildung.
Für Abbildungen $f: A \rightarrow B$ und $g: B \rightarrow C$ folgt aus der Injektivität der Komposition $g \circ f$ stets die Injektivität der Abbildung $f$.
Eine Abbildung $f: A \rightarrow B$ mit nichtleerer Definitionsmenge $A$ ist genau dann injektiv, wenn sie eine Linksinverse besitzt, wenn also eine Abbildung $g: B \rightarrow A$ existiert, für die $g \circ f = \id_A$ gilt. Mit $\id_A$ ist hierbei die identische Abbildung auf $A$ bezeichnet.
Eine Abbildung $f: A \rightarrow B$ ist genau dann injektiv, wenn sie linkskürzbar ist, d. h., wenn für beliebige Abbildungen $g,h: C \rightarrow A$ stets die folgende Aussage gilt: $f \circ g = f \circ h \Rightarrow g = h.$
Eine stetige reellwertige Funktion auf einem reellen Intervall ist genau dann injektiv, wenn sie auf ihrem gesamten Definitionsbereich streng monoton steigend oder streng monoton fallend ist.
Ein Gruppenhomomorphismus ist genau dann injektiv, wenn sein Kern trivial ist, wenn der Kern also nur aus dem neutralen Element besteht.
Eine lineare Abbildung (ein Vektorraumhomomorphismus) ist genau dann injektiv, wenn sein Kern trivial ist, wenn der Kern also nur aus dem Nullvektor besteht.
Eine lineare Abbildung $f: V \rightarrow W$ ist genau dann injektiv, wenn die Bilder $f(b_1), \ldots, f(b_n) \in W$ der Basisvektoren $b_1,\ldots,b_n \in V$ linear unabhängig sind.
Eine lineare Abbildung ist genau dann injektiv, wenn die Spalten der zugehörigen Abbildungsmatrix linear unabhängig sind.

Mächtigkeit von Mengen

Hauptartikel: Mächtigkeit einer Menge

Der Begriff der Injektivität spielt eine wichtige Rolle beim Vergleich der Mächtigkeiten von Mengen.

Zwei Mengen $A$ und $B$ heißen gleichmächtig, wenn es sowohl injektive Abbildungen $A \rightarrow B$ als auch injektive Abbildungen $B \rightarrow A$ gibt. (In diesem Fall existieren stets auch bijektive Abbildungen $A \rightarrow B$.)
Die Menge $A$ heißt weniger mächtig als die Menge $B$, wenn es zwar injektive Abbildungen $A \rightarrow B$ gibt, aber keine injektiven Abbildungen $B \rightarrow A$ existieren.

Anzahl injektiver Abbildungen

Die Anzahl der injektiven Abbildungen $A \rightarrow B$ von einer Definitionsmenge $A$ in eine Zielmenge $B$ mit $|B| \geq |A|$ kann mithilfe der fallenden Faktoriellen berechnet werden. Es existieren genau

\begin{align*} {|B|}^{\underline{|A|}} &= |B| \cdot \bigl( |B| - 1 \bigr) \cdot \ldots \cdot \bigl( [B| - |A| + 1 \bigr) \\[0.5em] &= \frac{|B|!}{\bigl( |B| - |A| \bigr)!} \\[0.5em] &= |A|! \cdot \binom{|B|}{|A|} \end{align*}

injektive Abbildung $A \rightarrow B$.