Kompositionen von Relationen und Funktionen.

Für eine Funktion

f

zwischen

A

und

B

und eine weitere Funktion

g

zwischen

B

und

C

bezeichnet

g \circ f

die durch die Relation

gegebene Komposition dieser beiden Funktionen. Mit anderen Worten ist

c = (g \circ f) (a)

falls

b = f (a)

und

c = g (b) = g (f (a))

. Von den folgenden zwei Resultaten kann man sich leicht durch eine graphische Darstellung überzeugen. Wir führen aber zur Demonstration trotzdem die formalen Beweise an.

Lemma 1.4.2. Die Komposition $g \circ f$ ist eine Funktion zwischen $A$ und $C$ , deren Definitionsbereich durch

D (g \circ f) = {a | a \in D (f) \land f (a) \in D (g)}

(1.3)

gegeben ist und für welche

(g \circ f) (a) = g (f (a))

(1.4)

für alle $a \in D (g \circ f)$ gilt.

Beweis. Es seien $(a, c_{1}) \in R_{g \circ f}$ und $(a, c_{2}) \in R_{g \circ f}$ . Dann gibt es nach (1.2) Elemente $b_{1}, b_{2} \in B$ mit

(a, b_{1}) \in R_{f}, (b_{1}, c_{1}) \in R_{g}, (a, b_{2}) \in R_{f}, (b_{2}, c_{2}) \in R_{g} .

Da $R_{f}$ eindeutig ist, so gilt $b_{1} = b_{2} = : b$ und damit

(b, c_{1}) \in R_{g}, (b, c_{2}) \in R_{g} .

Aus der Eindeutigkeit von $R_{g}$ folgt nun $c_{1} = c_{2}$ und damit ist $g \circ f$ ist eine Funktion.

Es gelte nun $a \in D (f)$ und $f (a) \in D (g)$ . Man setzt $b = f (a)$ und $c = g (b)$ , d.h. $(a, b) \in R_{f}$ und $(b, c) \in R_{g}$ . Nach (1.2) folgt $(a, c) \in R_{g \circ f}$ und damit

{a | a \in D (f) \land f (a) \in D (g)} \subset V b (R_{g \circ f}) = D (g \circ f)

(1.5)

sowie

(g \circ f) (a) = c = g (b) = g (f (a)) .

(1.6)

Umgekehrt, falls $a \in D (g \circ f) = V b (R_{g \circ f})$ und $c = (g \circ f) (a)$ , so gilt $(a, c) \in R_{g \circ f}$ . Dann existiert nach (1.2) ein $b \in B$ mit $(a, b) \in R_{f} \land (b, c) \in R_{g}$ . Daraus sehen wir, dass $a \in D (f)$ und $b = f (a)$ sowie $b \in D (g)$ , d.h.

D (g \circ f) \subset {a | a \in D (f) \land f (a) \in D (g)} .

(1.7)

Die Beziehungen (1.5)-(1.7) vervollständigen den Beweis. □

Es sei

h

nun eine dritte Funktion zwischen den Mengen

C

und

D

. Dann kann man die Komposition der drei Funktionen

f

g

und

h

zunächst als

h \circ (g \circ f)

oder

(h \circ g) \circ f

definieren. Es zeigt sich, dass die Komposition von Funktionen eine assoziative Operation ist:

Beweis. Die Behauptung folgt aus $\begin{array}{rcl} R_{h \circ (g \circ f)} & = & {(a, d) | \exists_{c \in C} (a, c) \in R_{g \circ f} \land (c, d) \in R_{h}} \\ = & {(a, d) | \exists_{c \in C} \exists_{b \in B} (a, b) \in R_{f} \land (b, c) \in R_{g} \land (c, d) \in R_{h}} \\ = & {(a, d) | \exists_{(b, c) \in B \times C} (a, b) \in R_{f} \land (b, c) \in R_{g} \land (c, d) \in R_{h}} \end{array}$

und $\begin{array}{rcl} R_{(h \circ g) \circ f} & = & {(a, d) | \exists_{b \in B} (a, b) \in R_{f} \land (b, d) \in R_{h \circ g}} \\ = & {(a, d) | \exists_{b \in B} (a, b) \in R_{f} \land (\exists_{c \in C} (b, c) \in R_{g} \land (c, d) \in R_{h})} \\ = & {(a, d) | \exists_{(b, c) \in B \times C} (a, b) \in R_{f} \land (b, c) \in R_{g} \land (c, d) \in R_{h}} . \end{array}$

□

1.4.2 Kompositionen von Relationen und Funktionen.