# Show that the function $f: N \to N$ given by ..

Show that the function $f:N \to N$ given by $$f(x)= \begin{cases} x+1 & \text{If x is odd} \\ x-1 & \text{If x is even} \end{cases}$$ is bijective.

My Attempt:

Case$1$. Suppose $x_1$ is odd and $x_2$ is even. $$f(x_1)=f(x_2)$$ $$x_1 + 1= x_2 -1$$ $$x_2 - x_1=2$$ This is impossible. So, our assumption is invalid.

Case$2$. Suppose $x_1$ and $x_2$ are even. $$f(x_1)=f(x_2)$$ $$x_1 - 1= x_2 -1$$ $$x_1=x_2$$

Case$3$. Supppse $x_1$ and $x_2$ are odd $$f(x_1)=f(x_2)$$ $$x_1+1=x_2+1$$ $$x_1=x_2$$.

• Hint: Compute $f(f(x))$ – Hagen von Eitzen Mar 31 '17 at 10:03
• I think $\mathbb{N}$ is usually taken to be $\{0,1,...\}$ these days, rather than $\{1,2,...\}$. Where does $0$ go? – Martin Rattigan Mar 31 '17 at 10:10
• @HagenvonEitzen, what does it help for? – pi-π Mar 31 '17 at 10:10
• @MartinRattigan, what is $N$? – pi-π Mar 31 '17 at 10:11
• You have successfully shown that $f$ is injective, or one-to-one. Now you need to show that it is surjective / onto, and you're done. – Arthur Mar 31 '17 at 10:13

• By definition, $f$ is injective when

$$f(x_1)=f(x_2)\to x_1=x_2$$

So, taking $f(x_1)=f(x_2)$ we have the possibilities:

$1)$ If $x_1,x_2$ are odd then, $x_1+1=x_2+1\to x_1=x_2$

$2)$ If $x_1,x_2$ are even then, $x_1-1=x_2-1\to x_1=x_2$

$3)$ If $x_1$ is odd and $x_2$ is even then $x_1+1=x_2-1\to x_1-x_2=-2$, what is impossible.

Then just the case $(1)$ and $(2)$ can be true and we get that $f$ is injective.

• Now we have to prove that $f$ is surjective. By definition, $f$ is surjective if $\text{Image}(f)=\Bbb N$.

Let's then take some $y_0\in \Bbb N$ and we must to prove that there is some $x_0$ in the domain, which is $\Bbb N$ such that $f(x_0)=y_0$.

$1)$ If $y_0$ is odd then take $x_0=y_0+1$, which will be even, and then we will get $f(x_0)=x_0-1=y_0+1-1=y_0$;

$2)$ If $y_0$ is even then take $x_0=y_0-1$, which will be odd, and then we will get $f(x_0)=x_0+1=y_0-1+1=y_0$;

So $f$ is surjective.

• Can the third possibility be $x_1$ and $x_2$ both are even? – pi-π Mar 31 '17 at 13:19
• @LeonhardEuler: Sure! I forgot that! I'll update. But it doesn't change the solution. – Arnaldo Mar 31 '17 at 13:21
• I am.not getting the second part of the solution (i.e the proof that the function is surjective). Could you please elaborate? How are we supposed to approach such proofs? – pi-π Mar 31 '17 at 13:24

Note that a function $g: X \to Y$ is bijective if and only if it is injective and surjective, if and only if for every $y \in Y$ there is exactly one $x \in X$ such that $g(x) = y$. Let $y \in \mathbb{N}$. Then $y$ is either odd or even. If $y$ is odd, then $y+1 \in \mathbb{N}$ and is even; note that $x := (y+1)$ implies $f(x) = (y+1)-1 = y$. If there is some $x' \neq x$ such that $x' \in \mathbb{N}$ and $f(x') = f(x) = y$, then $x'$ even implies $x' - 1 = y$ and $x'$ odd implies $x'+1$ is even; both leads to a contradiction. Now you can use the same argument to argue for the case where $y$ is even.

A bijection is an injection and a surjection. You have shown that this is an injection (although, depending on the level of your course, it might help to add an extra word about why your first case is "impossible"). All that remains now is to show that the function is also a surjection, i.e., that for every $n \in \mathbb{N}$ there is some $k \in \mathbb{N}$ such that $f(k) = n$.