# The set of rational numbers is countable

The set $$\mathbb{Q}$$ of ra­tio­nal num­bers is countable: that is, there is a bi­jec­tion be­tween $$\mathbb{Q}$$ and the set $$\mathbb{N}$$ of nat­u­ral num­bers.

# Proof

By the Schröder-Bern­stein the­o­rem, it is enough to find an in­jec­tion $$\mathbb{N} \to \mathbb{Q}$$ and an in­jec­tion $$\mathbb{Q} \to \mathbb{N}$$.

The former is easy, be­cause $$\mathbb{N}$$ is a sub­set of $$\mathbb{Q}$$ so the iden­tity in­jec­tion $$n \mapsto \frac{n}{1}$$ works.

For the lat­ter, we may define a func­tion $$\mathbb{Q} \to \mathbb{N}$$ as fol­lows. Take any ra­tio­nal in its low­est terms, as $$\frac{p}{q}$$, say. noteThat is, the GCD of the nu­mer­a­tor $$p$$ and de­nom­i­na­tor $$q$$ is $$1$$. At most one of $$p$$ and $$q$$ is nega­tive (if both are nega­tive, we may just can­cel $$-1$$ from the top and bot­tom of the frac­tion); by mul­ti­ply­ing by $$\frac{-1}{-1}$$ if nec­es­sary, as­sume with­out loss of gen­er­al­ity that $$q$$ is pos­i­tive. If $$p = 0$$ then take $$q = 1$$.

Define $$s$$ to be $$1$$ if $$p$$ is pos­i­tive, and $$2$$ if $$p$$ is nega­tive.

Then pro­duce the nat­u­ral num­ber $$2^p 3^q 5^s$$.

The func­tion $$f: \frac{p}{q} \mapsto 2^p 3^q 5^s$$ is in­jec­tive, be­cause prime fac­tori­sa­tions are unique so if $$f\left(\frac{p}{q}\right) = f \left(\frac{a}{b} \right)$$ (with both frac­tions in their low­est terms, and $$q$$ pos­i­tive) then $$|p| = |a|, q=b$$ and the sign of $$p$$ is equal to the sign of $$a$$. Hence the two frac­tions were the same af­ter all.

Parents:

• Mathematics

Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.