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

From ProofWiki
Jump to navigation Jump to search

Theorem

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

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

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

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


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


Proof

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

Let $\tuple {x, y_1}, \tuple {x, y_2} \in \RR$.

By the definition of union, $\tuple {x, y_1}$ and $\tuple {x, y_2}$ are each in $\RR_1$ or $\RR_2$.


Suppose that both are in $\RR_1$.

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


Suppose that $\tuple {x, y_1} \in \RR_1$ and $\tuple {x, y_2} \in \RR_2$.

Then $x$ is in the domain of $\RR_1$ and that of $\RR_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, $\RR$ is many-to-one.

$\blacksquare$