3
$\begingroup$

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

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

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.

$\endgroup$
5
$\begingroup$

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\}$.

$\endgroup$
  • 1
    $\begingroup$ Note that $f(0)=-1$. $\endgroup$ – SchrodingersCat Aug 25 '16 at 16:02
  • $\begingroup$ @SchrodingersCat This method works if $\Bbb N=\{1,2,3,\ldots\}$. For $\Bbb N=\{0,1,2,\ldots\}$ swap $+$ and $-$. $\endgroup$ – Hagen von Eitzen Aug 25 '16 at 16:03
  • $\begingroup$ @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. $\endgroup$ – Alex Ortiz Aug 25 '16 at 16:03
  • 1
    $\begingroup$ @AOrtiz You should mention that. What you consider N to be. Or better, as Hagen says, add the alternative. $\endgroup$ – SchrodingersCat Aug 25 '16 at 16:05
  • $\begingroup$ @SchrodingersCat, done. Thanks for the advice. It is always best to be explicit with these things. $\endgroup$ – Alex Ortiz Aug 25 '16 at 16:07

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.