3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ $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 \}$). $\endgroup$ – Newbie Aug 27 '15 at 14:28
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kamil Aug 27 '15 at 14:54
  • $\begingroup$ 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). $\endgroup$ – user178826 Aug 27 '15 at 15:01
2
$\begingroup$

Take $B=f(A)$. Since $f$ is injective, we have $$f^{-1}\bigl(f(A)\bigr)=A.$$

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