Countability of Rational Numbers
The set of rational numbers is countable. The most common proof is based on Cantor's enumeration of a countable collection of countable sets. I found an illuminating proof in [Schroeder, p. 164] with a reference to [Sagher].
m = p1a1 p2a2 ... prar, and n = q1b1 q2b2 ... qsbs,
Form the number K(m/n) = p12a1 p22a2 ... pr2ar q1(2b1-1) q2(2b2-1) ... qs(2bs-1). As a matter of fact, K is a function that maps any rational positive number onto a positive integer. A point of note is that K is a 1-1 correspondence. The rational number m/n can be unambiguously recovered from its image K(m/n). By the same token, to any integer N there corresponds a rational number m/n such that
The set Q of all rationals is thus equivalent to the set Z of all integers. The latter is equivalent to the set N of whole numbers.
Just to give an example, what rational number corresponds to
If n = 1, m/n is just the integer m. K(m) = K(m/1) = p12a1 p22a2 ... pr2ar = m2.
- Y. Sagher, Counting the Rationals, Am. Math. Monthly 96, 823
- M. Schroeder, Fractals, Chaos, Power Laws, W.H.Freeman and Company, 1991