# Image of Set Difference under Relation

## 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\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle \exists x \in A: x \notin B: \tuple {x, y}\) | \(\in\) | \(\displaystyle \mathcal R\) | $\quad$ Definition of Image of Subset under Relation | $\quad$ | ||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle \exists x \in A \setminus B: \tuple {x, y}\) | \(\in\) | \(\displaystyle \mathcal R\) | $\quad$ Definition of Set Difference | $\quad$ | ||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle y\) | \(\in\) | \(\displaystyle \mathcal R \sqbrk {A \setminus B}\) | $\quad$ Definition of Image of Subset under Relation | $\quad$ |

$\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.