1
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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}$. $\endgroup$ – fgp Apr 11 '14 at 14:03
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.