7.2 Injektivität, Surjektivität und Bijektivität
Drei wichtige Eigenschaften
Die Funktionsdefinition regelt die Zuordnung von Eingaben zu Ausgaben. Die folgenden Eigenschaften beschreiben zusätzlich, wie der Wertebereich erreicht wird.
Definition 7.4 (Injektivität, Surjektivität und Bijektivität). Eine Funktion \(f:X\to Y\) heißt
- injektiv, wenn aus \(f(x_1)=f(x_2)\) stets \(x_1=x_2\) folgt;
- surjektiv, wenn \(f(X)=Y\), also zu jedem \(y\in Y\) mindestens ein \(x\in X\) mit \(f(x)=y\) existiert;
- bijektiv, wenn sie injektiv und surjektiv ist.
Eine solche Funktion heißt auch Injektion, Surjektion bzw. Bijektion.
Gleichwertig zur Injektivität ist \(x_1\neq x_2\Rightarrow f(x_1)\neq f(x_2)\). Im Relationsvokabular ist der Funktionsgraph zusätzlich linkseindeutig bzw. rechtsvollständig.
Wie viele Urbilder hat ein Wert?
Die drei Eigenschaften lassen sich auch daran erkennen, wie viele Argumente zu jedem Wert im Wertebereich gehören.
Bemerkung. Für eine Funktion \(f:X\to Y\) gilt:
- \(f\) ist surjektiv \(\Longleftrightarrow\) zu jedem \(y\in Y\) existiert mindestens ein \(x\in X\) mit \(f(x)=y\).
- \(f\) ist injektiv \(\Longleftrightarrow\) zu jedem \(y\in Y\) existiert maximal ein \(x\in X\) mit \(f(x)=y\).
- \(f\) ist bijektiv \(\Longleftrightarrow\) zu jedem \(y\in Y\) existiert genau ein \(x\in X\) mit \(f(x)=y\).
Wie zeigt oder widerlegt man die Eigenschaften?
Für einen Nachweis müssen alle Argumente bzw. Elemente des Wertebereichs erfasst werden; zum Widerlegen genügt ein gezielt gewählter Gegenfall.
Injektivität: Beginnen Sie mit \(f(x_1)=f(x_2)\) und folgern Sie \(x_1=x_2\). Zwei verschiedene Argumente mit gleicher Ausgabe widerlegen die Eigenschaft.
Surjektivität: Wählen Sie ein beliebiges \(y\in Y\) und finden Sie ein \(x\in X\) mit \(f(x)=y\). Prüfen Sie dabei, ob das gefundene \(x\) im Definitionsbereich liegt. Ein unerreichter Wert in \(Y\) widerlegt Surjektivität.
Eine lineare Funktion \(f:\mathbb R\to\mathbb R\), \(f(x)=ax+b\) ist genau dann injektiv, wenn \(a\neq0\).
Beispiel: Eine lineare Funktion
Untersuchen Sie \(f:\mathbb R\to\mathbb R\), \(f(x)=3x-2\) auf Injektivität, Surjektivität und Bijektivität.
Gleiche Vorschrift, andere Eigenschaften
Eine Funktion ist durch ihre Vorschrift, ihren Definitionsbereich und ihren Wertebereich eindeutig bestimmt. Injektivität und Surjektivität hängen von allen drei Komponenten ab.
Beispiel: Vier Varianten einer verschobenen Betragsfunktion
| Funktion mit Vorschrift \(x\mapsto\lvert x-1\rvert+2\) | injektiv | surjektiv |
|---|---|---|
| \(\mathbb R\to\mathbb R\) | nein | nein |
| \(\mathbb R\to[2,\infty)\) | nein | ja |
| \([1,\infty)\to\mathbb R\) | ja | nein |
| \([1,\infty)\to[2,\infty)\) | ja | ja |
Auf \(\mathbb R\) ist die Funktion nicht injektiv, denn \(f(0)=f(2)=3\). Für \(x\geq1\) gilt dagegen \(f(x)=x+1\); aus \(f(x_1)=f(x_2)\) folgt dann \(x_1=x_2\).
Die Bildmenge ist in allen vier Fällen \([2,\infty)\): Es gilt stets \(f(x)\geq2\), und jedes \(y\geq2\) wird bei \(x=y-1\geq1\) angenommen. Daher ist die Funktion genau dann surjektiv, wenn \([2,\infty)\) als Wertebereich gewählt wird.
Ein Wechsel des Wertebereichs zur Bildmenge \(f(X)\) macht jede Funktion surjektiv, ändert aber nichts an ihrer Injektivität. Eine geeignete Einschränkung des Definitionsbereichs kann eine nicht injektive Funktion injektiv machen. Die Einschränkung des Definitionsbereichs auf \(A\subseteq X\) wird mit \(f|_A\) bezeichnet.
Was verrät die Anzahl der Elemente?
Bei endlichen Mengen gibt es einfache Zählargumente, die Injektivität und Surjektivität mit der Größe der Mengen in Beziehung setzen.
Satz 7.1 (Funktionen zwischen endlichen Mengen). Seien \(X,Y\) endlich und \(f:X\to Y\).
- Ist \(f\) injektiv, so gilt \(|X|\leq|Y|\).
- Ist \(f\) surjektiv, so gilt \(|X|\geq|Y|\).
- Ist \(|X|=|Y|\), so ist \(f\) genau dann injektiv, wenn sie surjektiv ist.
Der Grund ist einfaches Abzählen der tatsächlich erreichten Werte.
Beweis. Für eine Injektion gibt es genau \(|X|\) verschiedene Bildwerte, also \(|X|=|f(X)|\leq|Y|\). Allgemein gilt \(|f(X)|\leq|X|\); bei einer Surjektion folgt \(|Y|\leq|X|\). Sind \(|X|=|Y|\), so erreicht eine Injektion den gesamten Wertebereich. Wäre eine Surjektion nicht injektiv, hätten zwei verschiedene Argumente denselben Funktionswert. Dann wäre \(|f(X)|<|X|=|Y|\), im Widerspruch zur Surjektivität. \(\square\)
Eine Funktion von allen endlichen Binärwörtern in eine feste Menge von \(2^{32}\) Hashwerten kann daher nicht injektiv sein. Schon unter den \(2^{33}\) Wörtern der Länge \(33\) müssen mindestens zwei verschiedene Wörter denselben Hashwert erhalten. Dies nennt man bei Hashverfahren eine Kollision.
Zusammenfassung
- Injektiv bedeutet: Verschiedene Eingaben haben verschiedene Ausgaben.
- Surjektiv bedeutet: Die Bildmenge stimmt mit dem Wertebereich überein.
- Bijektiv bedeutet: Jeder Wert im Wertebereich besitzt genau ein passendes Argument.
- Definitionsbereich und Wertebereich müssen bei jeder Prüfung berücksichtigt werden.
- Für endliche Mengen gleicher Größe sind Injektivität und Surjektivität gleichwertig.