Image of Domain of Relation is Image Set

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ and $T$ be sets.

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


The image of the domain of $\mathcal R$ is the image set of $\mathcal R$:

$\mathcal R \left [{\operatorname{Dom} \left({\mathcal R}\right)}\right] = \operatorname{Im} \left ({\mathcal R}\right)$

where $\operatorname{Im} \left ({\mathcal R}\right)$ is the image of $\mathcal R$.


Proof

Let $y \in \mathcal R \left [{\operatorname{Dom} \left({\mathcal R}\right)}\right]$.

\(\displaystyle y\) \(\in\) \(\displaystyle \mathcal R \left [{\operatorname{Dom} \left({\mathcal R}\right)}\right]\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \exists x \in \operatorname{Dom} \left({\mathcal R}\right): \ \ \) \(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \mathcal R\) $\quad$ Definition of Image of Subset under Relation $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \operatorname{Im} \left ({\mathcal R}\right)\) $\quad$ Definition of Image of Relation $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \mathcal R \left [{\operatorname{Dom} \left({\mathcal R}\right)}\right]\) \(\subseteq\) \(\displaystyle \operatorname{Im} \left ({\mathcal R}\right)\) $\quad$ Definition of Subset $\quad$


Let $y \in \operatorname{Im} \left ({\mathcal R}\right)$.

\(\displaystyle y\) \(\in\) \(\displaystyle \operatorname{Im} \left ({\mathcal R}\right)\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \exists x \in S: \ \ \) \(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \mathcal R\) $\quad$ Definition of Image of Relation $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \mathcal R \left [{\operatorname{Dom} \left({\mathcal R}\right)}\right]\) $\quad$ Definition of Domain of Relation $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \operatorname{Im} \left ({\mathcal R}\right)\) \(\subseteq\) \(\displaystyle \mathcal R \left [{\operatorname{Dom} \left({\mathcal R}\right)}\right]\) $\quad$ Definition of Subset $\quad$


The result follows by definition of set equality.

$\blacksquare$