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].

Every positive rational number has a unique representation as a fraction m/n with mutually prime integers m and n. Each of m and n has its own prime number decomposition. Let these be

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 N = K(m/n).

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 28 35 13 172? Separate the primes with even and odd exponents: 28 172 and 35 13. Modify them to agree with the definition of K: m = 24 171 and n = 33 13. K(24 171 3-3 13-1) = 28 35 13 172.

If n = 1, m/n is just the integer m. K(m) = K(m/1) = p12a1 p22a2  ...  pr2ar = m2.

(Another curious proof is based on enumeration of fractions on the Stern-Brocot tree.)

References

  1. Y. Sagher, Counting the Rationals, Am. Math. Monthly 96, 823
  2. M. Schroeder, Fractals, Chaos, Power Laws, W.H.Freeman and Company, 1991

Countability of Rational Numbers

|Contact| |Front page| |Contents| |Up| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

72002735