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$