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.

  • $\begingroup$ Ahh okay thank you very much Samrat Makes more sense now $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.