# The set of rational numbers is countable

The set $$\mathbb{Q}$$ of rational numbers is countable: that is, there is a bijection between $$\mathbb{Q}$$ and the set $$\mathbb{N}$$ of natural numbers.

# Proof

By the SchrÃ¶der-Bernstein theorem, it is enough to find an injection $$\mathbb{N} \to \mathbb{Q}$$ and an injection $$\mathbb{Q} \to \mathbb{N}$$.

The former is easy, because $$\mathbb{N}$$ is a subset of $$\mathbb{Q}$$ so the identity injection $$n \mapsto \frac{n}{1}$$ works.

For the latter, we may define a function $$\mathbb{Q} \to \mathbb{N}$$ as follows. Take any rational in its lowest terms, as $$\frac{p}{q}$$, say. noteThat is, the GCD of the numerator $$p$$ and denominator $$q$$ is $$1$$. At most one of $$p$$ and $$q$$ is negative (if both are negative, we may just cancel $$-1$$ from the top and bottom of the fraction); by multiplying by $$\frac{-1}{-1}$$ if necessary, assume without loss of generality that $$q$$ is positive. If $$p = 0$$ then take $$q = 1$$.

Define $$s$$ to be $$1$$ if $$p$$ is positive, and $$2$$ if $$p$$ is negative.

Then produce the natural number $$2^p 3^q 5^s$$.

The function $$f: \frac{p}{q} \mapsto 2^p 3^q 5^s$$ is injective, because prime factorisations are unique so if $$f\left(\frac{p}{q}\right) = f \left(\frac{a}{b} \right)$$ (with both fractions in their lowest terms, and $$q$$ positive) then $$|p| = |a|, q=b$$ and the sign of $$p$$ is equal to the sign of $$a$$. Hence the two fractions were the same after all.

Parents:

• Mathematics

Mathematics is the study of numbers and other ideal objects that can be described by axioms.