Über injektive, surjektive und bijektive Abbildungen

Injektive, surjektive und bijektive Abbildungen sind wichtige Klassen von Abbildungen. Sie werden in diesem Artikel mit der Lösbarkeit von Gleichungen einfach erklärt und mit Hilfe von Bild und Kern charakterisiert. Zum besseren Verständnis werden außerdem sehr viele Beispiele vorgestellt (30 Stück). Anschließend geben wir auch einige Charakterisierungen an, die mit Kürzungs- und Liftungseigenschaften arbeiten. Mit ihnen wird deutlich, dass Injektivität und Surjektivität zueinander "duale" Konzepte sind. Der Artikel richtet sich an Studienanfänger.

Definition

Bei injektiven, surjektiven und bijektiven Abbildungen geht es grob gesagt darum, die Lösbarkeit von speziellen Gleichungen zu untersuchen. Bei einer Gleichung gibt es grundsätzlich mehrere Möglichkeiten:

• Die Gleichung hat höchstens eine Lösung.
  Das heißt, entweder gibt es gar keine Lösung, oder genau eine. Man kann das auch so ausdrücken: Je zwei Lösungen der Gleichung sind identisch. Zum Beispiel hat für festes $y \in \IN$ die Gleichung $x+1=y$ höchstens eine Lösung $x \in \IN$ (genau eine für $y \geq 1$, und keine für $y=0$).
• Die Gleichung hat mindestens eine Lösung.
  Das heißt, es gibt auf jeden Fall eine Lösung, und eventuell noch weitere. Zum Beispiel hat die Gleichung $x^2=1$ mindestens eine Lösung $x \in \IR$, nämlich zwei Stück.
• Die Gleichung hat genau eine Lösung.
  Das ist der beste Fall und eine Kombination der beiden vorigen Fälle: Es gibt höchstens eine und zugleich mindestens eine Lösung. Zum Beispiel hat die Gleichung $x+1=3$ genau eine Lösung $x \in \IZ$.

Die Gleichungen in den Beispielen sind vom Typ $f(x)=y$ für eine Abbildung $f$ und einem festen Element $y$. Dies bringt uns zur folgenden Definition. Sei $f : X \to Y$ eine Abbildung. Wir nennen

• $f$ injektiv oder auch eine Injektion, wenn es für jedes $y \in Y$ höchstens ein $x \in X$ gibt mit $f(x) = y$.
• $f$ surjektiv oder auch eine Surjektion, wenn es für jedes $y \in Y$ mindestens ein $x \in X$ gibt mit $f(x) = y$.
• $f$ bijektiv oder auch eine Bijektion, wenn es für jedes $y \in Y$ genau ein $x \in X$ gibt mit $f(x) = y$.

Wenn $f(x)=y$, nennen wir $x$ ein Urbild von $y$ (bezüglich $f$). Die Definition lässt sich daher auch so fassen:

• $f : X \to Y$ ist injektiv, wenn jedes Element von $Y$ höchstens ein Urbild in $X$ besitzt.
• $f : X \to Y$ ist surjektiv, wenn jedes Element von $Y$ mindestens ein Urbild in $X$ besitzt.
• $f : X \to Y$ ist bijektiv, wenn jedes Element von $Y$ genau ein Urbild in $X$ besitzt.

Dass $f$ bijektiv ist, bedeutet, dass sich die Gleichung $f(x)=y$ immer eindeutig nach $x$ auflösen lässt. Beispiele werden wir später besprechen. Bei der Definition oben sind die Mengen $X,Y$ völlig beliebig. Es könnten Mengen von Zahlen sein, aber auch Mengen von geordneten Paaren, oder sogar noch abstraktere Mengen. Zum Beispiel ist eine Abbildung $f : \IR^2 \to \IR^2$ genau dann bijektiv (bzw. injektiv, bzw. surjektiv) gemäß der allgemeinen Definition, wenn es für alle (hier muss man nun irgendwelche Variablennamen wählen) $(u,v) \in \IR^2$ genau ein (bzw. höchstens ein, bzw. mindestens ein) $(x,y) \in \IR^2$ existiert mit $f((x,y)) = (u,v)$. Hierbei schreibt man oftmals $f(x,y)$ anstelle von $f((x,y))$, aber das lenkt eventuell davon ab, dass es sich auch bei $f$ um eine ganz gewöhnliche Abbildung mit nur einem Argument handelt. Injektive, surjektive und bijektive Abbildungen haben eine wichtige Eigenschaft: Man könnte sich fragen, warum wir bei der Anzahl der Lösungen der Gleichung $f(x) = y$ eigentlich die $1$ als die kritische Zahl genommen haben. Wir könnten zum Beispiel auch eine Abbildung $f : X \to Y$ duojektiv nennen (fiktiver Name), wenn jedes $y \in Y$ genau zwei Urbilder besitzt. Zum Beispiel ist $f : \IR^* \to \IR^*$, $f(x) = x^2$ duojektiv. Nun, erstens gibt es nicht so viele duojektive Abbildungen in der Praxis. Zweitens sind sie nicht unter Komposition stabil (die Eigenschaft in Aufgabe 1). Und drittens besitzen sie keine nützlichen Charakterisierungen wie jene, die weiter unten für injektive, surjektive und bijektive Abbidlungen vorgestellt werden.

Veranschaulichung

Stellen wir uns eine Abbildung $f : X \to Y$ als einen Graphen vor, der die Elemente von $X$ und von $Y$ als Knoten besitzt und bei dem jedes Element von $X$ mit seinem Bild in $Y$ durch einen Pfeil verbunden wird. Dass $f$ eine Abbildung ist, bedeutet gerade, dass jedes Element von $X$ mit genau einem Element von $Y$ verbunden ist. Bei Fragen der Injektivität, Surjektivität und Bijektivität geht es um die andere Richtung, also darum, wieviele Elemente von $X$ mit einem gegebenen Element von $Y$ verbunden sind. Dass $f$ injektiv ist, bedeutet, dass jedes Element von $Y$ mit höchstens einem Element von $X$ verbunden ist. Die folgende Abbildung ist demnach injektiv, aber nicht surjektiv. $\backslash begin\{tikzpicture\}[>=latex,nodes=\{inner\; sep=1pt\}]\; \backslash draw[darkgray,dashed]\; (0,0)\; ellipse\; (1.2\; and\; 1.2);\; \backslash draw[darkgray,dashed]\; (5.5,0)\; ellipse\; (2.2\; and\; 1.2);\; \backslash node\; at\; (0,-1.2)\; [below=1ex]\; \{\$X\$\};\; \backslash node\; at\; (5.5,-1.2)\; [below=1ex]\; \{\$Y\$\};\; \backslash node\; at\; (2.5,-1.2)\; \{\$f\$\; injektiv\};\; \backslash node\; (x1)\; at\; (0.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (x2)\; at\; (-0.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (x3)\; at\; (0.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (x4)\; at\; (-0.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y1)\; at\; (5.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y2)\; at\; (4.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y3)\; at\; (5.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y4)\; at\; (4.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y5)\; at\; (6.5,+0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y6)\; at\; (6.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash draw[red,->,bend\; left=10]\; (x1)\; to\; (y4);\; \backslash draw[orange,->,bend\; right=18]\; (x2)\; to\; (y6);\; \backslash draw[brown,->,bend\; right=13]\; (x3)\; to\; (y2);\; \backslash draw[blue,->,bend\; left=20]\; (x4)\; to\; (y1);\; \backslash end\{tikzpicture\}$ Dass $f$ surjektiv ist, bedeutet, dass jedes Element von $Y$ mit mindestens einem Element von $X$ verbunden ist; man sagt auch, dass es von einem Element von $X$ getroffen wird. Die folgende Abbildung ist demnach surjektiv, aber nicht injektiv (zum Beispiel weil die beiden blauen Pfeile dasselbe Ziel haben). $\backslash begin\{tikzpicture\}[>=latex,nodes=\{inner\; sep=1pt\}]\; \backslash draw[darkgray,dashed]\; (-0.5,0)\; ellipse\; (2.2\; and\; 1.2);\; \backslash draw[darkgray,dashed]\; (5,0)\; ellipse\; (1.2\; and\; 1.2);\; \backslash node\; at\; (-0.5,-1.2)\; [below=1ex]\; \{\$X\$\};\; \backslash node\; at\; (5,-1.2)\; [below=1ex]\; \{\$Y\$\};\; \backslash node\; at\; (2.5,-1.2)\; \{\$f\$\; surjektiv\};\; \backslash node\; (x1)\; at\; (0.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (x2)\; at\; (-0.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (x3)\; at\; (0.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (x4)\; at\; (-0.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (x5)\; at\; (-1.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (x6)\; at\; (-1.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y1)\; at\; (5.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y2)\; at\; (4.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y3)\; at\; (5.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y4)\; at\; (4.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash draw[red,->,bend\; left=10]\; (x1)\; to\; (y3);\; \backslash draw[red,->,bend\; left=10]\; (x5)\; to\; (y3);\; \backslash draw[orange,->,bend\; right=16]\; (x2)\; to\; (y4);\; \backslash draw[brown,->,bend\; right=13]\; (x3)\; to\; (y2);\; \backslash draw[blue,->,bend\; left=20]\; (x4)\; to\; (y1);\; \backslash draw[blue,->,bend\; left=20]\; (x6)\; to\; (y1);\; \backslash end\{tikzpicture\}$ Die Bijektivität von $f$ bedeutet demnach, dass jedes Element von $Y$ mit genau einem Element von $X$ verbunden ist. Die Zuordnung funktioniert also in beide Richtungen als Abbildung. $\backslash begin\{tikzpicture\}[>=latex,nodes=\{inner\; sep=1pt\}]\; \backslash draw[darkgray,dashed]\; (0,0)\; ellipse\; (1.2\; and\; 1.2);\; \backslash draw[darkgray,dashed]\; (5,0)\; ellipse\; (1.2\; and\; 1.2);\; \backslash node\; at\; (0,-1.2)\; [below=1ex]\; \{\$X\$\};\; \backslash node\; at\; (5,-1.2)\; [below=1ex]\; \{\$Y\$\};\; \backslash node\; at\; (2.5,-1.2)\; \{\$f\$\; bijektiv\};\; \backslash node\; (x1)\; at\; (0.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (x2)\; at\; (-0.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (x3)\; at\; (0.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (x4)\; at\; (-0.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y1)\; at\; (5.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y2)\; at\; (4.5,0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y3)\; at\; (5.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash node\; (y4)\; at\; (4.5,-0.5)\; \{\backslash large\$\backslash bullet\$\};\; \backslash draw[red,->,bend\; left=10]\; (x1)\; to\; (y3);\; \backslash draw[orange,->,bend\; right=16]\; (x2)\; to\; (y4);\; \backslash draw[brown,->,bend\; right=13]\; (x3)\; to\; (y2);\; \backslash draw[blue,->,bend\; left=20]\; (x4)\; to\; (y1);\; \backslash end\{tikzpicture\}$

Charakterisierungen

Es sei $f : X \to Y$ eine Abbildung. Aus unseren Bemerkungen über die Lösbarkeit von Gleichungen folgt, dass $f$ genau dann injektiv ist, wenn je zwei Urbilder eines $y \in Y$ gleich sind, das heißt also, dass für alle $x,x' \in X$ gilt: $f(x)=f(x') \implies x=x'.$ Außerdem ist $f$ genau dann bijektiv, wenn $f$ injektiv und surjektiv ist. Das sollte aber kein Anlass sein, die Bijektivität immer über Injektivität und Surjektivität zu beweisen (siehe die Beispiele unten), weil es mit der Definition, also die eindeutige Lösbarkeit von $f(x)=y$, oftmals einfacher geht. Auch das folgende Lemma ist für den Nachweis in vielen Fällen sehr praktisch. Wenn nämlich $f$ bijektiv ist, definieren wir $g(y)$ als das eindeutig bestimmte Urbild von $y$ bezüglich $f$. Es gilt also $f(g(y))=y$ für alle $y \in Y$ nach Konstruktion, und $g(f(x))=x$ gilt ebenfalls für alle $x \in X$, weil $x$ und $g(f(x))$ Urbilder von $f(x)$ sind, also gleich sein müssen. Wenn umgekehrt eine Abbildung $g$ wie oben existiert, dann zeigt die Gleichung $f(g(y))=y$ für $y \in Y$, dass $f$ surjektiv ist, und aus $f(x)=f(x')$ folgt $x=g(f(x))=g(f(x'))=x'$, sodass $f$ auch injektiv ist. Also ist $f$ bijektiv. $\checkmark$ Dieser Beweis zeigt auch, dass die Abbildung $g : Y \to X$ eindeutig durch $f : X \to Y$ bestimmt ist: es muss $g(y)$ das eindeutige Urbild von $y$ bezüglich $f$ sein. Man notiert sie mit $f^{-1}$ und nennt sie die zu $f$ inverse Abbildung. Es gilt also $f \circ f^{-1}=\mathrm{id}_Y$ und $f^{-1} \circ f = \mathrm{id}_X$. Eine Abbildung ist also genau dann bijektiv, wenn sie eine inverse Abbildung besitzt. Dieses Kriterium ist tatsächlich oftmals sehr praktisch, um die Bijektivtät nachzuweisen.

Bild und Kern

Aus jeder Abbildung $f : X \to Y$ können wir eine surjektive Abbildung bauen, indem wir die Zielmenge verkleinern: Sei dazu $Z \subseteq Y$ die Teilmenge der $y \in Y$, die mindestens ein Urbild bezüglich $f$ haben, also $Z = \{f(x) : x \in X\}$. Dann schränkt sich $f$ zu einer Abbildung $p : X \to Z$, $p(x):=f(x)$ ein (die oftmals auch mit $f$ notiert wird, auch wenn sie nicht gleich sind), die nach Konstruktion surjektiv ist. Wenn $f$ injektiv ist, dann ist $p$ immer noch injektiv und daher bijektiv. Aus jeder injektiven Abbildung gewinnt man so also eine bijektive Abbildung. Man nennt $\mathrm{Bild}(f) := \{f(x) : x \in X\}$ auch das Bild von $f$. Eine Abbildung $f : X \to Y$ ist gemäß der Definitionen genau dann surjektiv, wenn $Y = \mathrm{Bild}(f)$. Wir definieren nämlich $p : X \to \mathrm{Bild}(f)$ wie oben und $i : \mathrm{Bild}(f) \to Y$, $i(y) := y$ als die Inklusionsabbildung, die natürlich injektiv ist. Es gibt auch eine ähnliche Charakterisierung der Injektivität. Wir definieren dazu den Kern durch $\mathrm{Kern}(f) := \{(x,x') \in X \times X : f(x)=f(x')\}$. Das ist eine Teilmenge von $X \times X$, genauer gesagt eine Äquivalenzrelation. Sie enthält die sogenannte Diagonale $\Delta_X := \{(x,x) : x \in X\}$, also $\Delta_X \subseteq \mathrm{Kern}(f)$. Dann ist $f$ genau dann injektiv, wenn $\Delta_X = \mathrm{Kern}(f)$. Das ist wieder nur eine Umformulierung der Definition, nichts weiter. Eine Abbildung ist demnach surjektiv, wenn ihr Bild so groß wie möglich ist, und sie ist injektiv, wenn ihr Kern so klein wie möglich ist.

Klassifikation

Wir können injektive und surjektive Abbildungen in einem gewissen Sinne klassifizieren, also alle angeben: Für jede Teilmenge $Z \subseteq Y$ ist natürlich die Inklusionsabbildung $i : Z \to Y$, $i(y) := y$ injektiv. Für jede bijektive Abbildung $f : X \to Z$ ist dann aus formalen Gründen $i \circ f : X \to Z$ ebenfalls injektiv (siehe Aufgabe 1). Tatsächlich hat jede Injektion diese Form, was bedeutet, dass Inklusionen von Teilmengen im Wesentlichen alle Injektionen sind. Diese Aussage geht aus unseren Beobachtungen zum Bild oben hervor. Für jede Äquivalenzrelation $\sim$ auf einer Menge $X$ ist die Projektion $p : X \to X / {\sim}$, $p(x) := [x]$ auf die Menge der Äquivalenzklassen per Definition surjektiv. Für jede Bijektion $f : X / {\sim} \to Y$ ist dann $f \circ p : X \to Y$ aus formalen Gründen ebenfalls bijektiv. Aus Aufgabe 2 unten geht hervor, dass jede Surjektion diese Gestalt hat. Projektionen auf Äquivalenzklassen decken damit im Wesentlichen alle Surjektionen ab.

Kardinalitäten

Jede Menge $X$ hat eine gewisse Anzahl $\# X$ von Elementen, auch Kardinalität genannt (zum Beispiel $\# \{\heartsuit,\diamond,\circ\} = 3$, die Formalitäten für unendliche Mengen lassen wir weg). Für jede Bijektion $f : X \to Y$ gilt die Gleichung $\# X = \# Y$, weil die Elemente sich eindeutig entsprechen. Jedes Element $x \in X$ korrespondiert eindeutig zum Element $f(x) \in Y$, und in der anderen Richtung benutzen wir $f^{-1}$. Umgekehrt impliziert $\# X = \# Y $ bereits, dass es eine Bijektion $X \to Y$ gibt. Bijektionen stellen damit die wichtigste Methode dar, um Kardinalitäten auszurechnen. Wenn es lediglich eine Injektion $f : X \to Y$ gibt, gilt $\# X \leq \# Y$, weil es ja eine Bijektion zwischen $X$ und einer Teilmenge $Y' \subseteq Y$ gibt, sodass $\# X = \# Y' \leq \# Y$. Wenn es eine Surjektion $f : X \to Y$ gibt, gilt hingegen $\#X \geq \# Y$, weil es dann tatsächlich eine Injektion $Y \to X$ gibt (sehen wir später).

Beispiele

Einfache Beispiele aus der Analysis

1. Die Abbildung $f : \IR \to \IR$, $f(x) := x^2$ ist weder surjektiv noch injektiv, weil $-1$ kein Urbild hat, aber $1$ gleich zwei Urbilder hat. $\backslash begin\{tikzpicture\}[scale=1.6]\; \backslash draw[->]\; (-1.2,\; 0)\; --\; (1.2,\; 0)\; node[right]\; \{\$x\$\};\; \backslash draw[->]\; (0,\; -0.5)\; --\; (0,\; 1.5)\; node[above]\; \{\$y\$\};\; \backslash draw[domain=-1.2:1.2,\; smooth,\; variable=\backslash x,\; blue]\; plot\; (\{\backslash x\},\; \{\backslash x*\backslash x\});\; \backslash draw[thick,dashed,red]\; (-1.2,1)\; --\; (+1.2,1);\; \backslash end\{tikzpicture\}$ Die Abbildung $f : \IR^+ \to \IR^+$, $f(x):=x^2$ (wo man sich also auf den 1. Quadraten beschränkt) ist hingegen bijektiv mit inverser Abbildung $x \mapsto \sqrt{x}$.
2. Die Abbildung $f : \IR \to \IR$, $f(x) := x + 1$ ist bijektiv, weil $g : \IR \to \IR$, $g(x) := x-1$ eine Abbildung ist, die zu $f$ invers ist.
3. Die Abbildung $\exp : \IR \to \IR$, $\exp(x) := e^x$ ist injektiv, aber nicht surjektiv, weil das Bild lediglich $\IR^+$ ist. Das heißt also, $\exp : \IR \to \IR^+$ ist bijektiv, die inverse Abbildung ist $\log : \IR^+ \to \IR$.
4. Die Abbildung $\lfloor - \rfloor : \IR \to \IZ$, die eine reelle Zahl auf eine ganze Zahl abrundet, ist surjektiv, aber nicht injektiv: Es gilt ja $\lfloor \pi \rfloor = \lfloor 3 \rfloor$.
5. Die Abbildung $f : \IR \to \IR$, $f(x) := x^3+x$ ist bijektiv. $\backslash begin\{tikzpicture\}[xscale=2]\; \backslash draw[->]\; (-1,\; 0)\; --\; (1,\; 0)\; node[right]\; \{\$x\$\};\; \backslash draw[->]\; (0,\; -2)\; --\; (0,\; 2)\; node[above]\; \{\$y\$\};\; \backslash draw[domain=-1:1,\; smooth,\; variable=\backslash x,\; blue]\; plot\; (\{\backslash x\},\; \{\backslash x*\backslash x*\backslash x\; +\; \backslash x\});\; \backslash end\{tikzpicture\}$ Das begründet man am besten analytisch; hier lässt sich auch keine "geschlossene" Formel für die inverse Abbildung angeben. Es ist $f$ differenzierbar. Für die Ableitung gilt $f'(x)=3x^2+1 > 0$. Damit ist $f$ streng monoton wachsend und daher injektiv. Es gilt $\lim_{x \to +\infty} f(x) = +\infty$ und $\lim_{x \to -\infty} f(x) = -\infty$. Nach dem Zwischenwertsatz muss daher $f$ surjektiv sein.
6. Die komplexe Konjugation $c : \IC \to \IC$, $a+ib \mapsto \overline{a+ib} := a-ib$ ist bijektiv, weil sie zu sich selbst invers ist.
7. Die Abbildung $f : \IR \to {]-1,+1[}$, $f(x) := x/(1 + |x|)$ ist bijektiv. (Es gilt also $\# \IR = \# {]-1,+1[}$, sodass es genauso viele reelle Zahlen wie reelle Zahlen im Intervall ${]-1,+1[}$ gibt.) $\backslash begin\{tikzpicture\}[xscale=0.3]\; \backslash draw[->]\; (-10,\; 0)\; --\; (10,\; 0)\; node[right]\; \{\$x\$\};\; \backslash draw[->]\; (0,\; -1)\; --\; (0,\; 1)\; node[above]\; \{\$y\$\};\; \backslash draw[domain=-10:10,\; smooth,\; variable=\backslash x,\; blue,\; samples=200]\; plot\; (\{\backslash x\},\; \{\backslash x/(1\; +\; abs(\backslash x)\});\; \backslash end\{tikzpicture\}$ Um das zu sehen, macht man am besten wieder Äquivalenzumformungen mit $f(x)=y$. Zunächst einmal gilt offenbar $x \geq 0 \iff y \geq 0$, und genauso mit $\leq$. Für $x \geq 0$ gilt $y=x/(1+x)=1-1/(1+x)$, und für $x \leq 0$ gilt $y=x/(1-x)=-1+1/(1-x)$. Offensichtlich kann man jeweils eindeutig nach $x$ auflösen.
8. Sei $P = \{a_0 + a_1 X + \cdots + a_n X^n : n \in \IN, a_0,\dotsc,a_n \in \IR\}$ die Menge der Polynome. Die Ableitung definiert eine Abbildung $D : P \to P$ (zum Beispiel $D(X^n)=n X^{n-1}$). Weil für jedes Polynom $p \in P$ sein Integral ein Polynom mit Ableitung $p$ ist, ist $D$ surjektiv. Weil dabei die Integrationskonstanten beliebig gewählt werden können, sind die Urbilder allerdings nicht eindeutig, sodass $D$ nicht injektiv ist. Genauer gesagt gilt $D(p)=D(q)$ genau dann, wenn $p-q$ konstant ist.
9. Die Abbildung $\sin : \IR \to \IR$ ist weder injektiv (es gilt $\sin(x)=\sin(x+2\pi)$) noch surjektiv (das Bild ist das Intervall $[-1,+1]$). Allerdings ist die Einschränkung $\sin : [-\frac{\pi}{2},+\frac{\pi}{2}] \to [-1,+1]$ bijektiv. Die inverse Abbildung dieser Einschränkung ist der Arkussinus $\arcsin : [-1,+1] \to [-\frac{\pi}{2},+\frac{\pi}{2}]$.
10. Sei $S^1 := \{(x,y) \in \IR^2 : x^2+y^2=1\}$ der Einheitskreis. Jeder Punkt auf dem Einheitskreis hat einen eindeutig bestimmten Winkel in Bezug auf die $x$-Achse. $\backslash begin\{tikzpicture\}[scale=1.4,nodes=\{inner\; sep=-1pt\}]\; \backslash draw[->]\; (-1.3,\; 0)\; --\; (1.3,\; 0)\; node[right=1ex]\; \{\$x\$\};\; \backslash draw[->]\; (0,\; -1.3)\; --\; (0,\; 1.3)\; node[above=1ex]\; \{\$y\$\};\; \backslash draw\; [blue]\; (0,0)\; circle\; (1cm);\; \backslash node\; (O)\; at\; (0,0)\; \{\};\; \backslash node\; [blue]\; (P)\; at\; (0.707,0.707)\; \{\$\backslash bullet\$\};\; \backslash draw\; (O)--(P);\; \backslash node\; (w)\; at\; (0.4,0.15)\; \{\$\backslash alpha\$\};\; \backslash end\{tikzpicture\}$ Das bedeutet gerade, dass die Abbildung $f : {[0,2\pi[} \to S^1$, $f(\alpha) := (\cos(\alpha),\sin(\alpha))$ bijektiv ist.

Beispiele aus der Geometrie

11. Sei $D$ die Menge aller Dreiecke im $\IR^2$. Die Abbildung $m : D \to \IR^2$, die jedem Dreieck seinen Schwerpunkt zuordnet, ist nicht injektiv, aber surjektiv.
12. Sei $\alpha \in \IR$. Dann definiert die Drehung um $\alpha$ eine Abbildung $R_{\alpha} : \IR^2 \to \IR^2$, nämlich $R_{\alpha}(x,y) = (x \cos(\alpha) - y \sin(\alpha), x \sin(\alpha) + y \cos(\alpha))$. Sie ist bijektiv, weil $R_{-\alpha}$ zu $R_{\alpha}$ invers ist.
13. Sei $K \subseteq \IR^2$ ein Kreis mit Mittelpunkt $P$. Dann ist die Inversion am Kreis eine bijektive Abbildung $\IR^2 \setminus \{P\} \to \IR^2 \setminus \{P\}$. Tatsächlich ist sie zu sich selbst invers.

Beispiele aus dem Alltag

14. Sei $W$ die Menge aller Zeichenketten, die aus dem deutschen Alphabet (A,B,...,Z,a,b,...,z,Ä,...,ß) gebildet werden. Wir nennen sie auch Wörter. Zum Beispiel ist Mathematik ein Wort, aber auch ZtXcDw. Die Abbildung $f : W \to W$, $f(w) := \mathrm{\textit a} \frown w$, die an jedem Wort vorne ein a anhängt (mit jedem anderen Buchstaben ginge das Beispiel ebenfalls), ist injektiv, aber nicht surjektiv. Lediglich die Wörter, die mit a beginnen, haben ein Urbild.
15. Sei $A$ die Menge aller Matheplanet-Artikel und $U$ die Menge der Matheplanet-User. Die Abbildung $a : A \to U$, die jedem Matheplanet-Artikel seinen/ihren Autor zuordnet, ist weder surjektiv noch injektiv: Das liegt daran, dass einige User mehrere Artikel geschrieben haben, einige aber auch keine. Die Abbildung $\mathrm{ID} : A \to \IN$, die jedem Matheplanet-Artikel seine ID zuordnet (erkennbar an der URL, zum Beispiel hat dieser Artikel die ID 1969), ist injektiv (sonst wüsste der Server ja nicht, welcher Artikel unter der URL zu öffnen ist!), aber natürlich nicht surjektiv.
16. Sei $M$ die Menge der Mitarbeiter in einem Unternehmen, das jedem Mitarbeiter eine Personalnummer zuordnet. Die Personalnummer $P : M \to \IN$ ist dann eine injektive Abbildung, weil zwei verschiedene Mitarbeiter niemals dieselbe Personalnummer bekommen dürfen. (Natürlich ist $P$ nicht surjektiv, weil $M$ endlich ist.) Ist $W$ die Menge aller Wörter (hier nun auch mit Leer- und Sonderzeichen), so ist die Abbildung $\mathrm{Name} : M \to W$ nicht unbedingt injektiv, weil es zwei unterschiedliche Mitarbeiter mit demselben Namen geben kann.

Beispiele aus der höher-dimensionalen Analysis

17. Die Abbildung $f : \IR^2 \to \IR^2$, $f(x,y) = (y,x-y^2)$ ist bijektiv. Um das zu sehen, müssen wir zeigen, dass für alle $(u,v) \in \IR^2$ die Gleichung $f(x,y)=(u,v)$ genau eine Lösung hat. Wir machen Äquivalenzumformungen: $\begin{align*}f(x,y)=(u,v) & \iff (y,x-y^2)=(u,v) \\ & \iff y=u ~ \wedge ~ x-y^2=v \\ & \iff y=u ~ \wedge ~ x=v+y^2\\ & \iff y=u ~ \wedge ~ x=v+u^2 \\ & \iff (x,y)=(v+u^2,u)\end{align*}$ Das zeigt, dass $f$ bijektiv ist mit inverser Abbildung $f^{-1}(u,v) := (v+u^2,u)$. Beachte, dass dieser Beweis wesentlich schneller als der Nachweis von Injektivität und Surjektivität ist, und wir obendrein die inverse Abbildung bestimmt haben. Beachte, dass die Abbildung $g : \IR^2 \to \IR$, $g(x,y) := x-y^2$ nicht injektiv ist, wie man schön am Konturenplot erkennen kann: Bildquelle: Wolframalpha
18. Die Abbildung $f : \IR^3 \to \IR^3$, $f(x,y,z) := (x+z,z^3,y)$ ist bijektiv. Dazu lösen wir die Gleichung $f(x,y,z)=(u,v,w)$ für beliebiges $(u,v,w) \in \IR^3$ äquivalent und eindeutig nach $(x,y,z)$ auf: $\begin{align*}f(x,y,z)=(u,v,w) & \iff (x+z,z^3,y)=(u,v,w) \\ & \iff x+z = u ~ \wedge ~ z^3=v ~ \wedge ~ y=w \\ & \iff x=u-z ~ \wedge ~ y=w ~ \wedge ~ z=\sqrt[3]{v} \\ & \iff (x,y,z)=(u-\sqrt[3]{v},w,\sqrt[3]{v})\end{align*}$ Das zeigt, dass $f$ bijektiv ist mit inverser Abbildung $f^{-1}(u,v,w) := (u-\sqrt[3]{v},w,\sqrt[3]{v})$. Wieder war es hier nicht nötig, Injektivität und Surjektivität getrennt zu beweisen. Wir haben nur benutzt, dass die Abbildung $\IR \to \IR$, $z \mapsto z^3$ bijektiv ist (was hier sowieso eingehen muss).
19. Die Abbildung $f : \IR \to \IR^3$, $f(t) := (\cos(t),\sin(t),t)$ ist injektiv (aber offenbar nicht surjektiv). Aus $f(t)=f(t')$ folgt schließlich sofort $t=t'$ nach einem Vergleich der dritten Koordinate. Diese Abbildung "wickelt" den Kreis gerade im dreidimensionalen Raum auf. Bildquelle: Wikipedia

Beispiele aus der Mengenlehre

20. Sei $f : X \to Y$ eine Abbildung. Ihr Graph ist die Teilmenge $\Gamma_f := \{(x,f(x)) : x \in X\} \subseteq X \times Y$. Die Abbildung $X \to \Gamma_f$, $x \mapsto (x,f(x))$ ist bijektiv.
21. Für eine Menge $X$ sei $P(X) := \{T : T \subseteq X\}$ ihre Potenzmenge. Dann ist die Abbildung $K : P(X) \to P(X)$, $K(T) := X \setminus T$ bijektiv, ja sie ist sogar zu sich selbst invers: $K(K(T))=X \setminus (X \setminus T) = T$. Wenn speziell $X$ eine endliche Menge mit $n$ Elementen ist und $0 \leq k \leq n$ fest ist, dann bildet $K$ bijektiv die Teilmengen mit $k$ Elementen auf Teilmengen mit $n-k$ Elementen ab. Das ist ein kombinatorischer Beweis für die Gleichung von Binomialkoeffizienten $\binom{n}{k} = \binom{n}{n-k}$.
22. Für je zwei Mengen $X,Y$ gibt es eine bijektive Abbildung $\tau_{X,Y} : X \times Y \to Y \times X$, $\tau_{X,Y}(x,y) := (y,x)$. Die inverse Abbildung ist nämlich $\tau_{Y,X}$.
23. Für je zwei Mengen $X,Y$ ist die Projekion $p_X : X \times Y \to X$ in der Regel surjektiv. Genauer gesagt ist $p_X$ genau dann surjektiv, wenn $X=\emptyset$ oder $Y \neq \emptyset$.
24. Es gilt der folgende Satz von Cantor. Ist $X$ eine beliebige Menge, so gibt es keine surjektive Abbildung $X \to P(X)$, sodass also $\# P(X) > \# X$. Wenn nämlich $f : X \to P(X)$ surjektiv wäre, hätte $T := \{x \in X : x \notin f(x)\}$ ein Urbild, sagen wir $T = f(x)$. Dann gilt $x \in f(x) \iff x \in T \iff x \notin f(x)$, Widerspruch.

Beispiele aus der Zahlentheorie

25. Die Abbildung $S : \IN \to \IN$, $S(n) := n+1$ ist injektiv (weil aus $n+1=m+1$ immer $n=m$ folgt), aber nicht surjektiv, weil das Bild lediglich $\IN^+ = \{1,2,3,\dotsc\}$ ist.
26. Sei $U \subseteq \IZ$ die Menge der ungeraden und $G \subseteq \IZ$ die Menge der geraden Zahlen. Dann ist $f : U \to G$, $f(z) := z+1$ bijektiv. Die inverse Abbildung ist $z \mapsto z-1$.
27. Die Abbildung $f : \IN \times \IN \to \IN$, $f(n,m) := 2^n \cdot (2m+1) - 1$ ist bijektiv. Das folgt aus dem Satz über die eindeutige Primfaktorzerlegung: jede natürliche Zahl $>0$ lässt sich demnach nämlich eindeutig schreiben als $2^n \cdot u$ mit einer natürlichen Zahl $n$ und einer ungeraden natürlichen Zahl $u$, und $u$ lässt sich wiederum eindeutig schreiben als $u=2m+1$ mit einer natürlichen Zahl $m$. Es gilt demnach $\# \IN = \# (\IN \times \IN)$. (Übrigens gibt es für jede unendliche Menge $X$ eine Bijektion $X \to X \times X$.)
28. Die Abbildung $f : \IZ \to \IN$ mit $f(n)=2n$ und $f(-n-1)=2n+1$ für $n \in \IN$ (also $f(0)=0$, $f(-1)=1$, $f(1)=2$, $f(-2)=3$, $f(2)=4$, usw.) ist bijektiv. Es gilt demnach $\# \IN = \# \IZ$.
29. Sei $T \subseteq \IN$ eine unendliche Teilmenge. Dann gibt es eine bijektive Abbildung $f : \IN \to T$, nämlich $T = \{f(0) < f(1) < f(2) < \cdots\}$. Formal definieren wir rekursiv $f(0) := \min(T)$ und $f(n+1) := \min(T \setminus \{f(0),\dotsc,f(n)\})$. Das Minimum existiert, weil $T \setminus \{f(0),\dotsc,f(n)\}$ nichtleer ist, weil nach Annahme $T$ unendlich ist. Die Injektivität von $f$ ist trivial, die Surjektivität folgt leicht per vollständiger Induktion. Also ist $\# T = \# \IN$.
30. Sei $T \subseteq \IN^+ \times \IN^+$ die Menge der Paare $(p,q)$ positiver natürlicher Zahlen, die teilerfremd sind. Dann ist $f : T \to \IQ^+$, $f(p,q) := p/q$ bijektiv.

Kategorielle Charakterisierungen

Wir haben bereits gesehen, dass man die Bijektivität einer Abbildung rein mit der Komposition $\circ$ von Abbildungen und den Identitätsabbildungen charakterisieren kann, nämlich über die Existenz von inversen Abbildungen. Es stellt sich die Frage, ob so etwas auch für injektive und surjektive Abbildungen möglich ist. Diese Frage werden wir gleich positiv beantworten. Es wird sich herausstellen, dass die Begriffe injektiv und surjektiv zueinander dual sind: das bedeutet, dass sich die Charakterisierungen gleichen, wenn man nur die Richtungen der Abbildungen umdreht. Außerdem lassen sich injektive Abbildungen durch ihre Relation zu surjektiven Abbildungen kennzeichnen (und umgekehrt).

Kürzungseigenschaften

Beweis. $1. \implies 2.$ Sei $f$ injektiv. Seien $g,g' : Z \to X$ Abbildungen (hierbei kann $Z$ eine beliebige Menge sein) mit $f \circ g = f \circ g'$. Um $g = g'$ zu zeigen, sei $z \in Z$ beliebig. Dann gilt $f(g(z))=f(g'(z))$ und damit $g(z)=g'(z)$, weil $f$ injektiv ist. $2. \implies 1.$ Dies ist klar, wenn man den Spezialfall $Z = \{0\}$ betrachtet, weil dann $g,g' : \{0\} \to X$ gerade Elementen $x,x' \in X$ entsprechen (via $x = g(0)$, $x' = g'(0)$). $1. \implies 3.$ Wenn $X = \emptyset$, ist nichts zu zeigen. Andernfalls gibt es mindestens ein Element $x_0 \in X$. Wir definieren $h : Y \to X$ über eine Fallunterscheidung. Wenn $y \in \mathrm{Bild}(f)$, sei $h(y) \in X$ das eindeutige Urbild von $y$ bezüglich $f$. Andernfalls sei $h(y) := x_0$. Dann gilt nach Konstruktion $h(f(x))=x$ für alle $x \in X$. $3. \implies 2.$ Für $X=\emptyset$ ist nichts zu zeigen. Andernfalls wählen wir $h : Y \to X$ mit $h \circ f = \mathrm{id}_X$. Aus $f \circ g = f \circ g'$ folgt nun $g = h \circ f \circ g = h \circ f \circ g' = g'$. $3. \implies 4.$ Für $g' := g \circ h$ gilt $g' \circ f = g \circ h \circ f = g$. $4. \implies 3.$ Wende die Voraussetzung auf $g := \mathrm{id}_X$ an. $\checkmark$ Bemerkung: Die eindeutigen Abbildungen $\emptyset \to Y$ mit nichtleeren Mengen $Y$ (siehe hier) sind injektiv, aber nicht linksinvertierbar, denn es gibt gar keine Abbildung $Y \to \emptyset$. Beweis. $1. \implies 2.$ ist leicht und überlassen wir als Aufgabe. $2. \implies 1.$ Wir wählen $Z = \{0,1\}$. Für jede Teilmenge $T \subseteq Y$ sei $\chi_T : Y \to \{0,1\}$, die charakteristische Funktion von $T$, definiert durch $\chi_T(t) = 1$ für $t \in T$ und $\chi_T(y)=0$ für $y \in Y \setminus T$. Es gilt offenbar $\chi_{\mathrm{Bild}(f)} \circ f = \chi_{Y} \circ f$. Nach Annahme gilt daher $\chi_{\mathrm{Bild}(f)}=\chi_{Y}$ und daher $\mathrm{Bild}(f)=Y$. $1. \implies 3.$ Wir können für jedes $y \in Y$ ein Urbild $g(y) \in X$ auswählen. (Dass man damit eine Abbildung $g : Y \to X$ erhält, ist genauer gesagt eine Folge des Auswahlaxioms.) Es gilt also nach Konstruktion $f(g(y))=y$ für alle $y \in Y$, d.h., $f \circ g = \mathrm{id}_Y$. $3. \implies 2.$ und $3. \iff 4.$ folgen genau wie in Lemma 3. $\checkmark$ Zahlreiche weitere Charakterisierungen werden hier im Rahmen von sogenannten Galois-Verbindungen bewiesen. Beweis. Wir nehmen an, dass $f$ injektiv ist (der Fall, dass $f$ surjektiv ist, geht analog). Weil $X$ endlich ist, gibt es auch nur endlich viele Abbildungen $X \to X$. Insbesondere können die Abbildungen $\mathrm{id}_X=f^0,f,f^2,f^3,\dotsc,$ (also die Verkettungen von $f$ mit sich selbst) nicht paarweise verschieden sein. Es gibt also ein Paar natürlicher Zahlen $k < n$ mit $f^k = f^n$. Das können wir nun auch als $f^k \circ \mathrm{id}_X = f^k \circ f^{n-k}$ schreiben. Weil $f^k$ injektiv ist, folgt (mit Lemma 3) $\mathrm{id}_X = f^{n-k}$. Das bedeutet aber gerade, dass $f^{n-k-1}$ zu $f$ invers ist. $\checkmark$

Liftungseigenschaften

Es gibt noch eine weitere Charakterisierung, die mit der folgenden Definition arbeitet. Eine Abbildung $i : A \to B$ habe die linke Liftungseigenschaft bezüglich einer Abbildung $p : X \to Y$, wenn es für alle Abbildungen $f : A \to X$, $g : B \to Y$ mit $g \circ i = p \circ f$ eine Abbildung $h : B \to X$ (einen Lift) gibt mit $h \circ i = f$ und $p \circ h = g$. Wir schreiben dann $i \downarrow p$. Das lässt sich so visualisieren: Beweis. $1. \iff 2.$ Ein Diagramm mit $g \circ i = p \circ f$ entspricht gerade zwei Elementen $x,y \in X$ mit $p(x)=p(y)$ (nämlich $x=f(0)$, $y=f(1)$), und ein Lift existiert nur wenn $x=y$. Dies zeigt $1. \iff 2.$ Die Implikation $3. \implies 2.$ ist trivial. Für $1. \implies 3.$ nehmen wir $g \circ i = p \circ f$ an (wie in der Definition oben) mit $p$ injektiv und $i$ surjektiv, und definieren $h$ durch $h(i(a)) := f(a)$. Das ist wohldefiniert, erstens weil $i$ surjektiv ist und zweitens weil aus $i(a)=i(a')$ ja $p(f(a))=g(i(a))=g(i(a'))=p(f(a'))$, also $f(a)=f(a')$ folgt. Es gilt also nach Konstruktion $h \circ i = f$. Außerdem gilt $p \circ h = g$ weil (hier benutzen wir nun Lemma 4) $i$ surjektiv ist und $p \circ h \circ i = p \circ f = g \circ i$ gilt. $\checkmark$ Beweis. Ein Diagramm mit $g \circ j = p \circ f$ entspricht einem Element $y \in Y$ (nämlich $y = g(0)$), und ein Lift entspricht einem $x \in X$ mit $p(x)=y$. Das zeigt $1. \iff 2.$ Die Implikation $3. \implies 2.$ ist trivial. Um $1. \implies 3.$ zu zeigen, nehmen wir $g \circ i = p \circ f$ an (wie in der Definition oben) mit $p$ surjektiv und $i$ injektiv, und definieren $h$ so: Für $b \in \mathrm{Bild}(i)$, etwa $b=i(a)$ für ein eindeutiges $a \in A$, sei $h(b) := f(a)$. Für $b \notin \mathrm{Bild}(i)$ sei $h(b)$ irgendein $p$-Urbild von $g(b)$. Dann gilt $h \circ i = f$ nach Konstruktion, und $p \circ h = g$ gilt zumindest auf dem Komplement von $\mathrm{Bild}(i)$ nach Konstruktion. Aber auf $\mathrm{Bild}(i)$ gilt dies ebenfalls wegen $p \circ h \circ i = p \circ f = g \circ i$. $\checkmark$