One-to-Many Image of Set Difference

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:

$(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 $\mathcal R \subseteq S \times T$ be a relation which is one-to-many.

Let $A \subseteq B \subseteq S$.


Then:

$\complement_{\mathcal R \left[{B}\right]} \left({\mathcal R \left[{A}\right]}\right) = \mathcal R \left[{\complement_B \left({A}\right)}\right]$

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$ and $B$ be subsets of $S$.


Then:

$\complement_{\operatorname{Im} \left({\mathcal R}\right)} \left({\mathcal R \left[{A}\right]}\right) = \mathcal R \left[{\complement_S \left({A}\right)}\right]$


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$