One-to-Many Image of Set Difference

From ProofWiki
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:

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


Then:

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


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

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

Then:

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

Thus:

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

$\Box$


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.

$\blacksquare$