One-to-Many Image of Set Difference

From ProofWiki
Jump to navigation Jump to search


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

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


$(1): \quad \mathcal R \left[{A}\right] \setminus \mathcal R \left[{B}\right] = \mathcal R \left[{A \setminus B}\right]$

if and only if $\mathcal R$ is one-to-many.

Corollary 1

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

Let $A \subseteq B \subseteq S$.


$\relcomp {\RR \sqbrk B} {\RR \sqbrk A} = \RR \sqbrk {\relcomp B A}$

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

Corollary 2

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

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


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


Sufficient Condition

First, to show that $(1)$ holds if $\mathcal R$ is one-to-many.

From Image of Set Difference under Relation, we already have:

$\mathcal R \left[{A}\right] \setminus \mathcal R \left[{B}\right] \subseteq \mathcal R \left[{A \setminus B}\right]$

So we just need to show:

$\mathcal R \left[{A \setminus B}\right] \subseteq \mathcal R \left[{A}\right] \setminus \mathcal R \left[{B}\right]$

Let $t \notin \mathcal R \left[{A}\right] \setminus \mathcal R \left[{B}\right]$.

Then $t \notin \mathcal R \left[{A}\right] \lor t \in \mathcal R \left[{B}\right]$ by De Morgan's Laws.

Suppose $t \notin \mathcal R \left[{A}\right]$.

Then by definition of a relation:

$\neg \exists s \in A: \left({s, t}\right) \in \mathcal R$

By Image of Subset is Subset of Image:

$\mathcal R \left[{A \setminus B}\right] \subseteq \mathcal R \left[{A}\right]$

Thus, by definition of subset and Rule of Transposition:

$t \notin \mathcal R \left[{A}\right] \implies t \notin \mathcal R \left[{A \setminus B}\right]$

Now suppose $t \in \mathcal R \left[{B}\right]$.


$\exists s \in B: \left({s, t}\right) \in \mathcal R$

Because $\mathcal R$ is one-to-many:

$\forall x \in S: \left({x, t}\right) \in \mathcal R \implies x = s$

and thus:

$x \in B$


$x \notin A \setminus B$

and hence:

$t \notin \mathcal R \left[{A \setminus B}\right]$

So by Proof by Cases:

$t \notin \mathcal R \left[{A}\right] \setminus \mathcal R \left[{B}\right] \implies t \notin \mathcal R \left[{A \setminus B}\right]$

The result follows from Set Complement inverts Subsets:

$S \subseteq T \iff \complement \left({T}\right) \subseteq \complement \left({S}\right)$


Necessary Condition

Now for the converse: If $(1)$ holds, it is to be shown that $\mathcal R$ is one-to-many.

Let $s, t \in S$ be distinct.

That is, $s \ne t$.

Then in particular:

$\left\{{s}\right\} \setminus \left\{{t}\right\} = \left\{{s}\right\}$

Applying $(1)$ to these two sets, it follows that:

$\mathcal R \left[{\left\{{s}\right\}}\right] \setminus \mathcal R \left[{\left\{{t}\right\}}\right] = \mathcal R \left[{\left\{{s}\right\}}\right]$

By Set Difference with Disjoint Set, this implies that:

$\mathcal R \left[{\left\{{s}\right\}}\right] \cap \mathcal R \left[{\left\{{t}\right\}}\right] = \varnothing$

It follows that every element of $T$ can be related to at most one element of $S$.

That is, $\mathcal R$ is one-to-many.