Image of Set Difference under Relation/Corollary 1

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 \subseteq B \subseteq S$.


Then:

$\complement_{\mathcal R \left[{B}\right]} \left({\mathcal R \left[{A}\right]}\right) \subseteq \mathcal R \left[{\complement_B \left({A}\right)}\right]$

where:

$\mathcal R \left[{B}\right]$ denotes the image of $B$ under $\mathcal R$
$\complement$ (in this context) denotes relative complement.


Proof

We have that $A \subseteq B$.

Then by definition of relative complement:

$\complement_B \left({A}\right) = B \setminus A$
$\complement_{\mathcal R \left[{B}\right]} \left({\mathcal R \left[{A}\right]}\right) = \mathcal R \left[{B}\right] \setminus \mathcal R \left[{A}\right]$


Hence, when $A \subseteq B$:

$\complement_{\mathcal R \left[{B}\right]} \left({\mathcal R \left[{A}\right]}\right) \subseteq \mathcal R \left[{\complement_B \left({A}\right)}\right]$

means exactly the same thing as:

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

$\blacksquare$