Union of Inverse is Inverse of Union

From ProofWiki
Jump to: navigation, search


Let for $i \in \left\{1,2\right\}$ $\mathcal R_i \subseteq S_i \times T_i$ be a relation on $S_i \times T_i$.

Let $\mathcal R_i^{-1} \subseteq T_i \times S_i$ be the inverse of $\mathcal R_i$.

Then $\mathcal R_1^{-1} \cup \mathcal R_2^{-1} = \left(\mathcal R_1 \cup \mathcal R_2\right)^{-1}$


Let $\left(t,s\right) \in \mathcal R_1^{-1} \cup \mathcal R_2^{-1}$.

By the definition of union: $\left(t,s\right) \in \mathcal R_1^{-1} \vee \left(t,s\right) \in \mathcal R_2^{-1}$.

Assume $\left(t,s\right) \in \mathcal R_i^{-1}$. By the definition of inverse: $\left(s,t\right) \in \mathcal R_i$.

By Disjunction introduction: $\left(s,t\right) \in \mathcal R_1 \vee \left(s,t\right) \in \mathcal R_2 \iff \left(s,t\right) \in \mathcal R_1 \cup \mathcal R_2$.

And by the definition of inverse: $\left(t,s\right) \in \left(\mathcal R_1 \cup \mathcal R_2\right)^{-1}$.