Show $S = f^{-1}(f(S))$ for all subsets $S$ iff $f$ is injective Let $f: A \rightarrow B$ be a function. How can we show that for all subsets $S$ of $A$, $S \subseteq f^{-1}(f(S))$? I think this is a pretty simple problem but I'm new to this so I'm confused.
Also, how can we show that $S = f^{-1}(f(S))$ for all subsets $S$ iff $f$ is injective?
 A: $S \subseteq f^{-1}(f(S)):$ Choose $a\in S.$ To show $a\in f^{-1}(f(S))$ it suffices to show that $\exists$ $a'\in S$ such that $a\in f^{-1}(f(a'))$ i.e. to show $\exists$ $a'\in S$ such that $f(a)=f(a').$ Now take $a=a'.$
$S = f^{-1}(f(S))$ $\forall$ $A \subset S$ $\iff f$ is injective:


*

*$\Leftarrow:$ Let $f$ be injective. Choose $s'\in f^{-1}(f(S))\implies f(s')\in f(S)\implies \exists$ $s\in S$ such that $f(s')=f(s)\implies s'=s$ (since $f$ is injective) $\implies s'\in S.$ So $f^{-1}(f(S))\subset S.$ Reverse inclusion has been proved earlier. Therefore $f^{-1}(f(S))= S.$

*$\Rightarrow:$ Let $f^{-1}(f(S))= S$  $\forall$ $A \subset S.$ Let $f(s_1)=f(s_2)$ for some $s_1,s_2\in S.$ Then $s_1\in f^{-1}(f(\{s_2\})=\{s_2\}\implies s_1=s_2\implies f$ is injective.
A: Formal proof (in DC Proof format) at http://dcproof.com/Image-Pre-Image.htm
A straightforward application of definitions except for two "sticking" points: 


*

*To prove $\neg x\in S \rightarrow \neg x\in f^{-1}(f(S))$ when $f$ is injective, you must
consider two cases: $x\in A$ and $\neg x\in A$.

*To prove $\neg\forall S\subseteq A(S=f^{-1}(f(S)))$ when $f$ is not injective, let $x\in A$ and $y\in A$ where $x\ne y$ and $f(x)=f(y)$. Then
construct counterexample $S=\{ x\}$.
A: Let $x\in S$. Then $f(x)\in f(S)$, so that $x\in f^{-1}(f(S))$.
Suppose $f$ is injective. Let $x\in f^{-1}(f(S))$. Then $f(x)\in f(S)$, so that $f(x)=f(y)$ for some $y\in S$. It follows that $x=y\in S$.
Suppose $f$ is not injective. Then $f(x)=f(y)=a$ for some $x\neq y$, so that $\{x,y\}\subset f^{-1}(f(\{x\}))$. It follows that $f^{-1}(f(\{x\}))\not\subset \{x\}$.
A: As images and inverse images are compatible with intersection and union, see here or here, this is equivalent with $\{ x \} = f^{-1}(f(x))$ for all $x \in X$ for $f : X \to Y$. Now injectivity is equivalent with $|f^{-1}(x)| \le 1$ for all $x \in X$, but as every element from $f(S)$ with $S \subseteq X$ has at least one element onto which it gets mapped by definition we have $|f^{-1}(f(x))|\ge 1$, taken together we find $|f^{-1}(f(x))| = 1$ or $f^{-1}(f(x)) = \{x\}$. Conversely if this holds, than sureley $|f^{-1}(x)|\le 1$ for every $x \in X$ as either $x \in f(X)$ or not.
