| Previous page (Dedekind cuts) | Contents | Next page (Cardinal numbers) |
The set Q of rational numbers was proved countable in an earlier section. Here is a different way of seeing the same thing.
Define the Farey sequence Fn to be the ascending sequence of fractions in the interval [0, 1] whose denominators are ≤ n.
F1= (0/1 , 1/1)
F2= (0/1 , 1/2 , 1/1)
F3= (0/1 , 1/3 , 1/2 , 2/3 , 1/1)
F4= (0/1 , 1/4 , 1/3 , 1/2 , 2/3 , 3/4 , 1/1)
F5= (0/1 , 1/5 , 1/4 , 1/3 , 2/5 , 1/2 , 3/5 , 2/3 , 3/4 , 4/5 , 1/1)
One nice thing about these sequences is the way they can be made.
To get the sequence Fn from the sequence Fn-1 , take an adjacent pair of fractions h1/k1 and h2/k2 (say) and provided k1 + k2 ≤ n, insert the mediant fraction (h1 + h2)/(k1 + k2) between them.
So, for example, to get F6 from F5 , insert 1/6 between 0/1 and 1/5 and insert 5/6 between 4/5 and 1/1 .
Some results about Farey sequences
You will be able to verify these for the examples above, but will probably not be able to prove them.
If h1/k1 and h2/k2 are successive fractions in a Farey sequence, then k2h1 - h2k1 = 1.
Given any three successive terms in a Farey sequence, the middle one is the mediant (see above) of the outer two. (*)
If h1/k1 and h2/k2 are successive fractions in the Farey sequence Fn , then k1 + k2 > n and if n > 1 no two successive terms have the same denominator.
Farey sequences were discovered by a British geologist John Farey (1766 to 1826) who published a note in 1816 containing the result (*) above. The English mathematician G H Hardy was rather dismissive of this:
He published no proof and it is unlikely that he had found one since he seems to have been at the best an indifferent mathematician.
The French mathematician Cauchy saw the note and quickly supplied the proofs.
Hardy continues,
Farey has a biography of twenty lines in the Dictionary of National Biography in which he is described as a geologist. As a geologist he is forgotten and his biographer does not mention the one thing in his life which survives.
| Previous page (Dedekind cuts) | Contents | Next page (Cardinal numbers) |