Understanding Mathematics by Peter Alfeld, Department of Mathematics, University of Utah

Examples of denumerable sets


An infinite set is denumerable if it is equivalent to the set of natural numbers. The following sets are all denumerable:
  1. The set of natural numbers
  2. The set of integers
  3. The set of prime numbers
  4. The set of odd integers
  5. The set of even integers
  6. The set of rational numbers
The equivalence to the first four sets can be seen easily. The following table shows the pairings for the various types of numbers. n is the natural number, i the integer, p the prime number, o the odd number, e the even number.
   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]