In his blog, Timothy Gowers gave the following proof:
If I'm not mistaken, he's proven that the rational numbers form a countable set by demonstrating that they can be written as the countable union of finite sets. In this case, it would be the countable union of all pre-images, right?
However, I'm having trouble following the proof. Specifically, the claim that the number of preimages of $n$ is certainly no more than $(2n + 1)^2$.
I would appreciate it if people could please take the time to clarify this.
Preimages of $n$ look like $p/q$, where $|p|+|q|=n$ and $q > 0$. This means $-n \leq q \leq n$ and $-n \leq p \leq n$, giving $(2n+1)$ choices for $p$ and $(2n+1)$ choices for $q$, for a total of $(2n+1)^2$ choices of preimage.
Of course, the number of preimages may well be less than this: it is also certainly no more than $(n+1)(2n+1)$, but the proof works exactly the same.