# Image of Set Difference under Relation

Jump to navigation
Jump to 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:

- $\relcomp {\Img {\mathcal R} } {\mathcal R \sqbrk A} \subseteq \mathcal R \sqbrk {\relcomp S A}$

where:

- $\Img {\mathcal R}$ denotes the image of $\mathcal R$
- $\mathcal R \sqbrk A$ denotes the image of $A$ under $\mathcal R$.

## Proof

\(\displaystyle y\) | \(\in\) | \(\displaystyle \mathcal R \sqbrk A \setminus \mathcal R \sqbrk B\) | |||||||||||

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

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

\(\displaystyle \leadsto \ \ \) | \(\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.