1
$\begingroup$

I was trying to construct an explicit bijection $f:\mathbb{N} \to \mathbb{Q}^+$, but unable to do so. I google it , & found a solution here in Stackexchange, which given below -

Let us first define Stern's diatomic series.

$a_1=1,a_{2k}=a_k,a_{2k+1}=a_k+a_{k+1}$

Let us list out the first few terms.

$a_1=1$

$a_2=a_1=1$

$a_3=a_1+a_2=1+1=2$

$a_4=a_2=1$

$a_5=a_2+a_3=1+2=3$

$a_6=a_3=2$

$a_7=a_3+a_4=2+1=3$

$a_8=a_4=1$

Now to obtain the nth rational number, we define $f:\mathbb{N} \to \mathbb{Q}^+$, by $f(n)={a_n\over a_{n+1}}$.

Let us list out the first few terms.

$f(1)={a_1\over a_{1+1}}={1\over 1}$

$f(2)={a_2\over a_{2+1}}={1\over 2}$

$f(3)={a_3\over a_{3+1}}={2\over 1}$

$f(4)={a_4\over a_{4+1}}={1\over3}$

$f(5)={a_5\over a_{5+1}}={3\over2}$

$f(6)={a_6\over a_{6+1}}={2\over3}$

$f(7)={a_7\over a_{7+1}}={3\over1}$

etc.

Using this concept I have proved the injection of the function $f$. But when I'm trying to prove surjection by choosing an arbitrary $q\in \mathbb{Q}^+$, I'm unable to find the preimage in $\mathbb{N}$.

Please show me the proper way to proof the surjection rigorously.

$\endgroup$
1
$\begingroup$

An easier bijection:

If you have an explicit bijection $g:\mathbb N_0\to\mathbb Z$ such that $g(0)=0$, then you can use the Fundamental Theorem of Arithmetic, and then map $$ \begin{align} 0 &\mapsto 0 \\ \pm 2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}\cdots p_n^{\alpha_n}\cdots &\mapsto \pm 2^{g(\alpha_1)}3^{g(\alpha_2)}5^{g(\alpha_3)}\cdots p_n^{g(\alpha_n)}\cdots \end{align} $$


The particular function you're defining in the body of the question is known as the Calkin-Wilf sequence. To prove that it is a bijection, what you need to show is that every positive rational appears exactly once in the Calkin-Wilf tree.

This is pretty easy to do by long induction on $p+q$ where $p/q$ is in lowest terms -- namely, for every $p/q$ there is only one possible label for its parent node, and you can then appeal to the induction hypothesis for the fact that this parent label appears exactly once.

Discovering where to find a given rational in the tree closely tracks using Euclid's algorithm (with successive subtractions rather than divisions) to verify that the $p/q$ you started out with is indeed in lowest terms.

$\endgroup$
  • $\begingroup$ I don't think this quite answers the question in the body - the OP is asking about how to show that a specific map is a bijection (although of course this does address the title question). $\endgroup$ – Noah Schweber Nov 18 '16 at 16:19
  • $\begingroup$ @NoahSchweber: I have edited with a hint for that particular function. $\endgroup$ – Henning Makholm Nov 18 '16 at 16:34

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.