Image of Relation is Domain of Inverse Relation

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathcal R \subseteq S \times T$ be a relation.

Let $\mathcal R^{-1} \subseteq T \times S$ be the inverse of $\mathcal R$.


Then:

$\operatorname{Im} \left ({\mathcal R}\right) = \operatorname{Dom} \left ({\mathcal R^{-1}}\right)$

That is, the image of a relation is the domain of its inverse.


Proof

By definition:

$\operatorname{Im} \left({\mathcal R}\right) := \left\{{t \in T: \exists s \in S: \left({s, t}\right) \in \mathcal R}\right\}$
$\operatorname{Dom} \left({\mathcal R^{-1}}\right) := \left\{{t \in T: \exists s \in S: \left({t, s}\right) \in \mathcal R^{-1}}\right\}$


\(\displaystyle x\) \(\in\) \(\displaystyle \operatorname{Im} \left({\mathcal R}\right)\) $\quad$ $\quad$
\(\displaystyle \iff \ \ \) \(\displaystyle \exists s \in S: \left({s, x}\right)\) \(\in\) \(\displaystyle \mathcal R\) $\quad$ Definition of Image of Relation $\quad$
\(\displaystyle \iff \ \ \) \(\displaystyle \exists s \in S: \left({x, s}\right)\) \(\in\) \(\displaystyle \mathcal R^{-1}\) $\quad$ Definition of Inverse Relation $\quad$
\(\displaystyle \iff \ \ \) \(\displaystyle x\) \(\in\) \(\displaystyle \operatorname{Dom} \left({\mathcal R^{-1} }\right)\) $\quad$ Definition of Domain of Relation $\quad$

$\blacksquare$


Also see


Sources