Surjection Induced by Powerset is Induced by Surjection
Theorem
Let $\mathcal R \subseteq S \times T$ be a relation.
Let $\mathcal R^\to: \powerset S \to \powerset T$ be the direct image mapping $\mathcal R$.
Let $\mathcal R^\to$ be a surjection.
Let $X = \Preimg {\mathcal R}$, that is, the preimage of $\mathcal R$.
Then $\mathcal R {\restriction_X} \subseteq X \times T$, that is, the restriction of $\mathcal R$ to $X$, is a surjection.
Proof
Let $X$ be the preimage of $\mathcal R$.
Suppose $\mathcal R {\restriction_X} \subseteq X \times T$ is a mapping, but not a surjection.
Then:
- $\exists y \in T: \neg \exists x \in S: \tuple {x, y} \in \mathcal R$
Because no element of $S$ relates to $y$, no subset of $S$ contains any element of $S$ that relates to the subset $\left\{{y}\right\} \subseteq T$.
Thus:
- $\exists \set y \in \powerset T: \neg \exists X \in \powerset S: \map {\mathcal R^\to} X = \set y$
So we see that $\mathcal R^\to: \powerset S \to \powerset T$ is not a surjection.
Now, suppose $\mathcal R {\restriction_X} \subseteq X \times T$ is not even a mapping.
This could happen, according to the definition of a mapping, in one of two ways:
- $(1): \quad \exists x \in X: \neg \exists y \in T: \tuple {x, y} \in \mathcal R$
- $(2): \quad \exists x \in S: \tuple {x, y_1} \in \mathcal R \land \tuple {x, y_2} \in \mathcal R: y_1 \ne y_2$
Because $X$ is already the preimage of $\mathcal R$, the first of these cannot happen here.
For the second, it can be seen that neither $\set {y_1}$ nor $\set {y_2}$ can be in $\Rng {\map {\mathcal R^\to} {\powerset S} }$.
Therefore $\mathcal R^\to: \powerset S \to \powerset T$ can not be a surjection.
Thus, by the Rule of Transposition, the result follows.
$\blacksquare$