2

I'm trying to find a surjective function $f:\mathbb{N}\to \mathbb{Q}$;

I know that at least one such function must exist since $\mathbb{Q}$ is countable, but I haven't been able to find one.

Can someone show me one such function?

Best regards,

lorenzo

lorenzo
  • 4,032

4 Answers4

12

For any positive integers $a$ and $b$, let $f(2^a3^b)=\frac{a}{b}$ and let $f(2^a5^b)=-\frac{a}{b}$. For any other natural number $n$, let $f(n)=0$.

André Nicolas
  • 507,029
  • 1
    To the OP: It is important to note that $2,3,5$ are primes. Such a method would not work if they were not. This follows from the uniqueness of prime decomposition. – K.Power Mar 09 '16 at 18:20
2

Make a grid in the upper right quadrant, and at location $(i, j)$ put the rational number $(i/j)$.

Now traverse the grid along diagonal lines where $i + j = c$, i.e. in the order

1/1
2/1  1/2
3/1  2/2 1/3
4/1  3/2  2/3  1/4
...

Eventually you will hit every number $i/j$ (in particular, it'll be in the $k$th row, where $k = i + j$.

This gives a surjective map $f$ from $\mathbb N$ to the positive rationals.

Now: split $\mathbb N$ into three groups: $0$, positive evens, and positive odds.

Send $0$ to $0$. Send $2n$ to $f(n)$. And send $2n+1$ to $-f(n)$. That defines your surjective function.

John Hughes
  • 93,729
2

Hint: First try to think about a surjective function $\mathbb{N}\to\mathbb{N}^{2}$, and then think about a surjective function $\mathbb{N}^{2}\to\mathbb{Q}^{+}$ by recalling that a positive rational number is of the form $\frac{p}{q}$ with $p,q\in\mathbb{N}$. Then finally, take a surjective function $\mathbb{Q}^{+}\to\mathbb{Q}$.

T. Eskin
  • 8,303
1

The elements of $\mathbb Q$ are quotients of two integers, so a injection can be established between $\mathbb Q$ and $\mathbb Z ^2$. Then traversing the elements of the two dimensional array $\mathbb Z ^2$ with a spiral suffices.

Henricus V.
  • 18,694