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.

If you don't care about a constructive bijection:
There is a clear injection from $\mathbb{N} \to \mathbb{Q}_+$. If we can show that there is a surjection $\mathbb{N} \to \mathbb{Q}_+$, then this shows (Cantor-Bernstein) that they have the same cardinality.
To construct our surjection, we note that there is a surjection $\mathbb{N} \times \mathbb{N} \to \mathbb{Q}_+$. So compose the maps
$$
\mathbb{N} \to \mathbb{N} \times \mathbb{N} \to \mathbb{Q}_+
$$
which gives us our answer. At least, for positive rationals...
