Proving a piece-wise defined function is bijective.

[pondzo]

Homework Statement

$f:\mathbb{Z} \to \mathbb{N}$
$f(x) = \begin{cases} 2x+2 & \text{if } x \geq 0 \\ -2x-1 & \text{if } x < 0 \end{cases}$
Prove that f is a bijection from $\mathbb{Z}$ to $\mathbb{N}$

Homework Equations

The Attempt at a Solution

Proving that it is an injection if quite simple. Proving it is a surjection is where i get confused.

Let $y\in\mathbb{N} \text{ and } x \in \mathbb{Z}$

If $x \geq 0 \text{ then } y=2x+2 ~~\Rightarrow~~ x=\frac{y-2}{2}$
if $y\geq 2 \text{ then } f(\frac{y-2}{2})=2(\frac{y-2}{2})+2=y$
if $y<2 \text{ then } f(\frac{y-2}{2})=-2(\frac{y-2}{2})-1=1-y$

If $x<0 \text{ then } y=-2x-1 ~~\Rightarrow~~ x=\frac{-(y+1)}{2}$
if $y \geq -1 \text{ then } f(\frac{-(y+1)}{2})=2(\frac{-(y+1)}{2})+2=1-y$
if $y<-1 \text{ then } f(\frac{-(y+1)}{2}) = -2(\frac{-(y+1)}{2})-1=y$

I'm pretty sure there should only be 2 or at most 4 cases that i need to investigate but i have 6. So I am clearly doing something wrong... Could someone help me out please?

 

[PeroK]

For the surjection, why not consider the cases where y is even and odd.

 

[pondzo]

For the surjection, why not consider the cases where y is even and odd.

Ahhh thank you PeroK! I'm certain i was thinking that on the bus home, and then i lost the thought and couldn't find it again. Thank you for reminding me!

Just an aside; Is my method even valid? i don't know what to make of the 1-y results.. does this matter?

 

[PeroK]

Ahhh thank you PeroK! I'm certain i was thinking that on the bus home, and then i lost the thought and couldn't find it again. Thank you for reminding me!

Just an aside; Is my method even valid? i don't know what to make of the 1-y results.. does this matter?

If I could follow your method, I'd tell you.

Normally, if you're trying to show something is a surjection onto a set Y, you would start with:

Let $y \in Y$

Then find the relevant $x \in X$

 

[pondzo]

So if I split the problem into whether y is odd or even will I end up dealing with four cases?

1. y is odd and y is less than or equal to 1
2. y is odd and y is greater than 1
3. y is even and y is greater than or equal to 2
4. y is even and y is less than 2

This is how I am thinking about it; The first two cases arise because y being odd leads to $x=\frac{1-y}{2}$ and if y <= 1 then x would be positive so i use 2x+2 but if y>1 then x is negative so i would use -2x-1. The same argument goes for the last two.

I feel somewhere in that argument i am contradicting myself and in general don't have a whole lot of confidence in the way i have done things. Could you show me how the "y is odd" argument would look?

 

[PeroK]

You don't need four cases, only two. To get you started:

Let $y \in \mathbb{N}$ be even. Then $y = 2n$ for some $n \in \mathbb{N}$

Can you take it from there?

 

[pondzo]

How does this look?

Let $y \in \mathbb{N}$ be even. Then $y=2n$ for some $n \in \mathbb{N}$
$y=2x+2 ~~\Rightarrow~~ x=\frac{y-2}{2}=\frac{2n-2}{2}=n-1$

Let $y \in \mathbb{N}$ be odd. Then $y=2n+1$ for some $n \in \mathbb{N}$
$y=-2x-1 ~~\Rightarrow~~ x=\frac{-(y+1)}{2}=\frac{-(2n+2)}{2}=-n-1$

 

[pondzo]

Thanks for all your help PeroK.

 

[PeroK]

A couple of things.

First, note that $\mathbb{N} = {1, 2, 3 ...}$. So, you need to check your definition of an odd natural number for n = 1.

Second, you're writing what I would call rough notes. These do not form a logical argument.

Third, you haven't finished the proof. You've stopped half-way through.

To take the even case a step further:

Let $y \in \mathbb{N}$ be even. Then $y = 2n$ for some $n \in \mathbb{N}$

(Now, do your rough notes off to one side, then come back with:

Let $x = n - 1$

$x \in \mathbb{Z}$ and $f(x) = 2n = y$

That is a formal proof (of the even case). Do you see the difference?

 

[pondzo]

I really appreciate the tips you are giving me! I'm just starting pure maths in uni and i need to become familiar with the procedures and formalism.

So is this a little better?

Let $y \in \mathbb{N}$ be even. Then $y=2n$ for some $n \in \mathbb{N}$
And let $x=n-1~~\text{with}~~x\in\mathbb{Z}$
$f(x)=2(n-1)+2=2n=y$

Let $y \in \mathbb{N}$ be odd. Then $y=2n+1$ for some $n \in \mathbb{N}$
And let $x=-n-1~~\text{with}~~x\in\mathbb{Z}$
$f(x)=-2(-n-1)-1=2n+1=y$

This shows that for every element of $\mathbb{N}$ there is a corresponding element of $\mathbb{Z}$ which f maps to it. Therefore f is a surjection of N onto Z.

Is the conclusion sufficient or must it be altered? Also is it a good idea to make the "rough notes" part of the proof or at least visible?

 

[pondzo]

And regarding my definition of an odd number i would change it to;

Let $y \in \mathbb{N}$ be odd. Then $y=2n-1$ for some $n \in \mathbb{N}$
And let $x=-n~~\text{with}~~x\in\mathbb{Z}$
$f(x)=-2(-n)-1=2n-1=y$

 

[PeroK]

Yes, much better.

A minor detail (I missed this too.) It's better to mention whether x is < 0 or not, so you know you're using the correct formula for f.

Let $x = -n$

$x \in \mathbb{Z}, x < 0 \ \ and \ \ f(x) = -2(-n) -1 = 2n - 1 = y$

Re notes and proofs in general. You should ask your lecturers what they expect in an exam. What I do is work out the notes to one side then decide how much (if any) needs to be mentioned in the proof for clarity and justification.

A brief recap at the end of exactly what you've shown is often worthwhile.

 

[pondzo]

If it is necessary to state the parity of x then does this mean there will be more cases I need to consider (i.e. if x<0 or x$\geq 0$)?

Also I could tighten up the conclusion by writing instead: "this shows that$~~\forall~ y~\in\mathbb{N}\exists x~\in~\mathbb{Z}:f(x)=y$ which if anyone else typeset would look more aesthetically pleasing to the eye...

 

[PeroK]

If it is necessary to state the parity of x then does this mean there will be more cases I need to consider (i.e. if x<0 or x$\geq 0$)?

No. But the sign of x tells you which formula to use. So, this justifies why you used the formula in each case.

 

[pondzo]

No. But the sign of x tells you which formula to use. So, this justifies why you used the formula in each case.

Ahh yes of course, I forgot that $n\in\mathbb{N}$ and not $n\in\mathbb{Z}$.
Thanks again for all your help PeroK.