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!)