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

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 many-to-one relation on $S_1 \times T_1$.

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

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


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


Proof

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

Let $\left({x, y_1}\right), \left({x, y_2}\right) \in \mathcal R$.

By the definition of union, $\left({x, y_1}\right)$ and $\left({x, y_2}\right)$ are each in $\mathcal R_1$ or $\mathcal R_2$.


Suppose that both are in $\mathcal R_1$.

Then since $\mathcal R_1$ is a many-to-one relation, $y_1 = y_2$.


Suppose that $\left({x, y_1}\right) \in \mathcal R_1$ and $\left({x, y_2}\right) \in \mathcal R_2$.

Then $x$ is in the domain of $\mathcal R_1$ and that of $\mathcal R_2$, contradicting the premise, so this cannot occur.


The other two cases are precisely similar.

Thus in all cases $y_1 = y_2$.

As this holds for all such pairs, $\mathcal R$ is many-to-one.

$\blacksquare$