Surjection Induced by Powerset is Induced by Surjection

From ProofWiki
Jump to navigation Jump to search

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.




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

$\blacksquare$