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** *F*_{n} to be the ascending sequence of fractions in the interval [0, 1] whose denominators are ≤ *n*.

*F*_{1}= (^{0}/_{1} , ^{1}/_{1})

*F*_{2}= (^{0}/_{1} , ^{1}/_{2} , ^{1}/_{1})

*F*_{3}= (^{0}/_{1} , ^{1}/_{3} , ^{1}/_{2} , ^{2}/_{3} , ^{1}/_{1})

*F*_{4}= (^{0}/_{1} , ^{1}/_{4} , ^{1}/_{3} , ^{1}/_{2} , ^{2}/_{3} , ^{3}/_{4} , ^{1}/_{1})

*F*_{5}= (^{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 *F*_{n} from the sequence *F*_{n-1} , take an adjacent pair of fractions *h*_{1}/*k*_{1} and *h*_{2}/*k*_{2} (say) and provided *k*_{1} + *k*_{2} ≤ *n*, insert the *mediant fraction* (*h*_{1} + *h*_{2})/(*k*_{1} + *k*_{2}) between them.

So, for example, to get *F*_{6} from *F*_{5} , 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 *h*_{1}/*k*_{1} and *h*_{2}/*k*_{2} are successive fractions in a Farey sequence, then *k*_{2}*h*_{1} - *h*_{2}*k*_{1} = 1.

Given any three successive terms in a Farey sequence, the middle one is the mediant (see above) of the outer two. (*****)

If *h*_{1}/*k*_{1} and *h*_{2}/*k*_{2} are successive fractions in the Farey sequence *F*_{n} , then *k*_{1} + *k*_{2} > *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) |