Prove a function is onto

**kaypachu** · April 29th 2010, 06:03 PM

I need to prove:

Let f:A->B be a function. We can generate a function from P(A) to P(B) using images. Define F: P(A)->P(B) by F(S)=f(S) for each S $\in$ P(A). Under what circumstances is F onto?

I know that F is onto when f is onto, but how do I go about proving this?

**Drexel28** · April 29th 2010, 06:19 PM

Originally Posted by kaypachu

I need to prove:

Let f:A->B be a function. We can generate a function from P(A) to P(B) using images. Define F: P(A)->P(B) by F(S)=f(S) for each S $\in$ P(A). Under what circumstances is F onto?

I know that F is onto when f is onto, but how do I go about proving this?

What do you think?

For the if part this is easy.

For the only if part note that if $f$ is not surjective then $f(A)\subsetneq B$

**kaypachu** · April 29th 2010, 06:34 PM

I don't understand what you are asking. I merely have to prove "F is onto when f is onto." There are no iff statements in this proof.

**Drexel28** · April 29th 2010, 06:40 PM

Originally Posted by kaypachu

I don't understand what you are asking. I merely have to prove "F is onto when f is onto." There are no iff statements in this proof.

The "when is it true" indicates to me it's an iff.

So what part are you having trouble with particularly?

**kaypachu** · April 29th 2010, 06:44 PM

I just have to prove that F is onto using the fact that f is onto somewhere in my proof.

I'm having trouble with how to start the proof. I know the standard way to start an onto proof, but the function F is throwing me off.

I also don't know what I should make S.

**Drexel28** · April 29th 2010, 07:12 PM

Originally Posted by kaypachu

I just have to prove that F is onto using the fact that f is onto somewhere in my proof.

I'm having trouble with how to start the proof. I know the standard way to start an onto proof, but the function F is throwing me off.

I also don't know what I should make S.

So, let me start you off. To prove that $F$ is surjective you must prove that $F(\mathcal{P}(A))=\mathcal{P}(B)$ , right? But, think about it like this. Let $C\subseteq\mathcal{P}(B)$ then for each $c\in C$ there must exists some $x_c\in A$ such that $f(x_c)=c$ . So, what is significant about $\bigcup_{c\in C}\{x_c\}$ ?

**kaypachu** · April 29th 2010, 07:21 PM

I'm not really sure. I'm a little confused.

**Drexel28** · April 29th 2010, 07:40 PM

Originally Posted by kaypachu

I'm not really sure. I'm a little confused.

So, we want to prove that given a set $V$ in $\mathcal{P}(B)$ there is a set $U$ in $\mathcal{P}(A)$ such that $F(U)=V$ , right? But, think about it: this $V$ is just made up of a whole bunch of elements of $B$ . But, since $f$ is surjective each of those elements has something in $A$ which maps to them, right? So, if for each $v\in V$ we take the element $x_v\in A$ which $f(x_v)=v$ we get a set $U$ whose image under $f$ is...

**kaypachu** · April 29th 2010, 07:52 PM

I think I get where you are going with that, but I'm still a bit unsure.

The set U would be a bunch of elements in A, right?

**Drexel28** · April 29th 2010, 09:01 PM

Originally Posted by kaypachu

I think I get where you are going with that, but I'm still a bit unsure.

The set U would be a bunch of elements in A, right?

Maybe an example would be helpful.

Think about the function $f:\{1,\cdots,10\}\to\{1,2,3\}$ by $f(1)=f(2)=f(6)=f(10)=1,f(3)=f(4)=f(5)=2,f(7)=f(8)= f(9)=3$ . This is clearly surjective, right? Now, we can form a mapping $F:\mathcal{P}\left(\{1,\cdots,10\}\right)\to\mathc al{P}\left(\{1,2,3\}\right):U\mapsto f(U)$ where $f(U)=\left\{f(u):u\in U\right\}$ . So, why is this necessarily surjective? So, what I have to prove to you is that given $V\in\mathcal{P}\left(\{1,2,3\}\right)$ I can find some $U\in\mathcal{P}\left(\{1,\cdots,10\}\right)$ such that $F(U)=f(U)=V$ .

But, for example let's take $V=\{1,3\}$ . Now, I know that for each element of $V$ (namely, $1,3$ ) I can find some element of $\{1,\cdots,10\}$ that maps to it because $f$ is surjective. So, let's pick two of the elements. For example, if I pick $U=\{1,2,9\}$ then $F(U)=f(U)=\left\{f(1),f(2),f(9)\right\}=\left\{1,3 \right\}=V$ .

Now, generalize.

**kaypachu** · April 29th 2010, 09:09 PM

I think what I'm getting confused about is what to make U equal to when I move to generalized terms.

**Drexel28** · April 29th 2010, 09:11 PM

Originally Posted by kaypachu

I think what I'm getting confused about is what to make U equal to when I move to generalized terms.

So, you're going to give me some $V\in\mathcal{P}(B)$ . For each $v\in V$ there exists some $u_v\in A$ such that $f(u_v)=v$ . So, choosing $u_v$ for each $v\in V$ and making that into a set works.......right?

**kaypachu** · April 29th 2010, 09:16 PM

My professor wants me to provide a candidate (U) and show that it does what I want it to do (i.e. F(U)=f(U)=V). How do I define U?

**kaypachu** · April 29th 2010, 09:35 PM

This is probably totally wrong, but this is my first attempt at this proof:

Prove that F is onto when f is onto.

Let f be onto. Let $V \in \mathcal{P}(B)$ . For each $v \in V$ there exists some $u_{v} \in A$ such that $f(u_{v})=v$ . Let $U= \bigcup_{v \in V}{u_{v}}$ . Then $F(\bigcup_{v \in V}{u_{v}})=f(\bigcup_{v \in V}{u_{v}})=V$ .

**Drexel28** · April 29th 2010, 09:46 PM

Originally Posted by kaypachu

This is probably totally wrong,

Or so you'd think!

Except, you want $U=\bigcup_{v\in V}{\color{red}\{}u_v{\color{red}\}}$

Thread: Prove a function is onto

LinkBack

Thread Tools

Display

Prove a function is onto

Similar Math Help Forum Discussions

How to prove x^2 is a function?

Prove a function is Onto

prove function is one-to-one

Prove that f(x) is an odd function?

odd function prove

Search Tags