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.