# Proof verification : $\mathbb{Q}$ is countable

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?

• This looks ok to me. In fact you can even inject directly into $\mathbb N$ via stuff like $(p,q)\mapsto 2^p3^q$.
– zwim
Sep 11, 2019 at 20:14
• @zwim $p$ can be negative. One could do $(p,q)\mapsto 2^q3^p$ if $p\ge0$, $2^q5^{-p}$ if $p<0$. Sep 11, 2019 at 20:24
• You can also consider the Stern-Brocot tree that is obviously countable and contains every positive rational. Sep 11, 2019 at 20:29
• just want to know if my method above is correct or not Sep 11, 2019 at 20:45
• 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. Sep 11, 2019 at 21:00