# 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)^{n}p/q is assigned a Gödel index 2^{n}3^{p}5^{q}. 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·12^{5} + 2·12^{4} + 3·12^{3} + 11·12^{2} + 1·12^{1} + 7·12^{0} = 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 S_{n, k} of all n-letter words from an alphabet of k symbols contains exactly k^{n} 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 A_{n}, n ∈ **N**. Then the union ∪A_{n} is also countable.

### Proof of Lemma

Let a_{n} = |A_{n}| be the number of elements in set A_{n}. Define

s_{n} = a_{1} + a_{2} + ... + a_{n}.

Note that s_{1} = a_{1}. There is a function f_{1} that maps A_{1} onto _{n}] ⊂ **N**._{2} that maps A_{2} onto _{1} + 1, s_{2}],_{n} that maps A_{n} onto _{n-1} + 1, s_{n}].

Assuming the worst case where all A_{n} are pairwise disjoint, define _{n} → **N**_{n}, _{n}(a)._{n} 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

- S. L. Campbell,
__Countability of Sets__,*Am. Math. Monthly*Vol. 93, No. 6 (Jun. - Jul., 1986), pp. 480-481 - P. W. Epasinghe,
__Letter to the Editor__,*Am. Math. Monthly*Vol. 94, No. 4 (Apr., 1987), p. 351 - R. Kantrowitz,
__A Principle of Countability__,*Mathematics Magazine*Vol. 73, No. 1 (Feb., 2000), pp. 40-42 - P. Touhey,
__Countability via Bases Other Than 10__,*The College Mathematics Journal*Vol. 27, No. 5 (Nov., 1996), pp. 382-384

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

Copyright © 1996-2018 Alexander Bogomolny