Subset equals Image of Preimage implies Surjection
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 1
Let $f$ be such that:
- $\forall B \subseteq T: B = \paren {f \circ f^{-1} } \sqbrk B$
In particular, it holds for $T$ itself.
Hence:
| \(\ds T\) | \(=\) | \(\ds \paren {f \circ f^{-1} } \sqbrk T\) | ||||||||||||
| \(\ds T\) | \(=\) | \(\ds f \sqbrk {f^{-1} \sqbrk T}\) | Definition of Composition of Mappings | |||||||||||
| \(\ds \) | \(\subseteq\) | \(\ds f \sqbrk S\) | Image of Subset under Mapping is Subset of Image | |||||||||||
| \(\ds \) | \(=\) | \(\ds \Img f\) | Definition of Image of Mapping | |||||||||||
| \(\ds \) | \(\subseteq\) | \(\ds T\) | Image is Subset of Codomain: Corollary $1$ |
So:
- $T \subseteq \Img f \subseteq T$
and so by definition of set equality:
- $\Img f = T$
So, by definition, $f$ is a surjection.
$\blacksquare$
Proof 2
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$