One-to-Many Image of Intersections

Theorem

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

Then:

$\forall S_1, S_2 \subseteq S: \mathcal R \left({S_1 \cap S_2}\right) = \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$

iff $\mathcal R$ is one-to-many.

General Result

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

Let $\mathcal P \left({S}\right)$ be the power set of $S$.

Then:

$\displaystyle \forall \mathbb S \subseteq \mathcal P \left({S}\right): \mathcal R \left({\bigcap \mathbb S}\right) = \bigcap_{X \in \, \mathbb S} \mathcal R \left({X}\right)$

iff $\mathcal R$ is one-to-many.

Proof

Sufficient Condition

Suppose that:

$\forall S_1, S_2 \subseteq S: \mathcal R \left({S_1 \cap S_2}\right) = \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$

If $S$ is singleton, the result follows immediately as $\mathcal R$ would have to be one-to-many.

So, assume $S$ is not singleton, and suppose $\mathcal R$ is specifically not one-to-many.

So:

$\exists x, y \in S: \exists z \in T: \left({x, z}\right) \in T, \left({y, z}\right) \in T, x \ne y$.

and of course $\left\{{x}\right\} \subseteq S, \left\{{y}\right\} \subseteq S$.

So:

• $z \in \mathcal R \left({\left\{{x}\right\}}\right)$
• $z \in \mathcal R \left({\left\{{y}\right\}}\right)$

and so by definition of intersection:

$z \in \mathcal R \left({\left\{{x}\right\}}\right) \cap \mathcal R \left({\left\{{y}\right\}}\right)$

But $\left\{{x}\right\} \cap \left\{{y}\right\} = \varnothing$.

Thus from Image of Null is Null:

$\mathcal R \left({\left\{{x}\right\} \cap \left\{{y}\right\}}\right) = \varnothing$

and so:

$\mathcal R \left({\left\{{x}\right\} \cap \left\{{y}\right\}}\right) \ne \mathcal R \left({\left\{{x}\right\}}\right) \cap \mathcal R \left({\left\{{y}\right\}}\right)$

$\Box$

Necessary Condition

Let $\mathcal R$ be one-to-many.

From Image of Intersection, we already have:

$\mathcal R \left({S_1 \cap S_2}\right) \subseteq \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$.

So we just need to show:

$\mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right) \subseteq \mathcal R \left({S_1 \cap S_2}\right)$.

Let $t \in \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$.

Then:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle t\)	\(\in\)	\(\displaystyle \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle t\)	\(\in\)	\(\displaystyle \mathcal R \left({S_1}\right) \land t \in \mathcal R \left({S_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Intersection
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \exists s_1 \in S_1: \left({s_1, t}\right)\)	\(\in\)	\(\displaystyle \mathcal R \land \exists s_2 \in S_2: \left({s_2, t}\right) \in \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Relation
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle s_1\)	\(=\)	\(\displaystyle s_2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	$\mathcal R$ is one-to-many
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle s_1 = s_2\)	\(\in\)	\(\displaystyle S_1 \land s_1 = s_2 \in S_2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle s_1 = s_2\)	\(\in\)	\(\displaystyle S_1 \cap S_2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Intersection
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \mathcal R \left({s_1}\right) = \mathcal R \left({s_2}\right)\)	\(\in\)	\(\displaystyle \mathcal R \left({S_1 \cap S_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Subset of Image
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)\)	\(\subseteq\)	\(\displaystyle \mathcal R \left({S_1 \cap S_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Subset

So if $\mathcal R$ is one-to-many, it follows that:

$\mathcal R \left({S_1 \cap S_2}\right) = \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$

$\Box$

Putting the results together, we see that:

$\mathcal R \left({S_1 \cap S_2}\right) = \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$ iff $\mathcal R$ is one-to-many.

$\blacksquare$

Proof of General Result

Sufficient Condition (General Result)

Suppose:

$\displaystyle \mathcal R \left({\bigcap \mathbb S}\right) = \bigcap_{X \in \, \mathbb S} \mathcal R \left({X}\right)$

where $\mathbb S$ is any subset of $\mathcal P \left({S}\right)$.

Then by definition of $\mathbb S$:

$\forall S_1, S_2 \subseteq S: \mathcal R \left({S_1 \cap S_2}\right) = \mathcal R \left({S_1}\right) \cap \mathcal R \left({S_2}\right)$

and the sufficient condition applies for the main proof.

So $\mathcal R$ is one-to-many.

$\Box$

Necessary Condition (General Result)

Suppose $\mathcal R$ is one-to-many.

From Image of Intersection, we already have:

$\displaystyle \mathcal R \left({\bigcap \mathbb S}\right) \subseteq \bigcap_{X \in \ \mathbb S} \mathcal R \left({X}\right)$

so we just need to show:

$\displaystyle \forall \mathbb S \subseteq \mathcal P \left({S}\right): \bigcap_{X \in \ \mathbb S} \mathcal R \left({X}\right) \subseteq \mathcal R \left({\bigcap \mathbb S}\right)$

Let:

$\displaystyle t \in \bigcap_{X \in \ \mathbb S} \mathcal R \left({X}\right)$.

Then:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle t\)	\(\in\)	\(\displaystyle \bigcap_{X \in \ \mathbb S} \mathcal R \left({X}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \forall X \in \mathbb S: t\)	\(\in\)	\(\displaystyle \mathcal R \left({X}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Intersection
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \forall X \in \mathbb S: \exists x \in X: \left({x, t}\right)\)	\(\in\)	\(\displaystyle \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Relation
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle x\)	\(\in\)	\(\displaystyle \bigcap \mathbb S\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	$\mathcal R$ is one-to-many
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \mathcal R \left({x}\right)\)	\(\in\)	\(\displaystyle \mathcal R \left({\bigcap \mathbb S}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Subset of Image
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \bigcap_{X \in \ \mathbb S} \mathcal R \left({X}\right)\)	\(\subseteq\)	\(\displaystyle \mathcal R \left({\bigcap \mathbb S}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Subset

So if $\mathcal R$ is one-to-many, it follows that:

$\displaystyle \forall \mathbb S \subseteq \mathcal P \left({S}\right): \mathcal R \left({\bigcap \mathbb S}\right) = \bigcap_{X \in \ \mathbb S} \mathcal R \left({X}\right)$

$\Box$

Putting the results together:

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

$\displaystyle \mathcal R \left({\bigcap \mathbb S}\right) = \bigcap_{X \in \ \mathbb S} \mathcal R \left({X}\right)$

where $\mathbb S$ is any subset of $\mathcal P \left({S}\right)$.

$\blacksquare$