n i p o e 1 0 2 1 0 2 1 3 -1 2 3 -1 5 3 -2 4 2 7 -3 4 5 -2 11 5 -4 6 3 13 -5 6 7 -3 17 7 -6 8 4 19 -7 8 . . . . . . . . . . . . . . .
It is more surprising, less obvious, and perhaps quite counterintuitive that the set of natural numbers is also equivalent to the set of rational numbers. To show that these sets are indeed equivalent we must order the rational numbers. The following proof is due to George Cantor. For ease of exhibition let us just consider the positive rational numbers. (To incorporate negative rational numbers we can, for example, pair even natural numbers with positive rational numbers, and odd natural numbers with negative rational numbers.)
(Positive) rational numbers are of the form p/q where p and q are natural numbers. These can be arranged in a table:
Of course, not all entries of this table are distinct. For example
1/1=2/2=3/3=4/4=5/5, or 2/4 = 1/2.In the next step we therefor erase all rational numbers that have non-trivial common factors in numerator and denominator.
Finally, to associate these numbers with 1, 2, 3, ... we start in the North-West corner of the Table, move down one row, go up diagonally in a North-East direction, until we reach the first row, go one column to the right, go back down in a South-West direction until we hit the first column, and continue in this manner:
So the "ordering of the rational numbers is:
1, 1/2, 2, 3, 1/3, 1/4, 2/3, 3/2, 4, 5, 1/5, 1/6, 2/5, 3/4, 4/3, 5/2, ...
Fine print, your comments, more links, Peter Alfeld, PA1UM
[16-Aug-1996]