Math Is Fun Forum

ziabing

Member

Registered: 2021-09-18

Posts: 6

Proving that a function is surjective

Hello,

How can I prove that the following function is surjective?

f : N → Z such that :
f(x) = x/2 if x is even
f(x) = -(x+1)/2 if x is odd

Many thanks!

zetafunc

Moderator

Registered: 2014-05-21

Posts: 2,436

Website

Re: Proving that a function is surjective

Hi ziabing,

Welcome to the forum. I will assume here the natural numbers include 0 -- otherwise there is no

for which

To show that this function is surjective, you need to show that every element

can be 'hit' by some

under your function

. So first consider the case where

. Can you always find an

such that

?

Yes, because we can just take

in which case -- because

must be even --

And since

then it's clear that

and so it must be that

That takes care of the positive integers (and 0) in

-- now you just need to do the same for the negative integers in

and you're done. So let's consider the case where

So, given

can you find an

such that we'll always have

?

I will leave you to finish this off -- but please do post back if you need more help.

ziabing

Member

Registered: 2021-09-18

Posts: 6

Re: Proving that a function is surjective

Thanks so much!