Can someone help me understand how to do this problem?

Let F:N -> {0,1} be defined by F(n)= 0 if 3|n or 1 if 3|n

a)Show F is NOT one-to-one.

b)Show F is onto.

Printable View

- Apr 10th 2010, 12:11 PMmatthayzon89Showing a function is one-to-one or onto.
Can someone help me understand how to do this problem?

Let F:N -> {0,1} be defined by F(n)= 0 if 3|n or 1 if 3|n

a)Show F is NOT one-to-one.

b)Show F is onto. - Apr 11th 2010, 02:11 AMtonio
- Apr 12th 2010, 12:36 PMmatthayzon89
- Apr 12th 2010, 12:44 PMPlato
- Apr 12th 2010, 12:44 PMMath Major
Sorry, but what are you using | to mean?

- Apr 12th 2010, 02:37 PMmatthayzon89
- Apr 12th 2010, 03:08 PMPlato
- Apr 12th 2010, 03:10 PMmatthayzon89
So b) is ONTO.

p.S

I need help trying to understand the question and knowing what to look for.... I don't really need help solving it. Hints don't help much either.

Can someone please explain how to approach such a problem and what I need to look for in order to prove something is onto or one-to-one? - Apr 12th 2010, 03:26 PMPlato
- Apr 13th 2010, 07:58 AMmatthayzon89
So I know the answer b/c I went over it with my prof. but I still dont really understand it, can someone please explain?

Here it is:

F:N -> {0,1}

F(n)= {0 if 3 does not |n, 1 if 3|n)

a) is NOT one-to-one <- I know this is due to having more then one value mapped to the same second value, but I dont understand how this conclusion is figured out given the information of the problem.

Proof:

Consider n(base1)= 1 and n(base2)= 2

Then F(n(base1)=F(n(base2))=0 but n(base1)DOES NOT EQUAL 2.

Also,

Is F onto? YES

Proof:

Let y E {0,1}

if y=0,choose n=1 then, n E N and F(n)=y since F(1)=0

If y=1, choose n-3 then, n E N and F(n)=y since F(3)=1.

Can someone please explain how this proof was reached and the logic behind whats going on in detail so i understand it once and for all?

Thank You in advance,

Matt H