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

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?

Solution 1:

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

Solution 2:

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$