Domain of Composite Relation

Theorem

Let $\mathcal R_2 \circ \mathcal R_1$ be a composite relation.

Then the domain of $\mathcal R_2 \circ \mathcal R_1$ is the domain of $\mathcal R_1$:

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

Proof

Let $\mathcal R_1 \subseteq S_1 \times S_2$ and $\mathcal R_2 \subseteq S_2 \times S_3$.

The domain of $\mathcal R_1$ is $S_1$.

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): x \in S_1, z \in S_3: \exists y \in S_2: \left({x, y}\right) \in \mathcal R_1 \land \left({y, z}\right) \in \mathcal R_2}\right\}$

From this definition:

$\mathcal R_2 \circ \mathcal R_1 \subseteq S_1 \times S_3$.

Thus the domain of $\mathcal R_2 \circ \mathcal R_1$ is $S_1$.

Thus:

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

$\blacksquare$