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 = p₁^a₁ p₂^a₂ ... p_r^a_r, and n = q₁^b₁ q₂^b₂ ... q_s^b_s,

Form the number K(m/n) = p₁^2a₁ p₂^2a₂ ... p_r^2a_r q₁^(2b₁-1) q₂^(2b₂-1) ... q_s^(2b_s-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 2⁸ 3⁵ 13 17²? Separate the primes with even and odd exponents: 2⁸ 17² and 3⁵ 13. Modify them to agree with the definition of K: m = 2⁴ 17¹ and n = 3³ 13. K(2⁴ 17¹ 3^-3 13^-1) = 2⁸ 3⁵ 13 17².

If n = 1, m/n is just the integer m. K(m) = K(m/1) = p₁^2a₁ p₂^2a₂ ... p_r^2a_r = m².

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

References

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

Countability of Rational Numbers

71534088