# 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_{1}^{a1} p_{2}^{a2} ... p_{r}^{ar}, and
n = q_{1}^{b1} q_{2}^{b2} ... q_{s}^{bs},

Form the number K(m/n) = p_{1}^{2a1} p_{2}^{2a2} ... p_{r}^{2ar} q_{1}^{(2b1-1)} q_{2}^{(2b2-1)} ... q_{s}^{(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 ^{8} 3^{5} 13 17^{2}?^{8} 17^{2}^{5} 13.^{4} 17^{1}^{3} 13.^{4} 17^{1} 3^{-3} 13^{-1}) = 2^{8} 3^{5} 13 17^{2}.

If n = 1, m/n is just the integer m. K(m) = K(m/1) = p_{1}^{2a1} p_{2}^{2a2} ... p_{r}^{2ar} = m^{2}.

(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

- Counting Ordered Pairs
- Countable Times Countable Is Countable
- Countability of Rational Numbers
- Countability of Rational Numbers: PWW
- Countability Principle
- Countability of Rational Numbers via Conitnued Fractions
- Fractions on a Binary Tree II
- Countability of Rational Numbers as a Union of Finite Sets
- A New Proof That the Rationals Are Countable

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

Copyright © 1996-2018 Alexander Bogomolny71522970