Union of Left-Total Relations is Left-Total

From ProofWiki
Jump to: navigation, 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 $\mathcal R = \mathcal R_1 \cup \mathcal R_2$ and assume both $R_1$ and $R_2$ left-total.

Let $s \in S_1 \cup S_2$.

By the definition of union:

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

Assume $s \in S_i$.

Then by totality of $\mathcal R_i$ there is a $t \in T_i$ such that $\left({s, t}\right) \in \mathcal R_i$.

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

Hence from Union is Smallest Superset:

$\left({s, t}\right) \in \mathcal R_i \subseteq \mathcal R \implies \left({s, t}\right) \in \mathcal R$

$\blacksquare$


Also see