Mapping Induced on Power Set by Relation
Contents |
Theorem
Let $\mathcal R \subseteq S \times T$ be a relation on $S \times T$.
Let $f_\mathcal R$ be the mapping induced by $\mathcal R$:
- $f_\mathcal R: \mathcal P \left({S}\right) \to \mathcal P \left({T}\right): f_\mathcal R \left({X}\right) = \mathcal R \left({X}\right)$
Then $f_\mathcal R$ is indeed a mapping.
Proof
Take the general relation $\mathcal R \subseteq S \times T$.
Let $X \subseteq S$, i.e. $X \in \mathcal P \left({S}\right)$.
- Suppose $X = \varnothing$. Then $\mathcal R \left({X}\right) = \varnothing \subseteq T$, from Image of Null is Null.
- Suppose $X = S$. Then $\mathcal R \left({X}\right) = \operatorname{Im} \left({\mathcal R}\right) \subseteq T$ from Image of Domain is Subset of Codomain.
- Finally, suppose $\varnothing \subset X \subset S$. From Image is Subset of Codomain, again we see that $\mathcal R \left({X}\right) \subseteq T$.
Now, from the definition of the power set, we have that $Y \subseteq T \iff Y \in \mathcal P \left({T}\right)$.
We defined $f_\mathcal R \subseteq \mathcal P \left({S}\right) \times \mathcal P \left({T}\right)$ such that:
- $f_\mathcal R : \mathcal P \left({S}\right) \to \mathcal P \left({T}\right): f_\mathcal R \left({X}\right) = \mathcal R \left({X}\right)$
Clearly, by definition, there is only one $\mathcal R \left({X}\right)$ for any given $X$, and so $f_\mathcal R$ is functional.
We have shown that $\forall X \subseteq S: \mathcal R \left({X}\right) \in \mathcal P \left({T}\right)$.
So:
- $\forall X \in \mathcal P \left({S}\right): \exists_1 Y \in \mathcal P \left({T}\right): \mathcal R \left({X}\right) = Y$
and thus:
- $\forall X \in \mathcal P \left({S}\right): \exists_1 Y \in \mathcal P \left({T}\right): f_\mathcal R \left({X}\right) = Y$.
So:
- $f_\mathcal R$ is defined for all $X \in \mathcal P \left({S}\right)$
and therefore $f_\mathcal R$ is a mapping.
$\blacksquare$
Also see
