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.