Is there a bijective function mapping Natural numbers to Natural numbers, other than $f(n) = n$?

Is there a function that can be bijective, with the set of natural numbers as domain and range, other than $f(n) = n$?

• Yes, there are $2^{\aleph_0}$ such functions. – Hanul Jeon Aug 25 '16 at 15:56
• To give an explicit example, consider $f(0):=1$, $f(1):=0$ and $f(n)=n$ for $n\ge 2$. – Hanul Jeon Aug 25 '16 at 15:57
• An easy way to construct such functions: permute the first $n$ natural numbers and then let $f(m)=m$ for $m \ge n+1$. – User8128 Aug 25 '16 at 15:58
• @crvo84: related on MO mathoverflow.net/questions/27785 – Watson Aug 25 '16 at 16:14

There are uncountably many of such maps.

In fact, let $A$ be any subset of $\Bbb N=\{1,2,3,\ldots\}$ such that both $A$ and $\Bbb N\setminus A$ are infinite (for example, $A$ could be the set of primes or the set of perfect squares). Then we can define $a(n):=$ $n$th smallest element of $A$, $b(n):=$ $n$th smallest element of $\Bbb N\setminus A$, and $$f(n)=\begin{cases}a(\tfrac n2)&\text{if n is even}\\b(\tfrac{n+1}2)&\text{if n odd}\end{cases}$$ Different $A$ will give different $f$, hence there are at leadt as many $f$ as there are $A$ - and that's continuum-many.

Sure. Consider the function $f: \Bbb N \to \Bbb N$ defined by

$$f(n) = \cases{ n - 1 & if n is even \\ n + 1 & if n is odd.}$$

This function is a non-identity bijection. As Hagen von Eitzen notes, depending on your definition of $\Bbb N$, swap $+$ and $-$ in the definition of $f$ if $\Bbb N = \{0, 1, 2, 3, \ldots\}$.

• Note that $f(0)=-1$. – SchrodingersCat Aug 25 '16 at 16:02
• @SchrodingersCat This method works if $\Bbb N=\{1,2,3,\ldots\}$. For $\Bbb N=\{0,1,2,\ldots\}$ swap $+$ and $-$. – Hagen von Eitzen Aug 25 '16 at 16:03
• @SchrodingersCat, depending on your definition of the naturals, this is a valid bijection. In particular, $\Bbb N$ does not have to contain $0$, and this is largely a matter of convention, anyway. – Alex Ortiz Aug 25 '16 at 16:03
• @AOrtiz You should mention that. What you consider N to be. Or better, as Hagen says, add the alternative. – SchrodingersCat Aug 25 '16 at 16:05
• @SchrodingersCat, done. Thanks for the advice. It is always best to be explicit with these things. – Alex Ortiz Aug 25 '16 at 16:07