Theorem. Let $f: X \rightarrow Y$ be a function and $U \subseteq Y$ s.t.
$$ f \: \text{onto} \leftrightarrow U = f(f^{-1}(U)). $$
Proof.
$$
f \: \text{onto} \leftrightarrow \underbrace{U = f(f^{-1}(U))}_{s_0}
\leftrightarrow (
(\underbrace{f \: \text{onto} \rightarrow s_0}_{(i)})
\wedge
(\underbrace{f \: \text{onto} \leftarrow s_0}_{(ii)})
)
$$
(i)
$$ f \: \text{onto} \rightarrow
(
\underbrace{U \subseteq f(f^{-1}(U))}_{(i.1)}
)
\wedge
(
\underbrace{U \supseteq f(f^{-1}(U))}_{(i.2)}
). $$
(i.1) (c-p) Given $y \notin f(f^{-1}(U)) = \{ f(x) : x \in \{ x \in X : f(x) \in U \} \}$, $y$ is either not in $U$ or in $U$ but not a mapping of an element in $X$. Since $f$ is onto, we have, by definition,
$$(\forall y \in Y)(\exists x \in X)f(x) = y,$$
which excludes the disjunction in our implication, since $every$ element from $Y$ has its counterpart in $X$. This gives rise to
$$ f \: \text{onto} \rightarrow (y \notin f(f^{-1}(U)) \rightarrow y \notin U) \leftrightarrow (y \in U \rightarrow y \in f(f^{-1}(U))
\leftrightarrow U \subseteq f(f^{-1}(U)). $$
$\Box$
(i.2) Given $y \in f(f^{-1}(U)) = \{ f(x) : x \in \{ x \in X : f(x) \in U \} \}$, we have $y \in U$, by definition. $\Box$
(ii) Suppose $f$ is not onto. Then there is a $y \in Y$ s.t. for every $x \in X$ no mapping of $x$ equals $y$: $f(x) \neq y$. Formally put:
$$ \neg f \: \text{onto} \rightarrow (\exists y \in Y) \: y \notin \{ f(x) : x \in X \} \supseteq \{ f(x) : x \in \{ x \in X : f(x) \in U \}\} = f(f^{-1}(U)). $$
Forming the contrapositive gives the required implication
$$ (\forall y \in Y) \: y \in f(f^{-1}(Y)) \rightarrow f \: \text{onto}, $$
since $U = Y$ is a special case of $U \subseteq Y$.
$\Box$
2014 DEC 29 (v1.0)
Contact me: m.herrmann followed by an -at- followed by blaetterundsterne.org.
This document created with the help of MathJax (Thank you guys!)