# Prove a function is Onto

• Apr 6th 2010, 08:23 PM
Alterah
Prove a function is Onto
Hello, I am having a problem with a certain function which is supposed to be one-to-one and onto. The function is:

$\displaystyle g: Z \rightarrow N$
$\displaystyle g(z) = -2z$ if $\displaystyle z \leq 0$
$\displaystyle g(z) = 2z - 1$ if $\displaystyle z > 0$

My approach is to tackle this by looking at each piece and trying to prove that each piece is one-to-one and onto. For the first part where z is less than or equal to 0, the one-to-one proof was straightforward. But proving it is onto seems straightforward, but I keep concluding it is NOT onto.

We've done the following in most of the onto proofs I have seen:

let g(z) = y
then:
-2z = y
z = -(y/2).

Because this isn't necessarily an integer (or part of the domain) I should conclude that it isn't onto, but the book says it is. Am I approaching the problem correctly? Or am I missing something? Thanks!

Edit: Nevermind, I see my problem. In this case y is defined as a natural number, but for this portion, y is also even. Thus, when I divide y by 2 in that last step, it will always be an integer.
• Apr 7th 2010, 06:57 AM
MoeBlee
Quote:

Originally Posted by Alterah
My approach is to tackle this by looking at each piece and trying to prove that each piece is one-to-one and onto.

Just to be clear, I think you mean that you want to show that the first piece is 1-1 and onto the even naturals and that the second piece is 1-1 and onto the odd naturals.
• Apr 7th 2010, 08:01 AM
xalk
Quote:

Originally Posted by Alterah
Hello, I am having a problem with a certain function which is supposed to be one-to-one and onto. The function is:

$\displaystyle g: Z \rightarrow N$
$\displaystyle g(z) = -2z$ if $\displaystyle z \leq 0$
$\displaystyle g(z) = 2z - 1$ if $\displaystyle z > 0$

My approach is to tackle this by looking at each piece and trying to prove that each piece is one-to-one and onto. For the first part where z is less than or equal to 0, the one-to-one proof was straightforward. But proving it is onto seems straightforward, but I keep concluding it is NOT onto.

We've done the following in most of the onto proofs I have seen:

let g(z) = y
then:
-2z = y
z = -(y/2).

Because this isn't necessarily an integer (or part of the domain) I should conclude that it isn't onto, but the book says it is. Am I approaching the problem correctly? Or am I missing something? Thanks!

Edit: Nevermind, I see my problem. In this case y is defined as a natural number, but for this portion, y is also even. Thus, when I divide y by 2 in that last step, it will always be an integer.

By definition g(z) is onto iff:

for all ,n : nεN ,there exists an integer z such that g(z) = n

But if nεN n is even or odd i.e n=2k ,where k is an integer ,or n is odd i.e n=2k+1 ,where k is an integer.

in the case n=2k ,use the 1st equation ;g(z) = -2z,and if -2z =2k => z= -k

thus g(-k) =-2(-k) = 2k =n .

So the integer z such that g(z) = n ,is -k

In the case n= 2k+1 ,use the 2nd equation : g(z) = 2z-1.and if 2z-1 = 2k+1 => z= k+1.

Thus g(k+1) = 2(k+1) -1 = 2k+1 = n.

So the integer ,z such that g(z) = n is k+1