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 '19 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 '19 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 '19 at 20:29
  • $\begingroup$ just want to know if my method above is correct or not $\endgroup$ – Abhay Sep 11 '19 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$ – Robert Shore Sep 11 '19 at 21:00

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.


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.