The set of all rational numbers on the interval (0, 1] is certainly countable. We enumerate them in a peculiar manner. Assuming all are in lowest terms, then listing them in order of increasing denominators, where fractions with the same denominator are listed in order of increasing numerators. The first several terms of the sequence are

1/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, \ldots

I shall denote this sequence \{a_n\} and, following G. Cantor, use it to construct two other sequences \{b_n\} and \{c_n\} as was done in his first proof of uncountability of the reals.

So let b_1=a_1=1/1 and c_1=a_2=1/2. b_2 is the first of a_n's that lies between b_1 and c_1. Thus b_2=a_4=2/3. c_2 is the first of the remaining terms of a_n that lies between b_2 and c_1. We see that c_2=a_9=3/5. As the process continues we obtain further terms:

b_1=1/1

  

c_1=1/2

b_2=2/3

  

c_2=3/5

b_3=5/8

  

c_3=8/13

b_4=13/21

  

c_4=21/34

b_5=34/55

  

c_5=55/89

There could be little doubt that what we are getting is a sequence of successive Fibonacci numbers. More accurately, we have the following

Lemma 1

For all n \ge 0, we have that b_n = F_{2n−1}/F_{2n} and c_n = F_{2n}/F_{2n+1}.

(To remind: the Fibonacci sequence \{F_n\} is defined recursively, F_1 = F_2 = 1 and F_{n+2} = F_n + F_{n+1}.)

Proof

The proof is by induction. That the assertion holds for n=1 is a direct consequence of the definitions. Assume it holds for n=k, i.e. b_k = F_{2k-1}/F_{2k} and c_k = F_{2k}/F_{2k+1}. We'll show that b_{k+1} = F_{2k+1}/F_{2k+2}. The proof for c_{k+1} is similar.

First observe that F_{2k+1}/F_{2k+2} is the mediant feaction of b_k and c_k. As such, it lies between the two.

Remains to be shown that F_{2k+1}/F_{2k+2} is the first such fraction from a_n past b_k and c_k with that property.

Consider the Farey sequence of order 2k+2. Because of Cassini's identity, |F_{n}^{2}-F_{n-1}F_{n+1}|=1, b_k and c_k are neighbors in all the previous Farey sequences. Their mediant fraction is the only term that added between them by the extension to the sequence of order 2k+2.

Assume there is an irreducible fraction u/v, with F_{2k+1}\le v\le F_{2k+2} that lies between b_k and c_k. Such a fraction would belong to the Farey sequence of order 2k+2. But from the previous paragraph, the only such fraction is F_{2k+1}/F_{2k+2}, which completes the proof of Lemma 1.

As in the first proof of uncountability of the reals, there is number L that does not belong to the sequence a_n and is bounded by the terms of sequences b_n and c_n. However, lim_{t\rightarrow \infty}F_{t+1}/F_t=\phi, the golden ratio, so that lim_{n\rightarrow \infty}b_n=lim_{n\rightarrow \infty}c_n=1/\phi which exactly means L=1/\phi. L must be irrational, because it's not an element of \{a_n\} and 0 < 1/\phi = L < 1. Its reciprocal - \phi - is therefore also irrational.

Remark

There is a simpler proof of the irrationality of \phi. \phi satisfies a quadratic equation x^2 - x - 1 = 0, from which it follows that \frac{1}{\phi} = \phi-1. Assume now that \phi is rational: \phi = \frac{m}{n}, both are positive, 2n \gt m \gt n, and n the least possible. But then \frac{1}{\phi} = \frac{m}{n}-1 = \frac{m-n}{n}. In other words, if \phi = \frac{m}{n}, then also \phi = \frac{n}{m-n}. But m-n \lt n contradicts the minimality of n.

Observe, in passing, that since \phi = (\sqrt{5}+1)/2, we have obtained another proof of irrationality of \sqrt{5}.

References

  1. M. Krebs, T. Wright, On Cantor’s First Uncountability Proof, Pick’s Theorem, and the Irrationality of the Golden Ratio, Am. Math. Monthly, 117 (August–September 2010) 633-637