Union of Right-Total Relations is Right-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 right-total relations.


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


Proof

Define the predicates $LT$ and $RT$ by:

  • $LT\left(X\right) \iff X\text{ is left-total}$
  • $RT\left(X\right) \iff X\text{ is right-total}$.


\(\displaystyle RT\left(\mathcal R_1\right) \land RT\left(\mathcal R_2\right)\) \(\implies\) \(\displaystyle LT\left(\mathcal R_1^{-1}\right) \land LT\left(\mathcal R_2^{-1}\right)\) Inverse of Right-Total is Left-Total
\(\displaystyle \) \(\implies\) \(\displaystyle LT\left(\mathcal R_1^{-1} \cup \mathcal R_2^{-1}\right)\) Union of Left-Total Relations is Left-Total
\(\displaystyle \) \(\implies\) \(\displaystyle LT\left(\left(\mathcal R_1 \cup \mathcal R_2\right)^{-1}\right)\) Union of Inverse is Inverse of Union
\(\displaystyle \) \(\implies\) \(\displaystyle RT\left(\mathcal R_1 \cup \mathcal R_2\right)\) Inverse of Right-Total is Left-Total

$\blacksquare$


Also see