# Proving a function $F$ is surjective if and only if $f$ is injective

Problem: Let $X$ and $Y$ be non-empty sets and let $f: X \rightarrow Y$ be a function. Then we can define $F: P(Y) \rightarrow P(X)$ by \begin{align*} F(B) = f^{-1}(B) \qquad \text{for all} \ B \in P(Y). \end{align*} Prove that $F$ is surjective if and only $f$ is injective.

(Here, $f^{-1}(B)$ denotes the inverse image, and $P(X), P(Y)$ are power sets.)

Attempt at proof: I think I proved one implication already, though I'm not sure if every step in my reasoning is correct. This is what I did:

First, suppose that $F$ is surjective. Let $x_1, x_2 \in X$ and suppose that $f(x_1) = f(x_2)$. Let $A_1 = \left\{x_1\right\}$ and $A_2 = \left\{x_2 \right\}$, so that $A_1, A_2 \in P(X)$. Because $F$ is surjective, there exist $B_1, B_2 \in P(Y)$ such that $F(B_1) = A_1$ and $F(B_2) = A_2$. From the assumption that $f(x_1) = f(x_2)$, we have also that $f(A_1) = f(A_2)$. Thus by definition of $F$ we have: \begin{align*} F(B_1) = A_1 = f^{-1}(B_1) \qquad \text{and} \qquad F(B_2) = A_2 = f^{-1}(B_2). \end{align*} From this it follows that $f(A_1) = B_1$ and $f(A_2) = B_2$ (is this step correct?). Hence $B_1 = B_2$. So we get \begin{align*} F(B_1) = A_1 = F(B_2) = A_2 \end{align*} and so $A_1 = A_2$. Thus $x_1 = x_2$ and $f$ is injective.

Now, the converse I find pretty hard. Suppose $f$ is injective, and let $A \in P(X)$. Then we have to prove that there exists a $B \in P(Y)$ such that $F(B) = A$. By definition of $F$ we have $F(B) = f^{-1}(B)$. Now, since $f$ is injective, the inverse image of $B$ exists of at most one element. But I cannot conclude that it is non-empty since $f$ may not be surjective. So I'm not sure what to do with $f^{-1}(B)$ in this case, and how to find $B$ such that $F(B) = A$.

Help with this part would be appreciated. And also, was my reasoning in the first part correct?

• $f^{-1} (B) = A \Rightarrow f(A) = B$ is not always true - e.g. if $f : X \rightarrow Y$ is a constant, $f \equiv c$, then for any $B \ni c$ one has $f^{-1} (B) = X$ however obviously $f (X) = \{ c \} \neq B$ (unless $B = \{ c \}$). – Newbie Aug 27 '15 at 14:28

For the second part, you need to show that there is $B\in P(Y)$, such that $F(B)=A$. What about $B:=f(A)$?
As for the first part, it is correct in this case (Why?). However, in not always we have that $A=f^{-1}(B)$ implies $f(A)=B$.
• I see, thanks. So why can I conclude in this case that $A = f^{-1}(B)$ implies $f(A) = B$? We know nothing about $f$ ? We only know that $F$ is surjective. – Kamil Aug 27 '15 at 14:54
• Because in this case $A$ is a singleton, hence $f^{-1}(B)$ too. In others words, $f:f^{-1}(B)\rightarrow B$ is surjective (moreover bijective). – user178826 Aug 27 '15 at 15:01
Take $B=f(A)$. Since $f$ is injective, we have $$f^{-1}\bigl(f(A)\bigr)=A.$$