Direct Image Mapping of Relation is Mapping

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be sets.

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

Let $\mathcal R^\to: \powerset S \to \powerset T$ be the direct image mapping of $\mathcal R$:

$\forall X \in \powerset S: \map {\mathcal R^\to} X = \set {t \in T: \exists s \in X: \tuple {s, t} \in \mathcal R}$


Then $\mathcal R^\to$ is indeed a mapping.


Proof

Take the general relation $\mathcal R \subseteq S \times T$.

Let $X \subseteq S$, that is $X \in \powerset S$.


Suppose $X = \O$.

Then from Image of Empty Set is Empty Set:

$\map {\mathcal R^\to} X = \O \subseteq T$


Suppose $X = S$.

Then from Image is Subset of Codomain: Corollary 1:

$\map {\mathcal R^\to} X = \Img {\mathcal R} \subseteq T$


Finally, suppose $\O \subset X \subset S$.

From Image is Subset of Codomain, again:

$\map {\mathcal R^\to} X \subseteq T$


Now, from the definition of the power set, we have that:

$Y \subseteq T \iff Y \in \powerset T$


We defined $R^\to \subseteq \powerset S \times \powerset T$ such that:

$R^\to: \powerset S \to \powerset T: \map {\mathcal R^\to} X = \set {t \in T: \exists s \in X: \tuple {s, t} \in \mathcal R}$

By definition, there is only one $\map {\mathcal R^\to} X$ for any given $X$, and so $R^\to$ is many-to-one.


We have shown that:

$\forall X \subseteq S: \map {\mathcal R^\to} X \in \powerset T$

So:

$\forall X \in \powerset S: \exists_1 Y \in \powerset T: \map {\mathcal R^\to} X = Y$

So:

$R^\to$ is defined for all $X \in \powerset S$

and therefore $R^\to$ is a mapping.

$\blacksquare$


Also see