Union of Left-Total Relations is Left-Total

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $\mathcal R_1 \subseteq S_1 \times T_1$ and $\mathcal R_2 \subseteq S_2 \times T_2$ be left-total relations.


Then $\mathcal R_1 \cup \mathcal R_2$ is left-total.


Proof

Let both $\mathcal R_1$ and $\mathcal R_2$ be left-total.

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

Let $s \in S_1 \cup S_2$.

By the definition of union:

$s \in S_1 \lor s \in S_2$

Thus $s \in S_i$ for $i \in \set {1, 2}$.

By definition of left-total relation, there is a $t \in T_i$ such that $\tuple {s, t} \in \mathcal R_i$.

We have that $\mathcal R$ is a superset of $\mathcal R_i$.

Hence from Union is Smallest Superset:

$\tuple {s, t} \in \mathcal R_i \subseteq \mathcal R \implies \tuple {s, t} \in \mathcal R$

$\blacksquare$


Also see