Countability of Rational Numbers in Base 11

The set of positive rational numbers is countable.

We shall prove more, viz., that the set of all fractions p/q where p and q are positive integers, is countable.

Proof

Just think of the fraction p/q as an integer in base 11 where the slash is interpreted as the digit "10".

Example: 2/3 maps to 2×11² + 10×11 + 3 = 355.

This proof is the content of a half-page article by S. L. Cambell, at the end of which the author remarks that the approach allows for generalizations. For example, using 16 symbols

{O, 1, 2, 3, 4, 5, 6, 7, 8, 9, /, +, -, %, &, x}

one maps polynomials over rationals into integers. To this end, "%" is interpreted as the start of a superscript, "&" as the end of the superscript.

Following up on Campbell's article P. W. Epasinghe has observed that Campbell's method is similar in spirit to Gödel's enumeration wherewith the rational (-1)np/q is assigned a Gödel index 2n3p5q. This method is also expandable to enumerate polynomials with rational coefficients.

With a reference to Campbell's article, Pat Touhey suggested to include into the mapping fractions with negative numerators. This is done with an alphabet that includes 12 symbols:

{O, 1, 2, 3, 4, 5, 6, 7, 8, 9, -, /}

where "-" is interpreted as 10 while "/" as 11. Then, for example, -23/17 is mapped onto 2536579 because

10·125 + 2·124 + 3·123 + 11·122 + 1·121 + 7·120 = 2536579.

To represent polynomials with integer coefficients, Touhey chose the 14-symbol alphabet:

{O, 1, 2, 3, 4, 5, 6, 7, 8, 9, x, +, -, ^}.

Later on, Robert Kantrowitz has described what he called Principle of Countability:

The set of all words that may be formed using letters of a finite alphabet is countably infinite. Hence, any set of words that may be so formed is countable.

For a proof, observe that the Sn, k of all n-letter words from an alphabet of k symbols contains exactly kn words (including an empty one.) At this point we are going to employ a general

Lemma

Let there be a countable collection of finite sets An, n ∈ N. Then the union ∪An is also countable.

Proof of Lemma

Let an = |An| be the number of elements in set An. Define

sn = a1 + a2 + ... + an.

Note that s1 = a1. There is a function f1 that maps A1 onto [1, an] ⊂ N. There is a function f2 that maps A2 onto [s1 + 1, s2], and so on. There is a function fn that maps An onto [sn-1 + 1, sn].

Assuming the worst case where all An are pairwise disjoint, define f: ∪AnN so that, for a ∈ An, f(a) = fn(a). Function f is a 1-1 mapping of ∪An onto N.

Principle of Countability is the most general statement proved so far; it covers the results of Campbell and Touhey, but goes much further. For example, the alphabet may include radicals, integrals, several variables and still give rise to a countable set of formulas.

In the alphabet that includes the ten digits, the decimal point and the sign minus we may express any rational number with a finite decimal expansion. By adding one more symbol, say "*" we'll be able to include all periodic decimals, like

234.34454545... = 234.34*45*

Since rational numbers have either finite or periodic decimal expansion, Countability Principle yields an additional proof of the countability of rational numbers.

References

1. S. L. Campbell, Countability of Sets, Am. Math. Monthly Vol. 93, No. 6 (Jun. - Jul., 1986), pp. 480-481
2. P. W. Epasinghe, Letter to the Editor, Am. Math. Monthly Vol. 94, No. 4 (Apr., 1987), p. 351
3. R. Kantrowitz, A Principle of Countability, Mathematics Magazine Vol. 73, No. 1 (Feb., 2000), pp. 40-42
4. P. Touhey, Countability via Bases Other Than 10, The College Mathematics Journal Vol. 27, No. 5 (Nov., 1996), pp. 382-384