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)ⁿp/q is assigned a Gödel index 2ⁿ3^p5^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⁵ + 2·12⁴ + 3·12³ + 11·12² + 1·12¹ + 7·12⁰ = 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ⁿ 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₁ + a₂ + ... + a_n.

Note that s₁ = a₁. There is a function f₁ that maps A₁ onto [1, a_n] ⊂ N. There is a function f₂ that maps A₂ onto [s₁ + 1, s₂], and so on. There is a function f_n that maps A_n onto [s_n-1 + 1, s_n].

Assuming the worst case where all A_n are pairwise disjoint, define f: ∪A_n → N so that, for a ∈ A_n, f(a) = f_n(a). Function f is a 1-1 mapping of ∪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

Countability of Rational Numbers

41169508