[Overview] [Previous] [Next]

Examples of Denumerable Sets

Example 1. The integers are denumerable. Here is one possible correspondence between the integers and the natural numbers:

{ 1, 2,  3, 4,  5, 6,  7, 8,  9, ...}
  |  |   |  |   |  |   |  |   |
{ 0, 1, -1, 2, -2, 3, -3, 4, -4, ...}

Notice that, given any natural number N, you can figure out what integer I it corresponds to, and vice versa:

if even(N) then I:=N/2 else I:=-((N-1)/2);
if I<0 then N:=(-2*I)+1 else N:=2*I;

Since we can put these two sets into a one-to-one correspondence, they must have the same number of elements, namely, aleph0.

Example 2. There are as many odd natural numbers as there are even natural numbers. To prove this, we note the following correspondence:

{ 1, 3, 5, 7,  9, ...}
  |  |  |  |   |
{ 2, 4, 6, 8, 10, ...}

Example 3. There are as many even natural numbers as there are numbers.

{ 1, 2, 3, 4,  5, ...}
  |  |  |  |   |
{ 2, 4, 6, 8, 10, ...}

Thus, "half of infinity is infinity." More precisely, aleph0/2=aleph0.

Example 4. aleph0-1 = aleph0. Proof:

{ 2, 3, 4, 5, 6, ...}
  |  |  |  |  |
{ 1, 2, 3, 4, 5, ...}

Example 5. The set of positive rational numbers (positive fractions) is denumerable.

A set is denumerable if it can be put into a one-to-one correspondence with the natural numbers. You can't prove anything with a correspondence that doesn't work. For example, the following correspondence doesn't work for fractions:

{  1,   2,   3,   4,   5, ...}
   |    |    |    |    |
{ 1/1, 1/2, 1/3, 1/4, 1/5, ...}

This correpondence doesn't work because there are fractions we never get to, e.g. 2/3. But here's a more complex correspondence that does work:

{  1,   2,   3,   4,   5,  ...}
   |    |    |    |    |
{ 1/1, 1/2, 2/1, 1/3, 2/3, ...}

This ordering comes from arranging the fractions in the order shown in the leftmost table below, then taking them in the order shown by the table at the right.

  ________________________     ____________________
 | 1/1  1/2  1/3  1/4  ...    |  1   2   4   7  ...
 | 2/1  2/2  2/3  2/4  ...    |  3   5   8  12  ...
 | 3/1  3/2  3/3  3/4  ...    |  6   9  13  18  ...
 | 4/1  4/2  4/3  4/4  ...    | 10  14  19  24  ...
 | ...  ...  ...  ...  ...    |... ... ... ...  ...

Copyright 1996 by David Matuszek
Last modified Mar 31, 1996