Domain of Composite Relation

Theorem

Let $\RR_2 \circ \RR_1$ be a composite relation.

Then the domain of $\RR_2 \circ \RR_1$ is the domain of $\RR_1$:

There is believed to be a mistake here, possibly a typo. In particular: All that can be said is that the domain of the composition is a subset of the domain of the first relation You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by reviewing it, and either correcting it or adding some explanatory material as to why you believe it is actually correct after all. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Mistake}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

$\Dom {\RR_2 \circ \RR_1} = \Dom {\RR_1}$

Proof

Let $\RR_1 \subseteq S_1 \times S_2$ and $\RR_2 \subseteq S_2 \times S_3$.

The domain of $\RR_1$ is $S_1$.

The composite of $\RR_1$ and $\RR_2$ is defined as:

$\RR_2 \circ \RR_1 = \set {\tuple {x, z}: x \in S_1, z \in S_3: \exists y \in S_2: \tuple {x, y} \in \RR_1 \land \tuple {y, z} \in \RR_2}$

From this definition:

$\RR_2 \circ \RR_1 \subseteq S_1 \times S_3$.

Thus the domain of $\RR_2 \circ \RR_1$ is $S_1$.

Thus:

$\Dom {\RR_2 \circ \RR_1} = S_1 = \Dom {\RR_1}$

$\blacksquare$