Image of Set Difference under Relation

From ProofWiki
Jump to: navigation, search

Theorem

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

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


Then:

$\mathcal R \sqbrk A \setminus \mathcal R \sqbrk B \subseteq \mathcal R \sqbrk {A \setminus B}$

where:

$\setminus$ denotes set difference
$\mathcal R \left[{A}\right]$ denotes image of $A$ under $\mathcal R$.


Corollary 1

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.


Corollary 2

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

\(\displaystyle y\) \(\in\) \(\displaystyle \mathcal R \sqbrk A \setminus \mathcal R \sqbrk B\)
\(\displaystyle \implies \ \ \) \(\displaystyle \exists x \in A: x \notin B: \tuple {x, y}\) \(\in\) \(\displaystyle \mathcal R\) Definition of Image of Subset under Relation
\(\displaystyle \implies \ \ \) \(\displaystyle \exists x \in A \setminus B: \tuple {x, y}\) \(\in\) \(\displaystyle \mathcal R\) Definition of Set Difference
\(\displaystyle \implies \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle \mathcal R \sqbrk {A \setminus B}\) Definition of Image of Subset under Relation

$\blacksquare$


Also see


Note that equality does not hold in general.

See the note on Image of Set Difference under Mapping for an example of a mapping (which is of course a relation) for which it does not.