Union of Inverse of Relations is Inverse of their Union

Theorem

For $i \in \set {1, 2}$, let $\RR_i \subseteq S_i \times T_i$ be relations on $S_i \times T_i$.

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

Then:

${\RR_1}^{-1} \cup {\RR_2}^{-1} = \paren {\RR_1 \cup \RR_2}^{-1}$

Proof

Let $\tuple {t, s} \in {\RR_1}^{-1} \cup {\RR_2}^{-1}$.

By definition of union:

$\tuple {t, s} \in {\RR_1}^{-1} \lor \tuple {t, s} \in {\RR_2}^{-1}$.

For $i \in \set {1, 2}$, let $\tuple {t, s} \in {\RR_i}^{-1}$.

By definition of inverse:

$\tuple {s, t} \in \RR_i$

That is:

$\tuple {s, t} \in \RR_1 \lor \tuple {s, t} \in \RR_2$

By definition of union:

$\tuple {s, t} \in \RR_1 \lor \tuple {s, t} \in \RR_2 \iff \tuple {s, t} \in \RR_1 \cup \RR_2$

By the definition of inverse:

$\tuple {t, s} \in \paren {\RR_1 \cup \RR_2}^{-1}$

$\blacksquare$