Onto function with domain of rational numbers and co-domain of natural numbers

1.1k Views Asked by At

I'm trying to find an onto function $f: \mathbb{Q} \to\mathbb{N}$

I'm somewhere along the lines of $f(q) = |(1 - q)| + q$ for non integers, but I'm not sure where to go from there.

2

There are 2 best solutions below

0
On BEST ANSWER

Thanks to the help of the users commenting on the question, I understand the problem. $f$($m$/$n$)=|$m$|+1 is an onto function, as long as $m$/$n$ is in reduced form.

8
On

This is the classical example to show that the rationals are countable and that defines a bijection from $\mathbb{Q}$ to $\mathbb{N}$:

enter image description here

You proceed taking $f(1/1)=0$ and then enumerate the fractions you encounter on the path described by the arrows, skipping the ones you have already considered previously.