Nachlesen

Surjektivität

Bei einer surjektiven Funktion bzw. surjektiven Abbildung (auch Surjektion genannt) handelt es sich um eine Abbildung, bei der jedes Element der Zielmenge mindestens ein Urbild besitzt. Allgemein: Bei einer surjektiven Funktion handelt es sich um eine Relation, die rechtseindeutig sowie links- und rechtstotal ist.

Inhalt

Definition
Beispiele
Nachweis der Surjektivität
Eigenschaften
Mächtigkeit von Mengen
Anzahl surjektiver Abbildungen

Definition

Gegeben seien zwei Mengen $A$ und $B$ sowie eine Funktion bzw. Abbildung $f: A \rightarrow B$. Die Abbildung $f$ heißt surjektiv, wenn für alle Elemente $b$ der Zielmenge $B$ stets ein Element $a$ der Definitionsmenge $A$ existiert, das durch die Abbildung $f$ auf $b$ abgebildet wird, für das also $f(a)=b$ gilt:

\forall b \in B \Bigl( \exists a \in A \bigl( f(a)=b \bigr) \Bigr).

Da alle Elemente der Zielmenge bei einer surjektiven Abbildung stets ein Urbild besitzen müssen, kann die Definitionsmenge nicht weniger mächtig als die Zielmenge sein. Da es für eine surjektive Abbildung jedoch nicht erforderlich ist, dass jedes Element der Zielmenge exakt ein Urbild besitzt, kann die Definitionsmenge auch mächtiger als die Zielmenge sein. Für surjektive Abbildungen gilt somit:

|A| \geq |B|.

Beispiele

Bei den folgenden Beispielen handelt es sich um surjektive Abbildungen:

Die Abbildung $f_1: \N \rightarrow \N$, $n \mapsto n$ ist surjektiv.
Die Abbildung $f_2: \Z \rightarrow \Z$, $n \mapsto n+3$ ist surjektiv.
Die Abbildung $f_3: \Z \times \Z \rightarrow \Z$, $(m,n) \mapsto 2m+n$ ist surjektiv.
Die Abbildung $f_4: \Z \times \N \rightarrow \Q$, $(m,n) \mapsto \frac{m}{n}$ ist surjektiv.

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

Die Abbildung $f_1: \N \rightarrow \N$, $n \mapsto n+1$ ist nicht surjektiv.
Die Abbildung $f_2: \Z \rightarrow \Z$, $n \mapsto 2n+1$ ist nicht surjektiv.
Die Abbildung $f_3: \Z \rightarrow \Z$, $n \mapsto n^2$ ist nicht surjektiv.
Jede Abbildung $f_4: A \rightarrow B$ mit $A = \bigl\{ a \bigr\}$ und $B = \bigl\{ b_1,b_2 \bigr\}$ ist nicht surjektiv, da $|A| \lt |B|$ gilt.

Nachweis der Surjektivität

Zum Nachweis der Surjektivität einer Abbildung $f: A \rightarrow B$ muss gezeigt werden, dass jedes Element $b$ der Zielmenge $B$ mindestens ein Urbild $a$ in der Definitionsmenge $A$ besitzt, dass also stets ein Element $a \in A$ mit $f(a)=b$ existiert. Während dies für endliche Mengen $B$ durch direkte Angabe der Urbilder gezeigt werden kann, ist dies bei unendlichen Mengen nicht möglich. In diesem Fall ist es sinnvoll, ein beliebiges Element $b \in B$ zu betrachten und – falls existent – ein Urbild $a \in A$ mit $f(a)=b$ in Abhängigkeit von $b$ zu bestimmen. Dies geschieht im Wesentlichen in zwei Schritten:

Finden einer Vermutung für ein Urbild $a \in A$ für das Element $b$ und sicherstellen, dass dieses in der Definitionsmenge $A$ tatsächlich enthalten ist.
Überprüfen, ob das vermutete Urbild durch die Abbildung $f: A \rightarrow B$ tatsächlich auf $b$ abgebildet wird.

Hinweis: Es ist nicht notwendig, alle Urbilder des Elements $b$ zu bestimmen; es genügt zu zeigen, dass mindestens ein Urbild existiert.

Die Nicht-Surjektivität einer Abbildung $f: A \rightarrow B$ kann alternativ auch durch die Angabe eines Gegenbeispiels gezeigt werden, indem ein Elemente $b \in B$ angegeben wird, für das kein $a \in A$ mit $f(a)=b$ existiert.

Beispiel 1

Gegeben sei die Abbildung $f_1: \Z \rightarrow \Z$ mit $n \mapsto n+3$. Um die Surjektivität der Abbildung zu prüfen, wird zunächst ein beliebiges Element $b$ der Zielmenge $\Z$ gewählt und versucht, ein Element $a$ der Definitionsmenge $\Z$ mit $f_1(a)=b$ zu finden; es gilt:

\begin{align*} f_1(a) &= b \\[0.5em] a+3 &= b. \end{align*}

Anschließendes Umstellen der Gleichung nach $a$ liefert:

\begin{align*} a+3 &= b \\[0.5em] a &= \underbrace{b-3}_{\in \Z}. \end{align*}

Da es sich bei $a = b-3$ um eine ganze Zahl handelt, ist das Element in der Definitionsmenge $\Z$ enthalten. Abschließend muss noch überprüft werden, ob das vermutete Urbild $a$ tatsächlich auf $b$ abgebildet wird:

\begin{align*} f_1(a) &= f_1(b-3) \\[0.5em] &= b-3 + 3 \\[0.5em] &= b. \end{align*}

Beim Element $a = b-3$ handelt es sich folglich um ein Urbild von $b$. Die Abbildung $f_1$ ist somit surjektiv.

Beispiel 2

Gegeben sei die Abbildung $f_2: \Z \rightarrow \Z$ mit $n \mapsto 2n+1$. Um die Surjektivität der Abbildung zu prüfen, wird zunächst ein beliebiges Element $b$ der Zielmenge $\Z$ gewählt und versucht, ein Element $a$ der Definitionsmenge $\Z$ mit $f_2(a)=b$ zu finden; es gilt:

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

Anschließendes Umstellen der Gleichung nach $a$ liefert:

\begin{align*} 2a+1 &= b \\[0.5em] a &= \frac{b-1}{2}. \end{align*}

Bei $a = \frac{b-1}{2}$ handelt es sich nur dann um eine ganze Zahl, wenn $b-1$ eine gerade Zahl ist, wenn $b$ selbst also ungerade ist. Für alle geraden Werte $b$ existiert folglich kein ganzzahliges Urbild $a$ in der Definitionsmenge $A$, sodass die Abbildung $f_2$ nicht surjektiv ist.

Hinweis: Alternativ hätte die Nicht-Surjektivität über ein Gegenbeispiel bewiesen werden können, indem beispielsweise gezeigt wird, dass kein $a \in \Z$ mit $f_2(a)=0$ existiert.

Beispiel 3

Gegeben sei die Abbildung $f_3: \Z \rightarrow \Z \times \Z$ mit $n \mapsto (n-1,n+1)$. Um die Surjektivität der Abbildung zu prüfen, wird zunächst ein beliebiges Element $(b_1,b_2)$ der Zielmenge $\Z \times \Z$ gewählt und versucht, ein Element $a$ der Definitionsmenge $\Z$ mit $f_3(a)=(b_1,b_2)$ zu finden; es gilt:

\begin{align*} f_3(a) &= \bigl( b_1,b_2 \bigr) \\[0.5em] \bigl( a-1, a+1 \bigr) &= \bigl( b_1, b_2 \bigr). \end{align*}

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

\begin{align*} a-1 &= b_1 \\[0.5em] \Rightarrow a &= b_1 + 1 \\[1em] a+1 &= b_2 \\[0.5em] \Rightarrow a &= b_2 - 1. \end{align*}

Das Gleichungssystem ist nur dann lösbar, wenn zeitgleich $a = b_1+1$ und $a = b_2-1$ gilt, wenn also $b_1+1 = b_2-1$ bzw. $b_2 = b_1+2$ gilt. Da dies für beliebige $b_1$ und $b_2$ im Allgemeinen nicht gilt, existiert im Allgemeinen folglich auch kein Wert $a$ als Lösung des Gleichungssystems und somit kein Urbild für das Element $(b_1,b_2)$ der Zielmenge, womit die Abbildung $f_3$ nicht surjektiv ist.

Hinweis: Alternativ hätte die Nicht-Surjektivität über ein Gegenbeispiel bewiesen werden können, indem beispielsweise gezeigt wird, dass kein $a \in \Z$ mit $f_3(a)=(0,0)$ existiert.

Beispiel 4

Gegeben sei die Abbildung $f_4: \Z \times \Z \rightarrow \Z$ mit $(m,n) \mapsto 2m+n$. Um die Surjektivität der Abbildung zu prüfen, wird zunächst ein beliebiges Element $b$ der Zielmenge $\Z$ gewählt und versucht, ein Element $(a_1,a_2)$ der Definitionsmenge $\Z \times \Z$ mit $f_4(a_1,a_2)=b$ zu finden; es gilt:

\begin{align*} f_4(a_1,a_2) &= b \\[0.5em] 2a_1+a_2 &= b. \end{align*}

Die resultierende Gleichung ist unterbestimmt. Da es für den Nachweis der Surjektivität genügt, die Existenz eines Urbilds zu zeigen, ist es ausreichend, eine Lösung der Gleichung zu finden. Hierzu kann der Wert einer der Variablen $a_1$ oder $a_2$ beliebig gewählt werden und dann die resultierende Gleichung gelöst werden. Für dieses Beispiel wird $a_1=0$ gewählt. (Hinweis: Es ist möglich, dass nicht jede Wahl zu einer gültigen Lösung führt.)

\begin{align*} 2a_1 + a_2 &= b\\[0.5em] 2 \cdot 0 + a_2 &= b \\[0.5em] a_2 &= b. \end{align*}

Da es sich sowohl bei $a_1=0$ als auch bei $a_2=b$ um ganze Zahlen handelt, ist das Paar $(a_1,a_2)=(0,b)$ in der Definitionsmenge $\Z \times \Z$ vorhanden und folglich ein potenzielles Urbild für $b$. Abschließend muss noch überprüft werden, ob das vermutete Urbild $(0,b)$ tatsächlich auf $b$ abgebildet wird:

\begin{align*} f_4(0,b) &= 2 \cdot 0 + b \\[0.5em] &= b. \end{align*}

Beim Element $(0,b)$ handelt es sich folglich um ein Urbild von $b$. Die Abbildung $f_4$ ist somit surjektiv.

Beispiel 5

Gegeben sei die Abbildung $f_5: \Z \times \Z \rightarrow \Z \times \Z$ mit $(m,n) \mapsto (7m+3n+1, 2m+n)$. Um die Surjektivität der Abbildung zu prüfen, wird zunächst ein beliebiges Element $(b_1,b_2)$ der Zielmenge $\Z \times \Z$ gewählt und versucht, ein Element $(a_1,a_2)$ der Definitionsmenge $\Z \times \Z$ mit $f_5(a_1,a_2)=(b_1,b_2)$ zu finden; es gilt:

\begin{align*} f_5(a_1,a_2) &= (b_1,b_2) \\[0.5em] \bigl( 7a_1+3a_2+1, 2a_1+a_2 \bigr) &= (b_1, b_2). \end{align*}

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

\begin{align*} 7a_1 + 3a_2 + 1 &= b_1 \\[0.5em] 2a_1 + a_2 &= b_2. \end{align*}

Abziehen des dreifachen der zweiten Gleichung von der ersten Gleichung liefert:

\begin{align*} 7a_1 + 3a_2 + 1 - 3 \cdot \bigl( 2a_1 + a_2 \bigr) &= b_1 - 3b_2 \\[0.5em] 7a_1 + 3a_2 + 1 - 6a_1 - 3a_2 &= b_1 - 3b_2 \\[0.5em] a_1 + 1 &= b_1 - 3b_2 \\[0.5em] \Rightarrow a_1 &= b_1 - 3b_2 - 1. \end{align*}

Einsetzen von $a_1$ in die zweite Gleichung liefert:

\begin{align*} 2a_1 + a_2 &= b_2 \\[0.5em] 2 \cdot \bigl( b_1 - 3b_2 - 1 \bigr) + a_2 &= b_2 \\[0.5em] 2b_1 - 6b_2 - 2 + a_2 &= b_2 \\[0.5em] \Rightarrow a_2 &= -2b_1 + 7b_2 + 2. \end{align*}

Da es sich sowohl bei $a_1=b_1-3b_2-1$ als auch bei $a_2=-2b_1+7b_2+2$ um ganze Zahlen handelt, ist das Paar $(a_1,a_2)$ in der Definitionsmenge $\Z \times \Z$ vorhanden und folglich ein potenzielles Urbild für $(b_1,b_2)$. Abschließend muss noch überprüft werden, ob das vermutete Urbild tatsächlich auf $(b_1,b_2)$ abgebildet wird:

\begin{align*} f_5(a_1,a_2) &= f_5(b_1-3b_2-1, -2b_1+7b_2+2) \\[0.5em] &= \bigl( 7 \cdot (b_1-3b_2-1) + 3 \cdot (-2b_1+7b_2+2) + 1, 2 \cdot (b_1-3b_2-1) -2b_1+7b_2+2 \bigr) \\[0.5em] &= \bigl( 7b_1 - 21b_2 - 7 - 6b_1 + 21b_2 + 6 + 1, 2b_1 - 6b_2 - 2 - 2b_1 + 7b_2 + 2 \bigr) \\[0.5em] &= \big( b_1, b_2 \bigr). \end{align*}

Beim Element $(b_1-3b_2-1,-2b_1+7b_2+2)$ handelt es sich folglich um ein Urbild von $(b_1,b_2)$. Die Abbildung $f_5$ ist somit surjektiv.

Beispiel 6

Gegeben sei die Abbildung $f_6: \Z \times \Z \rightarrow \Z \times \Z \times \Z$ mit $(m,n) \mapsto (n^3m^2, n^2+1, 2mn)$. Diese ist nicht surjektiv, da beispielsweise keine ganze Zahl $n \in \Z$ existiert, so dass

f_6(m,n) = (\star,0,\star)

gilt, da hierfür $n^2+1=0$ gelten müsste, was im Bereich der ganzen Zahlen nicht lösbar ist. Die mit $\star$ markierten Einträge spielen hierbei keine Rolle und können für den Nachweis der Nicht-Surjektivität ignoriert werden.

Eigenschaften

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

Die Surjektivität einer Abbildung $f: A \rightarrow B$ hängt nicht ausschließlich vom Funktionsgraphen $\bigl\{ (a,f(a)) \mid a \in A \bigr\}$ ab, sondern ebenfalls von der Zielmenge $B$.
Eine Abbildung $f: A \rightarrow B$ ist genau dann surjektiv, wenn für alle Teilmengen $S \subseteq B$ die folgende Eigenschaft gilt: $f \bigl( f^{-1}(S) \bigr) = S.$ Mit $f^{-1}$ ist hierbei die Urbildfunktion bezeichnet.
Für surjektive Abbildungen $f: A \rightarrow B$ und $g: B \rightarrow C$ ist auch die Komposition $g \circ f$ eine surjektive Abbildung.
Für Abbildungen $f: A \rightarrow B$ und $g: B \rightarrow C$ folgt aus der Surjektivität der Komposition $g \circ f$ stets die Surjektivität der Abbildung $g$.
Eine Abbildung $f: A \rightarrow B$ ist genau dann surjektiv, wenn sie eine Rechtsinverse besitzt, wenn also eine Abbildung $g: B \rightarrow A$ existiert, für die $f \circ g = \id_B$ gilt. Mit $\id_B$ ist hierbei die identische Abbildung auf $B$ bezeichnet.
Eine Abbildung $f: A \rightarrow B$ ist genau dann surjektiv, wenn sie rechtskürzbar ist, d. h., wenn für beliebige Abbildungen $g,h: B \rightarrow C$ stets die folgende Aussage gilt: $g \circ f = h \circ f \Rightarrow g = h.$
Ein Gruppenhomomorphismus $\varphi: G_1 \rightarrow G_2$ ist genau dann surjektiv, wenn das Bild von $\varphi$ der Gruppe $G_2$ entspricht, wenn also $\Bild{(\varphi)} = G_2$ gilt.
Eine lineare Abbildung $f: V \rightarrow W$ (ein Vektorraumhomomorphismus) ist genau dann surjektiv, wenn die Bilder $f(b_1),\ldots,f(b_n) \in W$ der Basisvektoren $b_1,\ldots,b_n \in V$ ein Erzeugendensystem des Vektorraums $W$ bilden.
Eine lineare Abbildung $f: V \rightarrow W$ ist genau dann surjektiv, wenn der Rang der zugehörigen Abbildungsmatrix gleich der Dimension des Vektorraums $W$ ist.

Mächtigkeit von Mengen

Hauptartikel: Mächtigkeit einer Menge

Der Begriff der Surjektivität kann verwendet werden, um die Mächtigkeiten von Mengen zu vergleichen.

Für endliche Mengen $A$ und $B$ gilt: Existieren surjektive Abbildungen $A \rightarrow B$, dann kann die Zielmenge $B$ höchstens so viele Elemente wie die Definitionsmenge $A$ besitzen; es gilt also $|B| \leq |A|$.
Für unendliche Mengen wird der Vergleich der Mächtigkeiten von Mengen $A$ und $B$ mithilfe von injektiven Abbildungen definiert, jedoch gilt auch hier: Ist $A \rightarrow B$ surjektiv, dann ist die Mächtigkeit von $B$ höchstens so groß wie die Mächtigkeit von $A$; es gilt also ebenfalls $|B| \leq |A|$.

Anzahl surjektiver Abbildungen

Die Anzahl der surjektiven Abbildungen $A \rightarrow B$ von einer Definitionsmenge $A$ in eine Zielmenge $B$ mit $|A| \geq |B|$ kann mithilfe der Stirling-Zahlen zweiter Art berechnet werden. Es existieren genau

|B|! \cdot S_{|A|,|B|}

surjektive Abbildung $A \rightarrow B$.

Für gleichmächtige Mengen $A$ und $B$ kann die Anzahl der surjektiven Abbildungen $A \rightarrow B$ alternativ auch über die Anzahl der injektiven Abbildungen berechnet werden, da jede surjektive Abbildung zwischen gleichmächtigen Mengen stets auch injektiv ist.