On this day in 1873, II

A little over a week ago I wrote about a letter from Cantor to Dedekind that contained an auspicious question, namely whether the sets of natural and (positive) real numbers could be put into one-to-one correspondence with each other.

On 7 December 1873 Cantor wrote Dedekind with the answer to his question; the answer was (and still is) “no”. The letter contains a proof of the impossibility of a one-to-one correspondence between the two sets.
This was the first time that something like this was done: attempt to compare two infinite entities by pairing off the elements of the sets such that every element of the first was paired with exactly one from the second and vice versa.

Cantor went on to study this idea in depth and he showed how to give a precise meaning to the idea that one set has (strictly) more (or fewer) elements than another set.
To get back to the original question: it is clear that there are at least as many real numbers as there are natural numbers as the latter set is a subset of the former. Cantor’s proof showed that there are strictly more real numbers than there are natural numbers.
There is a difference between this situation and the one mentioned in Cantor’s letter of 29 November, 1873: he mentioned that the natural numbers also form a subset of the positive rational numbers (all fractions of the form p/q with natural numbers p and q). Thus, it seems that there are more such rational numbers than that there are natural numbers. But, we can pair off the members of both sets in such a way that to one member of one set corresponds exactly one member of the other set.
To see this divide the fractions into groups: put fraction p/q into group n if p+q=n. Now observe that group n contains exactly n-1 fractions: 1/(n-1), 2/(n-2), …, (n-1)/1. This makes it easy to arrange the fractions in a nice simple sequence: first group 2, then group 3, then group 4, and so on and inside each group arrange the fractions according to their numerators, as we did above in group n.
The resulting sequence looks like this: 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, … and this makes it easy to pair off the natural numbers and the positive fractions as desired.

Exercise Try to devise a formula for the number that goes with the fraction p/q, or, conversely, concoct a formula that tells us what the nth fraction is.

Exercise What would you do if you had to pair off the natural numbers and the positive rational numbers (one rational number corresponds to many fractions).

Here you can read Cantor’s letter in German. It is a scan from Briefwechsel Cantor-Dedekind. And here you can read my translation into English.

Be Sociable, Share!

• 
•