Image of Subset under Relation equals Union of Images of Elements

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be sets.

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

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


Then:

$\displaystyle \RR \sqbrk X = \bigcup_{x \mathop \in X} \map \RR x$

where:

$\RR \sqbrk X$ is the image of the subset $X$ under $\RR$
$\map \RR x$ is the image of the element $x$ under $\RR$.


Proof

By definition:

$\RR \sqbrk X = \set {y \in T: \exists x \in X: \tuple {x, y} \in \RR}$
$\map \RR x = \set {y \in T:\tuple {x, y} \in \RR}$


First:

\(\displaystyle y\) \(\in\) \(\displaystyle \RR \sqbrk X\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \exists x \in X: \tuple {x, y}\) \(\in\) \(\displaystyle \RR\) Definition of $\RR \sqbrk X$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {x, y}\) \(\in\) \(\displaystyle \bigcup_{x \mathop \in X} \set {\tuple {x, y} \in \RR}\) Definition of Set Union
\(\displaystyle \leadsto \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \bigcup_{x \mathop \in X} \set {y \in T: \tuple {x, y} \in \RR}\) Definition of Relation
\(\displaystyle \leadsto \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \bigcup_{x \mathop \in X} \map \RR x\) Definition of $\map \RR x$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \RR \sqbrk X\) \(\subseteq\) \(\displaystyle \bigcup_{x \mathop \in X} \map \RR x\) Definition of Subset


Then:

\(\displaystyle y\) \(\in\) \(\displaystyle \bigcup_{x \mathop \in X} \map \RR x\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \bigcup_{x \mathop \in X} \set {y \in T: \tuple {x, y} \in \RR}\) Definition of $\map \RR x$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \exists x \in X: \tuple {x, y}\) \(\in\) \(\displaystyle \RR\) Definition of Set Union
\(\displaystyle \leadsto \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \set {y \in T: \exists x \in X: \tuple {x, y} \in \RR}\) Definition of Relation
\(\displaystyle \leadsto \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \RR \sqbrk X\) Definition of $\RR \sqbrk X$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \bigcup_{x \mathop \in X} \map \RR x\) \(\subseteq\) \(\displaystyle \RR \sqbrk X\) Definition of Subset


So:

$\displaystyle \bigcup_{x \mathop \in X} \map \RR x \subseteq \RR \sqbrk X$

and:

$\displaystyle \RR \sqbrk X \subseteq \bigcup_{x \mathop \in X} \map \RR x$


The result follows by definition of set equality.

$\blacksquare$