6
$\begingroup$

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?

$\endgroup$
9
  • 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$
    – Abhay
    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

0
$\begingroup$

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.

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