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
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.
(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 Bogomolny72002735