# Need a hint proving that f is bijective

Regard 0 (zero) as an even number and define f : N → N by

f(n) = \begin{cases} n + 1, & \text{if $n$ is even} \\ n -1, & \text{if $n$ is odd} \end{cases}

Prove that f is bijective

My solution:

(1) show that the function is injective:

f(n1)= f(y1)

n + 1 = y + 1

n = y

f(n2) = f(f2)

n - 1 = y - 1

n = y

Both functions n1 and n2 are injective

(2)Show that f is surjective:

function 1:

y = n1 + 1

y -1 = n1

function 2:

y = n2 -1

y -1 = n2

Is it correct till now? I am not sure about the next step Thank you.

No, it is not correct. If you define a function f by cases: $$f(x) = \begin{cases} f_1(x) & \text{if x \in A_1}\\ f_2(x) & \text{if x \in A_2} \end{cases}$$ it can happen that both $f_1$ and $f_2$ are bijective but $f$ is not.

Instead you should use the definition and consider all the possible cases.

Your writing seems to be incorrect.

Simply see that if $f(n)=f(m)$, then $n,m$ have to be either both odd or both even, otherwise, $|n-m|=2$ which will be a contradiction. So, if both of $n,m$ are even or odd, then from the formula, $f(n)=f(m)\implies n=m$. This proves injectivity.

For the surjectivity, note that $m=f(n)\implies m$ can be either $n-1$ or $n+1$ depending upon whether $m$ is even or odd. This proves surjectivity.

• Ahh okay thank you very much Samrat Makes more sense now – question Sep 11 '15 at 8:03

Denote $$E$$ the set of even natural numbers, and $$O$$ the set of odd natural numbers. Observe first that $$f(E)\subset O$$ and $$f(O)\subset E$$. Hence, if $$f(m)=f(n)$$, $$m$$ and $$n$$ are both even or both odd. As a consequence, if $$f(m)=f(n)$$, $$m=n$$, which proves $$f$$ is injective.

$$f$$ is surjective: let $$n\in \mathbf N$$. If $$n$$ is even, $$n+1$$ is odd, and $$f(n+1)=n$$.If $$n$$ is odd, $$n-1$$ is an even natural number and again $$f(n-1)=n$$.

Shorter proof:

If $$n$$ is even, $$f(f(n))=f(n+1)=n$$ since $$n+1$$ is odd. If $$n$$ is odd, $$f(f(n))=f(n-1)=n$$ since $$n-1$$ is even.

Hence $$\color{red}f\circ \color{blue}f=\operatorname{id}_\mathbf N$$, which proves $$\color{blue}f$$ is injective and $$\color{red}f$$ is surjective, hence $$f$$ is bijective.