Surjection Induced by Powerset is Induced by Surjection

Theorem

Let $\RR \subseteq S \times T$ be a relation.

Let $\RR^\to: \powerset S \to \powerset T$ be the direct image mapping $\RR$.

Let $\RR^\to$ be a surjection.

Let $X = \Preimg \RR$, that is, the preimage of $\RR$.

Then $\RR {\restriction_X} \subseteq X \times T$, that is, the restriction of $\RR$ to $X$, is a surjection.

Proof

Let $X$ be the preimage of $\RR$.

Suppose $\RR {\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 \RR$

Because no element of $S$ relates to $y$, no subset of $S$ contains any element of $S$ that relates to the subset $\set y \subseteq T$.

Thus:

$\exists \set y \in \powerset T: \neg \exists X \in \powerset S: \map {\RR^\to} X = \set y$

So we see that $\RR^\to: \powerset S \to \powerset T$ is not a surjection.

Now, suppose $\RR {\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 \RR$

$(2): \quad \exists x \in S: \tuple {x, y_1} \in \RR \land \tuple {x, y_2} \in \RR: y_1 \ne y_2$

Because $X$ is already the preimage of $\RR$, 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 {\RR^\to} {\powerset S} }$.

Therefore $\RR^\to: \powerset S \to \powerset T$ can not be a surjection.

The validity of the material on this page is questionable. In particular: See talk page You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by resolving the issues. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Questionable}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Thus, by the Rule of Transposition, the result follows.

$\blacksquare$