Domain of Composite Relation

From ProofWiki
Jump to navigation Jump to search

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$:

$\Dom {\mathcal R_2 \circ \mathcal R_1} = \Dom {\mathcal R_1}$


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 = \set {\tuple {x, z}: x \in S_1, z \in S_3: \exists y \in S_2: \tuple {x, y} \in \mathcal R_1 \land \tuple {y, z} \in \mathcal R_2}$


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:

$\Dom {\mathcal R_2 \circ \mathcal R_1} = S_1 = \Dom {\mathcal R_1}$

$\blacksquare$