Image of Intersection under Mapping

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ and $T$ be sets.

Let $f: S \to T$ be a mapping.

Let $S_1$ and $S_2$ be subsets of $S$.


Then:

$f \sqbrk {S_1 \cap S_2} \subseteq f \sqbrk {S_1} \cap f \sqbrk {S_2}$


This can be expressed in the language and notation of direct image mappings as:

$\forall S_1, S_2 \in \powerset S: \map {f^\to} {S_1 \cap S_2} \subseteq \map {f^\to} {S_1} \cap \map {f^\to} {S_2}$


That is, the image of the intersection of subsets of a mapping is a subset of the intersection of their images.


General Result

Let $S$ and $T$ be sets.

Let $f: S \to T$ be a mapping.

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

Let $\mathbb S \subseteq \mathcal P \left({S}\right)$.


Then:

$\displaystyle f \left[{\bigcap \mathbb S}\right] \subseteq \bigcap_{X \mathop \in \mathbb S} f \left[{X}\right]$


Family of Sets

Let $S$ and $T$ be sets.

Let $\family {S_i}_{i \mathop \in I}$ be a family of subsets of $S$.

Let $f: S \to T$ be a mapping.


Then:

$\displaystyle f \sqbrk {\bigcap_{i \mathop \in I} S_i} \subseteq \bigcap_{i \mathop \in I} f \sqbrk {S_i}$

where $\displaystyle \bigcap_{i \mathop \in I} S_i$ denotes the intersection of $\family {S_i}_{i \mathop \in I}$.


Proof 1

\(\displaystyle S_1 \cap S_2\) \(\subseteq\) \(\displaystyle S_1\) Intersection is Subset
\(\displaystyle \leadsto \ \ \) \(\displaystyle f \sqbrk {S_1 \cap S_2}\) \(\subseteq\) \(\displaystyle f \sqbrk {S_1}\) Image of Subset under Mapping is Subset of Image


\(\displaystyle S_1 \cap S_2\) \(\subseteq\) \(\displaystyle S_2\) Intersection is Subset
\(\displaystyle \leadsto \ \ \) \(\displaystyle f \sqbrk {S_1 \cap S_2}\) \(\subseteq\) \(\displaystyle f \sqbrk {S_2}\) Image of Subset under Mapping is Subset of Image


\(\displaystyle \leadsto \ \ \) \(\displaystyle f \sqbrk {S_1 \cap S_2}\) \(\subseteq\) \(\displaystyle f \sqbrk {S_1} \cap f \sqbrk {S_2}\) Intersection is Largest Subset

$\blacksquare$


Proof 2

As $f$, being a mapping, is also a relation, we can apply Image of Intersection under Relation:

$\mathcal R \sqbrk {S_1 \cap S_2} \subseteq \mathcal R \sqbrk {S_1} \cap \mathcal R \sqbrk {S_2}$

$\blacksquare$


Examples

Square Function

Let:

$S_1 = \set {x \in \Z: x \le 0}$
$S_2 = \set {x \in \Z: x \ge 0}$
$f: \Z \to \Z: \forall x \in \Z: \map f x = x^2$


We have:

$f \sqbrk {S_1} = \set {0, 1, 4, 9, 16, \ldots} = f \sqbrk {S_2}$

Then:

$f \sqbrk {S_1} \cap f \sqbrk {S_2} = \set {0, 1, 4, 9, 16, \ldots}$

but:

$f \sqbrk {S_1 \cap S_2} = f \sqbrk {\set 0} = \set 0$


As can be seen, the inclusion is proper, that is:

$f \sqbrk {S_1 \cap S_2} \ne f \sqbrk {S_1} \cap f \sqbrk {S_2}$


First Projection on Subsets of $\N \times \N$

Let $\pr_1: \N \times \N \to \N$ denote the first projection from the cartesian space $\N \times \N$ of the natural numbers.

Let:

\(\displaystyle S_1\) \(=\) \(\displaystyle \set {\tuple {m, 1}: m \in \N}\)
\(\displaystyle S_2\) \(=\) \(\displaystyle \set {\tuple {0, 2 n}: n \in \N}\)


First note that we have:

\(\displaystyle S_1 \cap S_1\) \(=\) \(\displaystyle \set {\tuple {m, 1}: m \in \N} \cap \set {\tuple {0, 2 n}: n \in \N}\)
\(\displaystyle \) \(=\) \(\displaystyle \O\) as $1$ is not an integer of the form $2 n$


Then:

\(\displaystyle \pr_1 \sqbrk {S_1}\) \(=\) \(\displaystyle \set {m: m \in \N}\)
\(\displaystyle \) \(=\) \(\displaystyle \N\)
and:
\(\displaystyle \pr_1 \sqbrk {S_2}\) \(=\) \(\displaystyle \set 0\)
\(\displaystyle \) \(=\) \(\displaystyle 0\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \pr_1 \sqbrk {S_1} \cap \pr_1 \sqbrk {S_2}\) \(=\) \(\displaystyle \N \cap 0\)
\(\displaystyle \) \(=\) \(\displaystyle 0\)


while:

\(\displaystyle \pr_1 \sqbrk {S_1 \cap S_2}\) \(=\) \(\displaystyle \pr_1 \sqbrk {\O}\)
\(\displaystyle \) \(=\) \(\displaystyle \O\)


As can be seen, the inclusion is proper, that is:

$\pr_1 \sqbrk {S_1 \cap S_2} \ne \pr_1 \sqbrk {S_1} \cap \pr_1 \sqbrk {S_2}$


Also see


Sources