1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Assuming $|p|,|q| \le n$, $p$ is between $-n$ and $n$ inclusive which is $2n+1$ choices. Certainly there are even less choices for $q$, so an upper bound for the number of preimages is $(2n+1)^2$. $\endgroup$ – mysatellite Sep 7 at 21:27
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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