Image under Subset of Relation is Subset of Image under Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be sets.

Let $\RR_1 \subseteq S \times T$ be a relation in $S \times T$.

Let $\RR_2 \subseteq \RR_1$.

Let $A \subseteq S$.


Then:

$\RR_2 \sqbrk A \subseteq \RR_1 \sqbrk A$

where $\RR_1 \sqbrk A$ denotes the image of $A$ under $\RR_1$.


Corollary

Let $x \in S$.


Then:

$\map {\RR_2} x \subseteq \map {\RR_1} x$

where $\map {\RR_1} x$ denotes the image of $x$ under $\RR_1$.


Proof

\(\ds y\) \(\in\) \(\ds \RR_2 \sqbrk A\)
\(\ds \leadsto \ \ \) \(\ds \exists x \in A: \, \) \(\ds \tuple {x, y}\) \(\in\) \(\ds \RR_2\) Definition of Image of Subset under Relation
\(\ds \leadsto \ \ \) \(\ds \exists x \in A: \, \) \(\ds \tuple {x, y}\) \(\in\) \(\ds \RR_1\) Definition of Subset
\(\ds \leadsto \ \ \) \(\ds y\) \(\in\) \(\ds \RR_1 \sqbrk A\) Definition of Image of Subset under Relation

$\blacksquare$


Sources