4
$\begingroup$

Let $f:A\rightarrow B$ be a function, $C\subseteq A$, $D\subseteq B$ then prove:

  • $C = f^{-1}(f(C)) \iff f$ is injective
  • $f(f^{-1}(D) = D \iff f$ is surjective

For both equivalences, I have difficulties proving the right implications (proving that $f$ is injective for the first equivalence and proving that $f$ is surjective for the second).

I found a proof of the second right implication (proving that $f$ is surjective) that I can't understand. The proof is as follows:

"Let $y\in D$, consider the set $D=\{y\}$. Then $f(f^{-1}(\{y\}))=\{y\}$ wich implies $y\in f(f^{-1}(\{y\}))$, this is, $y=f(x)$ for an element $x\in f^{-1}(\{y\})\subseteq A$. This proves that $f$ is surjective."

Would appreciate an explanation of this last proof, helpful hints or proofs of these implications. Thank you beforehand.

For the left implications I proved the equalitiess by proving that $P\subseteq Q$ and $Q\subseteq P$ (then $P=Q$). There are 2 inclusions that do not need $f$ to be injective or surjective where I have no difficulties proving:

  • $C \subseteq f^{-1}(f(C))$
  • $f(f^{-1}(D) \subseteq D$

This means the other 2 inclusions must use the premise of $f$ being injective or surjective. I have proved successfully that $f(f^{-1}(D) \supseteq D$ using the that $f$ is surjective. But when proving $C \supseteq f^{-1}(f(C))$ I didn't use the $f$ is injective so something must be wrong. Proof is as follows:

Let $a\in f^{-1}(f(C))$

$\implies f(a) \in f(C)$

$\implies \exists a\in C: f(a)=b$

Where must I use the premise of $f$ being injective?

$\endgroup$
3
$\begingroup$

For the first question:

It is to be shown that every $y \in B$ is given by $f(x)$ for some $x\in A$. It is given that $f(f^{-1}(D))=D \quad \forall D\subseteq B$. The proof you mention chooses the singleton $\{y\}$ as the subset $D$ and proceeds to show that $y$ is indeed $f(x)$ for some $x \in A$.

For the second question:

You have $f(a)\in f(C) \Rightarrow f(a)=f(c)$ for some $c\in C$. But $f$ injective $\Rightarrow a=c$

$\endgroup$
  • $\begingroup$ I now understand the proof, thank you. Regarding the injectivity of $f$, I understand what you said but not why is necessary for the proof. We need to show that for $a\in f^{-1}(f(C)) \implies a\in C$. My first thought was that there could be more inverse images for $f(a)$ but, by injectivity, there will only be one, in this case, $a$. Pardon if this is easy to understand and I'm struggling with it. $\endgroup$ – AndreGSalazar Dec 16 '13 at 5:25
  • 1
    $\begingroup$ Consider this counter example. Let $A=B=\mathbb R$ and $f(x)=x^{2}$ Clearly $f$ is not injective. Let $C=\{1\}$. Then $f(C)=\{1\}$, but $f^{-1}(f(C))=\{-1,1\}\neq C$. So injectivity is required. It is necessary for the proof for $f(a)=f(b)\Rightarrow a=b \forall a,b \in A$ if only if f is injective. $\endgroup$ – Arundhathi Dec 16 '13 at 5:44
1
$\begingroup$

Just for the sake of completeness, I'm going to post a full and detailed answer.

Let $f: A \to B$ be a map without any further assumption.Then

$$i-) \quad C \subseteq A \Rightarrow C \subseteq f^{-1}(f(C))$$

$$ii-) \quad C \subseteq A \quad \wedge \quad \text{f is injective }\Rightarrow C = f^{-1}(f(C))$$

Proof:

$i-)$

Let $c \in C$. then $$f(c) \in f(C),$$ and by the definition of $f^{-1} (T) = \{ a \in A | f(a) \in T\}$, we get

$$f(c) \in f(C) \Rightarrow c \in f^{-1}(f(C)).$$

$ii-)$

Let $a \in f^{-1}f(C)$. Then by our assumption, $\exists b \in f(C)$ such that $$b=f(a).$$ Now, $b \in f(C)$ does not directly imply that $a\in C$ unless $f$ is injective because there might be other element outside of $C$ whose image under $f$ is in the image set of $C$ under $f$, i.e there might be two element in the domain one is in $C$, and one is not whose images are the same.Therefore, if $f$ is injective, we know that there is only one element whose image is $b$, hence by its definition is should be in $C$, hence $$a \in C.$$


$$iii-) \quad D \subseteq B \rightarrow f(f^{-1}(D)) \subseteq D$$

$$iv-) \quad D \subseteq B \wedge \text{f is surjective}\rightarrow f(f^{-1}(D)) = D$$

Proof:

$iii-)$

Let $b \in f(f^{-1}(D))$. Then $\exists a \in f^{-1}(D)$ such that $$b=f(a).$$ Now, $a \in f^{-1}(D)$ implies that $$f(a) \in D \Rightarrow b = f(a) \in D.$$

$iv-)$

Let $d \in D$. Now If $f$ is not surjective, we cannot say that $d$ in the image set of the domain, hence we cannot conclude anything from that.Now since the fact that $f$ is surjective is given, by our assumptions, $\exists a \in f^{-1}(D)$ such that $$f(a) = d.$$ Hence from its definition, $$d = f(a) \in f(f^{-1}(D)).$$

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