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

From ProofWiki
Jump to: navigation, search

Theorem

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

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

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

Suppose that the images of $\mathcal R_1$ and $\mathcal R_2$ are disjoint.


Then $\mathcal R_1 \cup \mathcal R_2$ is a one-to-many relation on $(S_1 \cup S_2) \times (T_1 \cup T_2)$.


Proof

Let $\mathcal Q = \mathcal R_1 \cup \mathcal R_2$.

Then $Q \subseteq (S_1 \times T_1) \cup (S_2 \times T_2) \subseteq (S_1 \cup S_2) \times (T_1 \cup T_2)$.

Thus $Q$ is a relation on $(S_1 \cup S_2) \times (T_1 \cup T_2)$.

Let $T'_1$ and $T'_2$ be the images of $\mathcal R_1$ and $\mathcal R_2$, respectively.

Let $(x_1, y), (x_2, y) \in Q$.

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

If $y \in T'_1$ then $y \notin T'_2$, so neither $(x_1, y)$ nor $(x_2, y)$ is in $\mathcal R_2$, so these pairs are both in $\mathcal R_1$.

As $\mathcal R_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$: $Q$ is a one-to-many relation.

$\blacksquare$