# 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 ### Countability of Rational Numbers 