This question already has an answer here:

A question regarding a bijection between $\mathbb N^2$ and $\mathbb N$. I know about cantor pairing function but I wanted to ask about a bijection I have seen around the site which is $n=2^{u-1}(2v-1)$.

Can anyone explain why is this bijection surjective (I understand how it's injective) as it seems to give only values of $\mathbb N_{even}$ (power of 2 which is even times an odd number).

Thank you


marked as duplicate by Guy Fsone, Asaf Karagila elementary-set-theory Feb 6 '18 at 11:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ If $u=1$ then $2^{u-1}=2^0=1$ and you get an odd number! $\endgroup$ – user491874 Feb 6 '18 at 11:48

It is surjective because if $n\in\mathbb N$ and you write $n$ as $2^ab$, with $a\in\mathbb{Z}_+$ and $b$ and odd natural, then the function that have in mind maps $\left(a+1,\frac{b+1}2\right)$ into $2^ab=n$.

  • $\begingroup$ But how can n be odd? $\endgroup$ – Galush Balush Feb 6 '18 at 11:53
  • 1
    $\begingroup$ @GalushBalush When $a=0$. $\endgroup$ – José Carlos Santos Feb 6 '18 at 11:53

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