Subset equals Image of Preimage implies Surjection/Proof 2

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let:

$\forall B \subseteq T: B = \paren {f \circ f^{-1} } \sqbrk B$

where $f \sqbrk B$ denotes the image of $B$ under $f$.

Then $f$ is a surjection.


Proof

Suppose $f$ is not a surjection.

$T$ must have at least two elements for this to be the case.

Let one of these two elements not be the image of any element of $S$.

That is, let $b_1, b_2 \in T$ such that:

$\exists a \in S: f \paren a = b_1$
$\nexists x \in S: f \paren x = b_2$


Let $B = \set {b_1, b_2}$.

Then:

\(\ds f^{-1} \sqbrk B\) \(=\) \(\ds A\) for some $A \subseteq S$
\(\ds \leadsto \ \ \) \(\ds f \sqbrk {f^{-1} \sqbrk B}\) \(=\) \(\ds \set {b_1}\) as $b_2$ has no preimage
\(\ds \leadsto \ \ \) \(\ds f \sqbrk {f^{-1} \sqbrk B}\) \(\ne\) \(\ds B\) as $B = \set {b_1, b_2}$

So by the Rule of Transposition:

$\forall B \subseteq S: B = \paren {f \circ f^{-1} } \sqbrk B$

implies that $f$ is an surjection.

$\blacksquare$


Sources