# Thread: Prove a function is Onto

1. ## 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:

$
g: Z \rightarrow N
$

$
g(z) = -2z$
if $z \leq 0
$

$
g(z) = 2z - 1$
if $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.

2. 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.

3. 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:

$
g: Z \rightarrow N
$

$
g(z) = -2z$
if $z \leq 0
$

$
g(z) = 2z - 1$
if $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