Definition:Composition of Relations

Definition

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

Then the composite of $\mathcal R_1$ and $\mathcal R_2$ is defined and denoted 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\}$

Some authors write $\mathcal R_2 \circ \mathcal R_1$ as $\mathcal R_2 \mathcal R_1$.

It is clear that the composite relation $\mathcal R_2 \circ \mathcal R_1$ can also be defined as:

$\mathcal R_2 \circ \mathcal R_1 \left( {S_1}\right) = \mathcal R_2 \left( {\mathcal R_1 \left({S_1}\right)}\right)$

Note that:

• $\mathcal R_2 \circ \mathcal R_1 \subseteq S_1 \times T_2$;
• The domain of $R_2 \circ \mathcal R_1$ equals the domain of $\mathcal R_1$, that is, $S_1$;
• The codomain of $R_2 \circ \mathcal R_1$ equals the codomain of $\mathcal R_2$, that is, $T_2$.

Also see

• Image and Preimage of Composition of Relations‎

• Composition of Mappings is Composition of Relations

Illustration

The following is a Venn diagram illustrating the relations between the various entities.

In the above:

$\operatorname{Im} \left({\mathcal R}\right)$ denotes the image of a relation $\mathcal R$

$\operatorname{Im}^{-1} \left({\mathcal R}\right)$ denotes the preimage of a relation $\mathcal R$.

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 10$: Inverses and Composites
• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $5.8$
• George McCarty: Topology: An Introduction with Application to Topological Groups (1967): $\text{I}$: Problem $\text{AA}$