Union of One-to-Many Relations with Disjoint Images is One-to-Many

Theorem

Let $S_1, S_2, T_1, T_2$ be sets or classes.

Let $\RR_1$ be a one-to-many relation on $S_1 \times T_1$.

Let $\RR_2$ be a one-to-many relation on $S_2 \times T_2$.

Suppose that the images of $\RR_1$ and $\RR_2$ are disjoint.

Then $\RR_1 \cup \RR_2$ is a one-to-many relation on $\paren {S_1 \cup S_2} \times \paren {T_1 \cup T_2}$.

Proof

Let $\QQ = \RR_1 \cup \RR_2$.

Then $\QQ \subseteq \paren {S_1 \times T_1} \cup \paren {S_2 \times T_2} \subseteq \paren {S_1 \cup S_2} \times \paren {T_1 \cup T_2}$.

Thus $\QQ$ is a relation on $\paren {S_1 \cup S_2} \times \paren {T_1 \cup T_2}$.

Let $T'_1$ and $T'_2$ be the images of $\RR_1$ and $\RR_2$, respectively.

Let $\tuple {x_1, y}, \tuple {x_2, y} \in \QQ$.

Then $y \in T'_1$ or $y \in T'_2$.

If $y \in T'_1$ then $y \notin T'_2$, so neither $\tuple {x_1, y}$ nor $\tuple {x_2, y}$ is in $\RR_2$, so these pairs are both in $\RR_1$.

As $\RR_1$ is one-to-many, $x_1 = x_2$.

A similar argument leads to the same result for $y \in T'_2$.

As this holds for all such $x_1, x_2, y$: $\QQ$ is a one-to-many relation.

$\blacksquare$