How show $\mathbb N \cong \mathbb Q$ using Cantor pairing? According to this:
http://en.wikipedia.org/wiki/Cantor_pairing_function#Cantor_pairing_function,
we can show that $\mathbb N\times\mathbb N\cong\mathbb N$. But as for $\mathbb Q$, this is not the exact same case since not all numerators and denominators are coprime, the above algorithm can't give bijection. How to modify it to make a bijection? thanks.

Take the function $f:\mathbb N\to \mathbb N\times\mathbb N$ defined as $f(n)=(f_1(n),f_2(n))$.
Now define $g(n)$ "step by step". First, define
$$g(1)=1$$
Then, for $n>1$, define $g(n)$ as the first element of $$\left\{\frac{f_1(n)}{f_2(n)},\frac{f_1(n+1)}{f_2(n+1)},\frac{f_1(n+2)}{f_2(n+2)},\dots,\right\}$$
which is not in the set $\{g(1),g(2),\dots,g(n)\}$.
