16
$\begingroup$

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?

  • 2
    How do you prove that one set is a subset of another set?2012-12-18

4 Answers 4

12

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

  • 0
    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$?2012-12-19
2

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

0

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

0

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.