Einfache Operationen mit Funktionen
Die einfachste Operation, die aus einer Funktion eine weitere Funktion macht, ist die Einschränkung der Funktion auf einen Teil des Definitionsbereichs:
Definition (Einschränkung einer Funktion)
Sei f : A → B und C ⊆ A. Dann setzen wir
f|C = { (a, b) ∈ f | a ∈ C }.
f|C heißt die Einschränkung von f auf C.
Sind f, g Funktionen mit f ⊆ g, so heißt g eine Fortsetzung von f.
Ist f : A → B und C ⊆ A, so gilt f|C : C → B, und f ist eine Fortsetzung von f|C. Eine Funktion g ist Fortsetzung einer Funktion f genau dann, wenn g|dom(f) = f.
Eine weitere Operation ist uns im Beweis oben schon begegnet, nämlich die „Umkehrung“ einer Funktion. Hier brauchen wir die Injektivität (Linkseindeutigkeit) der Ausgangsfunktion, damit die Rechtseindeutigkeit der Umkehrung gewährleistet ist.
Definition (Umkehrfunktion)
Sei f eine injektive Funktion. Dann ist die Umkehrfunktion von f, in Zeichen f −1, definiert durch
f −1 = { (b, a) | (a, b) ∈ f }.
Offenbar ist f −1 wieder eine injektive Funktion, und es gilt dom(f −1) = rng(f), rng(f −1) = dom(f). Weiter gilt (f −1)−1 = f.
Definition (Verkettung oder Verknüpfung von Funktionen)
Seien f, g Funktionen. Dann ist die Verkettung g ∘ f der Funktionen f und g [gelesen: g nach f] definiert durch:
g ∘ f = { (a, c) | a ∈ dom(f) und (f (a), c) ∈ g }.
Übung
Seien f, g Funktionen. Dann gilt:
(i) | g ∘ f ist eine Funktion, dom(g ∘ f) ⊆ dom(f), rng(g ∘ f) ⊆ rng(g). |
(ii) | Ist f : A → B und g : B → C, so ist g ∘ f : A → C. |
Seien f : A → B, g : B → C, und sei h = g ∘ f : A → C.
Nach Definition haben wir h(a) = g(f (a)) für alle a ∈ A. Die Verkettung h von f und g ist also die Hintereinanderausführung von f und g: Wir starten bei a, bilden b = f (a) und setzen dann h(a) = g(b) = g(f (a)).
Weiter gilt in dieser Situation stets g ∘ f = g|rng(f) ∘ f.
Übung
Seien f : A → B und g : B → C Funktionen und sei h = g ∘ f.
(i) | Sind f, g injektiv, so ist auch h injektiv. |
(ii) | Ist g|rng(f) surjektiv nach C, so ist h surjektiv nach C. |
(iii) | Sind f : A → B und g : B → C bijektiv, so ist h : A → C bijektiv. |
Die Verkettung ist eine assoziative Operation, was man sich anhand eines Diagramms wie oben anschaulich machen kann:
Übung (Assoziativgesetz für die Verknüpfung von Funktionen)
Seien f, g, h Funktionen. Dann gilt (h ∘ g) ∘ f = h ∘ (g ∘ f).
Wir können also Klammern weglassen und h ∘ g ∘ f schreiben.
Für die einfachsten Funktionen brauchen wir noch eine Bezeichnung:
Definition (Identität)
Sei A eine Menge. Dann ist die Identität auf A, in Zeichen idA, definiert durch:
idA = { (a, a) | a ∈ A }.
Es gilt idA : A → A. Offenbar ist idA eine Bijektion von A nach A.
Nach Definition ist id∅ = ∅.
Übung
(a) | Sei f : A → B bijektiv. Dann gilt f −1 ∘ f = idA und f ∘ f −1 = idB. |
(b) | Seien f, g injektiv. Dann gilt (g ∘ f)−1 = f −1 ∘ g−1. |
Der folgende Satz bringt ein nützliches Kriterium für die Injektivität oder Surjektivität einer Funktion.
Satz (Verkettung zur Identität)
Sei f : A → B eine Funktion.
(a) | Ist A ≠ ∅, so sind die folgenden Aussagen äquivalent:
|
(b) | Die folgenden Aussagen sind äquivalent:
|
Beweis
zu (a):
(i) ↷ (ii):
Seien B′ = rng(f) und a ∈ A beliebig. Wir definieren g : B → A durch
g|B′ = f −1, g(b) = a für b ∉ B′.
Dann ist g ∘ f = idA.
(ii) ↷ (i):
Sei f (a1) = b = f (a2) für a1, a2 ∈ A. Dann ist
g(b) = g(f (a1)) = idA(a1) = a1,
g(b) = g(f (a2)) = idA(a2) = a2,
also a1 = a2. Also ist f injektiv.
zu (b):
(i) ↷ (ii):
Wir definieren g : B → A durch
g(b) = „ein a ∈ A mit f (a) = b“ für alle b ∈ B.
[Ein a ∈ A mit f (a) = b existiert wegen rng(f) = B nach Voraussetzung.]
Dann gilt g : B → A und nach Definition von g ist f (g(b)) = b für alle b ∈ B. Also f ∘ g = idB.
(ii) ↷ (i):
Sei b ∈ B. Wegen f ∘ g = idB ist f (g(b)) = b. Also ist b ∈ rng(f), denn f (a) = b für a = g(b). Also ist f : A → B surjektiv.
Dem Leser ist hier vielleicht die folgende Zeile aufgefallen:
g(b) = „ein a ∈ A mit f (a) = b“.
Manche Leser werden dieses „ein“ vielleicht seltsam finden, andere werden fragen, was daran besonderes sein soll. Die einzige Besonderheit ist, dass hier ein sehr abstrakter Prozess am Werk ist (und manche Leser werden sich mittlerweile schon an unbegrenzte Abstraktion gewöhnt haben): Wir wissen, dass für jedes b in B mindestens ein a in A mit f (a) = b existiert. Für die Definition von g müssen wir aber derartige Zeugen a für alle b ∈ B herauspicken. Überspitzt gefragt: Wer garantiert uns, dass es einen auf ganz B operierenden „Zufallsgenerator“ gibt, der uns diese Auswahlarbeit „liefere, gegeben b, irgendein für dieses b geeignetes a“ abnimmt? Die Antwort aus heutiger Sicht ist: Innerhalb eines genügend reichhaltigen naiven Mengenbegriffs liegt kein Problem vor, es gibt immer solche a’s, also nehmen wir einfach welche und definieren g. Innerhalb der axiomatischen Behandlung der Mengenlehre zeigt sich, dass man das Funktionieren solcher platonisch zweifellos gerechtfertigter Auswahlprozesse durch ein eigenes und sehr starkes Axiom absichern muss.
Im Folgenden deuten wir ähnliche Situationen durch verwandte Schreibweisen wie „ein … “ an, und betrachten diese sehr abstrakte Form der Mengenbildung als interessant aber unproblematisch. Begegnet ist sie uns an versteckter Stelle schon zuvor: Will man beweisen, dass jede Äquivalenzrelation ein vollständiges Repräsentantensystem besitzt, ist ein ähnliches „ein …“ nötig.