Analysis – Counting the rationals

It is easy to see that to show that \mathbb Q is countable, it suffices to show the countability of \mathbb Q^+, or even of \mathbb Q\cap(0,1].

I.

There is a straightforward way of enumerating the latter: First list the fractions with denominator 1, then those with denominator 2 (skipping those already listed), then those with denominator 3 (again, skipping repetitions), etc. This list begins

\displaystyle \frac11;\frac12;\frac13,\frac23;\frac14,\frac34;\frac15,\frac25,\frac35,\frac45;\dots

Cantor’s  first proof of the uncountability of the reals (the nested intervals argument) from 1874 proceeds as follows:

Given any (injective) sequence a_1,a_2,\dots of reals, we want to exhibit a real that was not listed. There are two cases: Either there are i\ne j with a_i<a_j, and such that there is no k with a_k\in(a_i,a_j), in which case we are obviously done, or (more interestingly), whenever a_i<a_j, we can find an a_k strictly in between (the range of the sequence is dense in itself). Assume we are in this situation.

Define two sequences b_1,b_2,\dots and c_1,c_2,\dots as follows:

  • First, b_1=a_1 and c_1=a_2.
  • For definiteness, suppose that a_1>a_2. The other case is treated similarly. Let b_2 be a_i, where i is least such that a_i\in(c_1,b_1). Then define c_2 as a_j, where j is least such that a_j\in(c_1,b_2).
  • In general, given c_n<b_n, we define b_{n+1} as a_k, where k is least such that a_k\in(c_n,b_n), and then define c_{n+1} as a_m, where m is least such that a_m\in(c_n,b_{n+1}). Note that these sequences are well defined, because of our density assumption.

The construction just described ensures that if I_n=[c_n,b_n], then:

  1. For any n, we have that a_n\notin I_{n+1}, and
  2. The intervals are nested and decreasing: I_1\supsetneq I_2\supsetneq I_3\dots

It follows (from the completeness of the reals) that \bigcap_n I_n\ne\emptyset, and (from 1.) that any real in this intersection is not in the range of the sequence a_1,a_2,\dots

It turns out that if we carry out Cantor’s construction when the sequence of a_i is the enumeration of the rationals in (0,1] we began with, then \bigcap_n I_n=\{1/\phi\}, where \phi is the golden ratio.

This is proved in the nice note

Mike Krebs, and Thomas Wright. On Cantor’s first uncountability proof, Pick’s theorem, and the irrationality of the golden ratio, Amer. Math. Monthly, 117 (7),  (2010), 633–637. MR2681523 (2011e:11127).

II.

There is a very nice enumeration of \mathbb Q^+ with combinatorial significance.

Binary trees

The rationals are used to label the nodes of the infinite complete binary tree, and the resulting enumeration simply follows the nodes of the tree, lexicographically.

Calkin-WilfWe begin by putting 1/1 at the root of the tree. Once a node has been labelled m/n, its left successor is labelled m/(m+n), and its right successor is latex (m+n)/n.

And that’s all! The list so produced begins

\displaystyle \frac11;\frac12,\frac21;\frac13,\frac32,\frac23,\frac31;\dots

The proof that this is indeed a bijective listing of \mathbb Q^+ is remarkably simple; one verifies in order the following claims:

  1. The numerator and denominator of any of the assigned fractions are relative prime.
  2. Every positive rational is assigned to some node.
  3. Every positive rational is assigned to some node.

For this, one proceeds by induction. For example, if there is a fraction m/n not in reduced form, and used as a label, pick such a fraction appearing in as small a level as  possible, and note that the fraction cannot be 1/1. A contradiction is now attained by noting that \mathrm{gcd}(m,n)=\mathrm{gcd}(m-n,n)=\mathrm{gcd}(m,n-m).

Similarly, if m/n appears in more than one node, then m\ne n, and its immediate predecessor (either (m-n)/n or m/(n-m), depending on whether m>n or m<n) must also appear more than once.

Finally, if some fraction is not listed, we can choose its denominator n least among the denominators of all skipped fractions, and then choose its numerator m least among the numerators of all skipped fractions with denominator n. A contradiction follows because m\ne n, and if m>n, then (m-n)/n must also have been skipped, but m-n<m, while if m<n, then m/(n-m) must have been skipped, but n-m<n.

This enumeration is due to Neil Calkin and Herbert Wilf, who also showed that it has the following nice combinatorial properties:

  1. There is a sequence b(0),b(1),b(2),\dots of positive integers such that the n-th fraction in the enumeration is just \displaystyle \frac{b(n)}{b(n+1)} (in reduced form). In particular, the denominator of a fraction is the numerator of its successor in the enumeration. So b(0)=1, b(1)=1, b(2)=2, b(3)=1, b(4)=3, b(5)=2, b(6)=3, etc.
  2. In fact, b(n) is precisely the number of ways of writing n as a sum of powers of 2, where each power can be used at most twice. For example, b(6)=3, because we can write 6 as 2^2+2^1, as 2^2+2^0+2^0, or as 2^1+2^1+2^0+2^0.

This is proved in the nice note

Neil J. Calkin, and Herbert S. Wilf. Recounting the rationals, Amer. Math. Monthly, 107 (4), (2000), 360–363. MR1763062 (2001d:11024).

Some natural questions:

  1. What can we say about the real(s) that comes out when the procedure from Cantor’s proof from section I is applied to this enumeration?
  2. Any infinite path through the binary tree defines a sequence of rationals. What reals appear as limit points of these sequences?

One Response to Analysis – Counting the rationals

  1. […] 30. Comparing infinities. Counting the rationals. This week, office hours end at 2:30. Office hours this week will be on Friday, […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: