Composition of Mappings is Composition of Relations

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S_1, S_2, S_3$ be sets.

Let $f_1: S_1 \to S_2$ and $f_2: S_2 \to S_3$ be mappings such that the domain of $f_2$ is the same set as the codomain of $f_1$.

Let $f_2 \circ f_1$ be the composite of $f_1$ and $f_2$.


Let $f_1$ and $f_2$ be considered as relations on $S_1 \times S_2$ and $S_2 \times S_3$ respectively.

Then $f_2 \circ f_1$ defined as the composition of relations coincides with the definition of $f_2 \circ f_1$ as the composition of mappings.


Proof

By definition of composition of mappings:

$f_2 \circ f_1 = \left\{{\left({x, z}\right) \in S_1 \times S_3: \exists y \in S_2: \left({x, y}\right) \in f_1 \land \left({y, z}\right) \in f_2}\right\}$


Let $\mathcal R_1 \subseteq S_1 \times T_1$ and $\mathcal R_2 \subseteq S_2 \times T_2$ be relations.

The composite of $\mathcal R_1$ and $\mathcal R_2$ is defined as:

$\mathcal R_2 \circ \mathcal R_1 := \left\{{\left({x, z}\right) \in S_1 \times T_2: \exists y \in S_2 \cap T_1: \left({x, y}\right) \in \mathcal R_1 \land \left({y, z}\right) \in \mathcal R_2}\right\}$


When $T_1 = S_2$ and $T_2 = S_3$, this becomes:

$\mathcal R_2 \circ \mathcal R_1 := \left\{{\left({x, z}\right) \in S_1 \times T_3: \exists y \in S_2: \left({x, y}\right) \in \mathcal R_1 \land \left({y, z}\right) \in \mathcal R_2}\right\}$

The definitions can be seen to be identical.

$\blacksquare$


Sources