Inverse of Subset of Relation is Subset of Inverse
Jump to navigation
Jump to search
Theorem
Let $S$ and $T$ be sets
Let $\RR_1 = S \times T$ be a relation on $S \times T$.
Let $\RR_2 \subseteq \RR_1$.
Then:
- $\RR_2^{-1} \subseteq \RR_1^{-1}$
where $\RR_1^{-1}$ denotes the inverse of $\RR_1$.
Proof
\(\ds \tuple {t, s}\) | \(\in\) | \(\ds \RR_2^{-1}\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {s, t}\) | \(\in\) | \(\ds \RR_2\) | Definition of Inverse Relation | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {s, t}\) | \(\in\) | \(\ds \RR_1\) | Definition of Subset | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {t, s}\) | \(\in\) | \(\ds \RR_1^{-1}\) | Definition of Inverse Relation |
The result follows by definition of subset.
$\blacksquare$