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

From ProofWiki
Jump to navigation Jump to search

Theorem

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

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


Then:

$\relcomp {\Img {\mathcal R} } {\mathcal R \sqbrk A} = \mathcal R \sqbrk {\relcomp S A}$

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


In the language of direct image mappings this can be presented as:

$\forall A \in \powerset S: \map {\paren {\complement_{\Img {\mathcal R} } \circ \mathcal R^\to} } A = \map {\paren {\mathcal R^\to \circ \complement_S} } A$


Proof

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

$\Img {\mathcal R} = \mathcal R \sqbrk S$


So, when $B = S$ in One-to-Many Image of Set Difference: Corollary 1:

$\relcomp {\Img {\mathcal R} } {\mathcal R \sqbrk A} = \relcomp {\mathcal R \sqbrk S} {\mathcal R \sqbrk A}$


Hence:

$\relcomp {\Img {\mathcal R} } {\mathcal R \sqbrk A} = \mathcal R \sqbrk {\relcomp S A}$

means exactly the same thing as:

$\relcomp {\mathcal R \sqbrk S} {\mathcal R \sqbrk A} = \mathcal R \sqbrk {\relcomp S A}$

that is:

$\mathcal R \sqbrk S \setminus \mathcal R \sqbrk A = \mathcal R \sqbrk {S \setminus A}$


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

$\blacksquare$