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


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


Proof

Define the predicates $L$ and $R$ by:

$\map L X \iff \text {$X$ is left-total}$
$\map R X \iff \text {$X$ is right-total}$


\(\displaystyle \map R {\mathcal R_1} \land \map R {\mathcal R_2}\) \(\leadsto\) \(\displaystyle \map L {\mathcal R_1^{-1} } \land \map L {\mathcal R_2^{-1} }\) Inverse of Right-Total Relation is Left-Total
\(\displaystyle \) \(\leadsto\) \(\displaystyle \map L {\mathcal R_1^{-1} \cup \mathcal R_2^{-1} }\) Union of Left-Total Relations is Left-Total
\(\displaystyle \) \(\leadsto\) \(\displaystyle \map L {\paren {\mathcal R_1 \cup \mathcal R_2}^{-1} }\) Union of Inverse is Inverse of Union
\(\displaystyle \) \(\leadsto\) \(\displaystyle \map R {\mathcal R_1 \cup \mathcal R_2}\) Inverse of Right-Total Relation is Left-Total

$\blacksquare$


Also see