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

From ProofWiki
Jump to: navigation, search

Theorem

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

Let $A \subseteq B \subseteq S$.


Then:

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

where $\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) = \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] = \mathcal R \left[{B \setminus A}\right]$


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

$\blacksquare$