# 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.

• Introduce a "height" of a rational number $q/p$ as $q+p$ and after arrange all possible rationals according to the height. – Artem Apr 11 '14 at 13:20

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...

• To get a surjection onto $\mathbb{Q}$, just use $\mathbb{N} \to \mathbb{N}\times\mathbb{N}$ twice to get a surjection $\mathbb{N}\to\mathbb{N}\times\mathbb{N}\times\mathbb{N}$, and then use $(k,m,n) \mapsto (-1)^k\frac{m}{n}$ as a surjection $\mathbb{N}\times\mathbb{N}\times\mathbb{N} \to \mathbb{Q}$. – fgp Apr 11 '14 at 14:03

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