Image of Set Difference under Relation/Corollary 2

From ProofWiki
Jump to: navigation, search

Corollary to Image of Set Difference under Relation

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

Let $A$ be a subset of $S$.


Then:

$\complement_{\operatorname{Im} \left({\mathcal R}\right)} \left({\mathcal R \left[{A}\right]}\right) \subseteq \mathcal R \left[{\complement_S \left({A}\right)}\right]$

where:

$\operatorname{Im} \left({\mathcal R}\right)$ denotes the image of $\mathcal R$
$\mathcal R \left[{A}\right]$ denotes the image of $A$ under $\mathcal R$.


Proof

By definition of the image of $\mathcal R$:

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

So, when $B = S$ in Image of Set Difference under Relation: Corollary 1:

$\complement_{\operatorname{Im} \left({\mathcal R}\right)} \left({\mathcal R \left[{A}\right]}\right) = \complement_{\mathcal R \left[{S}\right]} \left({\mathcal R \left[{A}\right]}\right)$


Hence:

$\complement_{\operatorname{Im} \left({\mathcal R}\right)} \left({\mathcal R \left[{A}\right]}\right) \subseteq \mathcal R \left[{\complement_S \left({A}\right)}\right]$

means exactly the same thing as:

$\complement_{\mathcal R \left[{S}\right]} \left({\mathcal R \left[{A}\right]}\right) \subseteq \mathcal R \left[{\complement_S \left({A}\right)}\right]$

that is:

$\mathcal R \left[{S}\right] \setminus \mathcal R \left[{A}\right] \subseteq \mathcal R \left[{S \setminus A}\right]$

$\blacksquare$