# 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?

-
How do you prove that one set is a subset of another set? –  Code-Guru Dec 18 '12 at 3:16

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\}$.

-
Okay I should have known that. How would I show that $S=f^-1(f(S))$ iff $f$ is one-to-one? –  GAtechWizard Dec 18 '12 at 3:22
This shows that $S=f^−1(f(S))$ if $f$ is injective but not that $f$ is injective if $S=f^−1(f(S))$. I know you begin by supposing that $f(x) = f(y)$ for some $x,y \in S$ but how do you go about showing that $x = y$? –  GAtechWizard Dec 19 '12 at 1:45

Formal proof (in DC Proof format) at http://dcproof.com/Image-Pre-Image.htm

A straightforward application of definitions except for two "sticking" points:

1. 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$.

2. 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\}$.

-
$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.