To show that : $\mathbb{Q}$ is countable

Set $A$ is said to be countable if there exists a bijection from $A$ to $\mathbb{N}$. Every countable set is infinite.

Further I have proved the following results:

  1. Set $A$ is finite or countable $\iff$ $\exists f:N\to A $ a surjection $\iff \exists g:A\to N$ an injection.

  2. Let $f:S\to T$ an injection where $T$ is countable and $S$ is infinite, then $S$ has to be countable. This result follows directly from 1.

$\mathbb{Q}= \{p/q \; | \; p\in Z,\; q\in N, (p,q)=1\}$

define. $f:\mathbb{Q}\to \mathbb{Z} \times \mathbb{N}$ as the identity map which is an injection too.

Now, $\mathbb{Q}$ is infinite as $\mathbb{N}\subset \mathbb{Q}$ and $\mathbb{N} $ is countable.

Also $\mathbb{Z}\times\mathbb{N}$ is countable as $\mathbb{Z}$ and $\mathbb{N}$ are countable and using the fact finite product of countable is countable.

Hence by 2. above $\mathbb{Q}$ is countable.

Is this proof okay?

  • 1
    $\begingroup$ This looks ok to me. In fact you can even inject directly into $\mathbb N$ via stuff like $(p,q)\mapsto 2^p3^q$. $\endgroup$
    – zwim
    Sep 11, 2019 at 20:14
  • $\begingroup$ @zwim $p$ can be negative. One could do $(p,q)\mapsto 2^q3^p$ if $p\ge0$, $2^q5^{-p}$ if $p<0$. $\endgroup$
    – egreg
    Sep 11, 2019 at 20:24
  • $\begingroup$ You can also consider the Stern-Brocot tree that is obviously countable and contains every positive rational. $\endgroup$
    – egreg
    Sep 11, 2019 at 20:29
  • $\begingroup$ just want to know if my method above is correct or not $\endgroup$
    – chesslad
    Sep 11, 2019 at 20:45
  • $\begingroup$ Basically, yes. The one tiny flaw is that you need to choose a canonical way of expressing a rational. Just requiring $q \gt 0$ solves the problem. $\endgroup$ Sep 11, 2019 at 21:00

1 Answer 1


Alternate proof.
As |Q| <= |Z×Z| and the latter is countable, Q is countable.
Since Q is infinite, it is countablely infinite, hence equinumerous to N.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .