Image of Subset under Relation equals Union of Images of Elements

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ and $T$ be sets.

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

Let $X \subseteq S$ be a subset of $S$.


Then:

$\displaystyle \mathcal R \left[{X}\right] = \bigcup_{x \mathop \in X} \mathcal R \left({x}\right)$

where:

$\mathcal R \left[{X}\right]$ is the image of the subset $X$ under $\mathcal R$
$\mathcal R \left({x}\right)$ is the image of the element $x$ under $\mathcal R$.


Proof

By definition:

$\mathcal R \left[{X}\right] = \left\{ {y \in T: \exists x \in X: \left({x, y}\right) \in \mathcal R}\right\}$
$\mathcal R \left({x}\right) = \left\{ {y \in T: \left({x, y}\right) \in \mathcal R}\right\}$


First:

\(\displaystyle y\) \(\in\) \(\displaystyle \mathcal R \left[{X}\right]\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \exists x \in X: \left({x, y}\right)\) \(\in\) \(\displaystyle \mathcal R\) $\quad$ Definition of $\mathcal R \left[{X}\right]$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \bigcup_{x \mathop \in X} \left\{ {\left({x, y}\right) \in \mathcal R}\right\}\) $\quad$ Definition of Set Union $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \bigcup_{x \mathop \in X} \left\{ {y \in T: \left({x, y}\right) \in \mathcal R}\right\}\) $\quad$ Definition of Relation $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \bigcup_{x \mathop \in X} \mathcal R \left({x}\right)\) $\quad$ Definition of $\mathcal R \left({x}\right)$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \mathcal R \left[{X}\right]\) \(\subseteq\) \(\displaystyle \bigcup_{x \mathop \in X} \mathcal R \left({x}\right)\) $\quad$ Definition of Subset $\quad$


Then:

\(\displaystyle y\) \(\in\) \(\displaystyle \bigcup_{x \mathop \in X} \mathcal R \left({x}\right)\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \bigcup_{x \mathop \in X} \left\{ {y \in T: \left({x, y}\right) \in \mathcal R}\right\}\) $\quad$ Definition of $\mathcal R \left({x}\right)$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \exists x \in X: \left({x, y}\right)\) \(\in\) \(\displaystyle \mathcal R\) $\quad$ Definition of Set Union $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \left\{ {y \in T: \exists x \in X: \left({x, y}\right) \in \mathcal R}\right\}\) $\quad$ Definition of Relation $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \mathcal R \left[{X}\right]\) $\quad$ Definition of $\mathcal R \left[{X}\right]$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \bigcup_{x \mathop \in X} \mathcal R \left({x}\right)\) \(\subseteq\) \(\displaystyle \mathcal R \left[{X}\right]\) $\quad$ Definition of Subset $\quad$


So:

$\displaystyle \bigcup_{x \mathop \in X} \mathcal R \left({x}\right) \subseteq \mathcal R \left[{X}\right]$

and:

$\displaystyle \mathcal R \left[{X}\right] \subseteq \bigcup_{x \mathop \in X} \mathcal R \left({x}\right)$


The result follows by definition of set equality.

$\blacksquare$