Proof that the set of rationals is countable with finite preimages?

Question

I'm working through the proof that the set of Rational numbers is countable and the proof says in order to do this you just have to show every rational number can be mapped to the set of natural numbers using a function. The function they choose is |p| + |q| where p and q are p/q where q > 0, which is the definition of a rational number. Then it says the number of preimages are no more than (2n+1)^2, but doesn't explain why. I can intuitively see that |p| + |q| = n for some natural number n is finite, but I don't really know how to prove it. Also I don't know where they got (2n+1)^2

Answer 1

With $q>0$, and $|p|+|q|=n$ the number of preimages is actually less than $(2n+1)^2$. It is $n(2n-1)$, because $q$ can take at most $n$ values, namely $1,2,\dots, n$, and $p$ can take any value between $-n+1$ and $n-1$, altogether $2(n-1)+1=2n-1$ values. It follows that the number of pairs $(p,q)$ such that $p,q$ are integers, $q>0$ and $|p|+|q|=n$ is precisely $n(2n-1)$.

Answer 2

Fix a non-negative integer $n$. Really, all you need to prove is that $S_n:=\{(p,q)\in \mathbb Q: |p|+|q|=n\}$ is either finite or countably infinite, because $\mathbb Q\subseteq \bigcup_n S_n.$ In fact, it is easy to show that $S_n$ is finite: the values of $p$ and $q$ cannot exceed $n$ in absolute value so $|S_n|$ is bounded by $(2n)^2+1.$

It might be easier just to note that $\mathbb Q^+=-\mathbb Q^-$ so $|\mathbb Q^+|=|\mathbb Q^-|$ and then inject $\mathbb Q^+$ into $\mathbb N$ via $(p,q)\mapsto 2^p\cdot 3^q.$