One-to-Many Image of Set Difference/Corollary 2

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathcal R \subseteq S \times T$ be a relation which is one-to-many.

Let $A$ and $B$ be subsets of $S$.


Then:

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

where $\complement$ (in this context) denotes relative complement.


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 One-to-Many Image of Set Difference: 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) = \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) = \mathcal R \left[{\complement_S \left({A}\right)}\right]$

that is:

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


Hence the result from One-to-Many Image of Set Difference.

$\blacksquare$