Direct Image Mapping of Surjection is Surjection/Proof 1

From ProofWiki
Jump to: navigation, search

Theorem

Let $f: S \to T$ be a surjection.


Then the direct image mapping of $f$:

$f^\to: \powerset S \to \powerset T$

is a surjection.


Proof

Let $f: S \to T$ be a surjection.

Then:

$\forall y \in T: \exists x \in S: f \paren x = y$

From the Quotient Theorem for Surjections, there is one and only one bijection $r: S / \mathcal R_f \to T$ such that $r \circ q_{\mathcal R_f} = f$.

Each element of $S / \mathcal R_f$ is a subset of $S$ and therefore an element of $\powerset S$.

Thus as $r: S / \mathcal R_f \to T$ is a bijection, and hence a fortiori also an injection:

$\forall X_1, X_2 \in \powerset S: \map r {X_1} = \map r {X_2} \implies X_1 = X_2$


Because $f$ is a surjection, every $y \in T$ is mapped to by exactly one element of the partition of $S$ defined by $\mathcal R_f$.

Let $T = \set {y_1, y_2, \ldots}$.

Let the partition defined by $\mathcal R_f$ be $\bigcup \paren {X_1, X_2, \ldots}$ where $\map r {X_n} = y_n$.


Let $Y_r \in \powerset T$, such that $Y_r = \set {y_{r_1}, y_{r_2}, \ldots}$.

Then:

$\map {f^\to} {X_r} = Y_r$

where $\displaystyle X_r = \bigcup \paren {X_{r_1}, X_{r_2}, \ldots}$.

As $\set {X_1, X_2, \ldots}$ is a partition of $S$, $\forall Y_r \in \powerset T: X_r$ is unique.

Thus $f^\to: \powerset S \to \powerset T$ is a surjection.

$\blacksquare$