I’m having a hard time understanding this proof and I hope someone could help me.
Theorem: Let $f: A \rightarrow B$ a map. Think of this map as inducing the map $f^{*}: \mathcal{P}(B) \rightarrow \mathcal{P}(A)$. Then, $f^{*}$ is surjective if and only if $f$ is injective.
The $\Longleftarrow$ part I already prove it:
Proof: $\Longleftarrow.$ Suppose $f$ is injective. Hence, we know that $E = f^{*}(f_{*}(E))$ for all subsets $E \subseteq A$. Let $S$ be a subset of $A$. Then $S \in \mathcal{P}(A)$. We define the set $X_0$ as $X_0 = f_{*}(S)$. Observe that $X_0 \in \mathcal{P}(B)$. Hence $f^{*}(X_0) = f^{*}(f_{*}(S)) = S$. Therefore $f^{*}$ is surjective. $\square$
For the $\implies$ part, I don’t know what to do.
My attempts:
-
I tried to prove the contrapositive, so if $f$ is not injective, then $f^{*}$ is not surjective. Suppose that $f$ is not injective. Then there exists some $a,b \in A$ such that $a \neq b$ and $f(a) = f(b)$. But I don’t know what to do next.
-
I tried a direct proof: Suppose that $f^{*}$ is surjective. Hence for all $X \in \mathcal{P}(A)$, there exists some $Y \in \mathcal{P}(B)$, such that $f^{*}(Y)=X$. Since $A \subseteq A$, we have that $A \in \mathcal{P}(A)$. So there exists some $Y_0 \in \mathcal{P}(B)$ such that $f^{*}(Y_0) = A$. But, again, I don’t know where to go next.
Can someone help me? Thank you in advance!
Best Answer
Suppose $x,y$ are two distinct elements of $A$ such that $f(x)=f(y)$. Since $f^*$ is surjective there is a subset $E\subseteq B$ such that $\{x\}=f^*(E)$. Now, we have $x\in\{x\}=f^*(E)$ and hence $f(x)\in E$. Thus:
$f(y)=f(x)\in E$
But this means $y\in f^*(E)=\{x\}$, a contradiction.