2

For two sets $A,B$ there are functions - $f: A\rightarrow B$ and $g: P(B) \rightarrow P(A)$ such that $D$ belongs to $P(B)$ and $g(D)=f^{-1}[D]$.

I need to prove that $f$ is surjective if and only if $g$ is injective.

It is my first ever semester so I'm still learning these basics.

I did the first part like so: Assume $f$ is surjective, I'll show that $g$ is injective. Let $D_1,D_2$ be in $P(B)$ such that $g(D_1)=g(D_2)$, I'll show that $D_1=D_2$.

From the question it's clear that $f^{-1}[D_1]=f^{-1}[D_2]$

Because it's surjective then $f(f^{-1}[D_1]) = f(f^{-1}[D_2]) \Rightarrow D_1=D_2$. So I proved that it's injective.

Now the second part is to prove that if $g$ is injective then $f$ is surjective. And I probably didn't even begin right so I would love to have a direction from you guys. I know that I either assume that $g$ is injective and prove that $f$ is surjective or show that if $f$ is not surjective then $g$ is not injective. And in both cases I'm stuck.

Would appreciate your help/guidance. Thank you!

Bernard
  • 175,478
Dan
  • 21
  • 2
    The word is "surjective". – lulu Jul 28 '20 at 12:33
  • To your argument: perhaps it helps to note that if $b\in B$ is not in the image of $f$ then $g({b})=f^{-1}(b)=\emptyset$. As $g(\emptyset)=\emptyset$ we easily see that $g$ can't then be injective. – lulu Jul 28 '20 at 12:34
  • A little bit of a noob questions but how can we see from g(\emptyset)=\emptyset that g can't be injective? How does it prove it? Thank you so much! – Dan Jul 28 '20 at 13:11
  • 1
    In my comment, I found two distinct sets both of which are mapped by $g$ to $\emptyset$. Specifically, $g({b})=\emptyset$ AND $g(\emptyset)=\emptyset$. That's what shows that $g$ is not injective. – lulu Jul 28 '20 at 13:25
  • I see, thank you so much! Do you have a tip as to how I could have gotten to this answer? Is there any rule of thumb I should always look for or any thought pattern to go through? Or is it just pure exercising? – Dan Jul 28 '20 at 13:36
  • To show that a function is not injective you really need to show that there are two different things which get mapped to the same thing. Since, here, all you know is that $f$ is not surjective, it seems natural to consider a point missed by $f$. – lulu Jul 28 '20 at 13:42

0 Answers0