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?

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

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

$\endgroup$
  • $\begingroup$ Okay I should have known that. How would I show that $S=f^-1(f(S))$ iff $f$ is one-to-one? $\endgroup$ – GAtechWizard Dec 18 '12 at 3:22
  • $\begingroup$ 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$? $\endgroup$ – GAtechWizard Dec 19 '12 at 1:45
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.